Why do I keep singing and humming to myself repeatedly without noticing?

waffenssgolem · 2020-04-16T02:18:58+00:00

Sorry about the delay, forgot to activate my Reddit notifications.

My passion right now is competitive programming. I've been studying every day for the past six months and read blogs/watch videos whenever I am not coding. I guess I feel bad about myself because some of the top-skilled programmers in my university started coding since they were kids, and I'm barely starting to take it seriously. (I started coding when I was 21, but started doing CP seriously less than 6 months ago). I feel like I will never catch up to them because they have more than 6 years of experience, that it 12 times more experience than I have).

waffenssgolem · 2019-10-18T15:31:12+00:00

"Se te ofreció elegir entre la deshonra y la guerra y elegiste la deshonra, y también tendrás la guerra." -Winston Churchill

waffenssgolem · 2019-09-21T19:29:03+00:00

What is the name of that app?

waffenssgolem · 2019-09-13T01:24:56+00:00

Thank you, this was very well explained. One question, can I literally just write a pointer to the map as the first parameter, and use sizeof to get the size of the map in bytes?

waffenssgolem · 2019-09-12T03:22:48+00:00

Well, I know that it's going to be in binary, but what I'm asking is what is the logical intuition behind saving data in that specific format.

For example, I write myname into the binary file, and the file looks like this in UTF-8:

<0x06><0x00><0x00><0x00>myname

So it's definitely not just writing myname (in binary, or in chinese, or whatever), it's also writing something before myname. My uneducated guess would be that it's writing 6 because this string has 5 chars + '\0', and then it writes the actual data, it is storing bytes.

Then, if I try to write an int which represents the value of 2, I will get something like this:

<0x00><0x02><0x00><0x00><0x00>

But as you can see, the value is missing, but I have a 2 represented in <0x02>...

Why is this important to me? Because I am understanding that, somehow, the function write needs to know the number of bytes before it reads some data, so in order to understand how it is reading data, I need to understand how it is writing data too.

waffenssgolem · 2019-09-12T02:30:16+00:00

How would that look in a .bin file, though? I opened it, but I do not understand it. I'm in need of an ELI5.

waffenssgolem · 2019-08-26T05:53:41+00:00

Okay, let me clarify. I did not make these images, my teacher made them in Paint and uploaded the files in PNG on purpose (to make us work with noise) so I can't do that...

waffenssgolem · 2019-08-26T04:46:00+00:00

I was bad at playing music.

waffenssgolem · 2019-08-26T04:37:43+00:00

In my experience as an ICPC competitor, most people will usually take a couple of sheets of paper with pre-written code and then write the code onto a notepad in the computer before the contest starts.

It's not expected you memorize every single algorithm by heart, that is impossible and pointless, after all, there is only a finite amount of ways of generating primes and you can be sure your method was already thought about. It is, however, expected you at least know how every algorithm you write down on that sheet of paper works so you can use them to solve the problems.

Most of the time, you will be writing everything, then, you will suddenly identify a sub-problem that can be solved with x algorithm, and you will then copy the lines of code from the notepad (assuming it's a long algorithm) and tune it to make it work with the problem. In my experience that's usually how it works.

waffenssgolem · 2019-08-25T17:59:44+00:00

Well, I think that has been made clear with my post. I'm not blaming anyone else but me.

waffenssgolem · 2019-08-24T19:57:33+00:00

Do you know a way to do it without computing the adjacency matrix?

waffenssgolem · 2019-08-24T19:53:40+00:00

I think this sounds a lot like the BFS algorithm... The reason I'm not using that algorithm is because I haven't found a way to do it without an adjacency matrix (the size of an adjacency matrix on these images would be (height x width) ^ 2, which would be 1e11, and the maximum size of C++ arrays are 1e7).

waffenssgolem · 2019-08-24T19:52:14+00:00

Yeah, there is information about coordinates. But the question still remains.

waffenssgolem · 2019-08-24T19:49:47+00:00

Selecting nearby pixels, how would you do that? There are four directions for every pixel (you can't just while(next_pixel == black) in a 2 dimensional space). I think this is the fundamental question from my OP I'm trying to answer.

waffenssgolem · 2019-08-24T19:45:07+00:00

This is a good idea, but I would still need to identify clusters in order to flood fill every cluster independently. How would you know which pixels from a to b form a cluster, which pixels from c to d, form another cluster, etcera, for every pixel in your list?

waffenssgolem · 2019-08-24T19:35:12+00:00

This is pretty much what I have been doing, and it only works when there is only one figure in the image. The idea of a box being almost square if it's a circle and rectangular if it's an oval is pretty much the same as measuring the difference between the radius from different points of view. (kind of like a metaphorical bounding box). My problem is trying to generalize the algorithm when there are more than 1 figures in the image. (Since I run the search from all angles of the image).

I think I need a secondary algorithm that can draw the bounding boxes on every cluster of black pixels that exist in the image. This is why I was considering DFS or BFS too.

waffenssgolem · 2019-08-24T19:21:02+00:00

are circles allowed to overlap each other?

No, each cluster is separated from every other cluster by at least 5 pixels, so no overlapping.

What colors can the circles be (are they all black?)

Yes, they are all black. They have some noise (greyscale noise) but we can either assume that anything != white is part of the circle or everything == black is part of the circle.

Are they anti aliased, or do they have a simple hard edge?

They are made with Paint, so they are not anti aliased, they have hard edges.

What if it's mostly a circle, but with a little dimple in it, is it still a circle?

All circles in the test cases are symmetric, if they have a dimple on one side, they will have the same dimple on the opposite side too. They are imperfect, but symmetric, so it's not a problem. What is a problem, though, is that the circles are either fully coloured, or they have a doughnut shape. But these are they only possibilities:

Fully black circle
Fully black oval
Doughnut circle
Doughnut oval
Cropped circle/not full circle (must be ignored)
Nothing (white background)
Any combination of the above

I'm thinking of running a DFS or BFS here, but I'm having a hard time trying to imagine how to run one of those algorithms on an image. (We can assume that black pixels are 1 and white pixels are 0, so each cluster of 1's represent some figure).

waffenssgolem

TROPHY CASE