th3_g0d's blog

By th3_g0d, 10 years ago, In English

Good time of a day, Codeforces community :)

I actually was a little bit uncertain if I have the right (well not right but if my question is eligible for asking) to ask help in this problem. The tag on the problem says that it can be solved with Segment/Interval Tree but I tackled the problem and was unable to solve it. I had some ideas of solutions that used the Linked List, but well, you know it was too slow :) I browsed the web for the solution but was unable to find it. Finally, I found the bravery and am asking the help from you :) The task is HERE.

I am very grateful to anyone that found the time to read this.

Thank you very much in advance! :)

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By th3_g0d, 11 years ago, In English

Hi, everyone! :)

As you know from 13th to 20th of January The International Olympiad in Informatics, Physics and Mathematics named after Orymbek Zhautykov(hope I wrote the name correctly) will be held in Kazakhstan, Almaty.

I think that is a bit unfortunate that organisers do not post the official solutions or at least hints for the problems. I was unsuccessful in finding the test data and statements for problems too for a while. Luckily, the tasks and test data of the previous IZHO were published here. If anyone knows solutions for problems, you can help others by sharing your knowledge here.

Have fun! :)

*Regarding the first problem of DAY1 I had a solution that computed the change in x and y coordinates for Gorlum and tried to simulate the process in O(1) by adding Dx to x and Dy to y coordinates. I was also identifying whether the Gorlum converges or diverges the Laser. So there are basically three cases:

1) After going through the string of commands Gorlum returns to the position where he started. In this case, we just have to simulate the string once and find the max and min distances observed.

2) Gorlum converges the Laser. Here we just have to add dx and dy change values to our current coordinates and wait till it starts to diverge from the Laser. actually on that intersection of Gorlum and Laser we can find the nearest point.

3) Gorlum diverges from the Laser. Here we can again simulate the process and look for maximum distance.

*Note: I also simulate the last and first cycles fully because there can be the answers for the farthest and nearest points.

Here is my code.

This was my solution for this problem. However, it seems incorrect. And now I don't have an idea that would fit in time. If anyone knows the solution I would be grateful if you shared. :)

Full text and comments »

  • Vote: I like it
  • +5
  • Vote: I do not like it

By th3_g0d, 11 years ago, In English

:) Hello everyone,

Yesterday took place Round#3 of Croatian olympiad.

It seemed to me that contest was a bit unbalanced because first 3 problems were easier than usual. However, the 4th one seemed more complicated than usual. I think it would be great if people would share their ideas about problems here.

Could anyone explain the approach for problem 4? I think we had to use Binary Search there to find the amount of meat. However, I could not find the way I had to build my binary search. I think there was only a certain continuous range of solutions. Though, I could not figure out how and when to change the bounds of binary search.

Full text and comments »

  • Vote: I like it
  • +5
  • Vote: I do not like it