Блог пользователя MateiX21

Автор MateiX21, история, 23 месяца назад, По-английски

Does someone have the day 1 rankings ?

  • Проголосовать: нравится
  • +94
  • Проголосовать: не нравится

»
23 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In the question group, they said that they will publish it tomorrow morning.

»
23 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

When you log in, it shows "Final Standings", but they are not available.

»
23 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Where can I see statements of the first day?

»
23 месяца назад, # |
  Проголосовать: нравится +58 Проголосовать: не нравится
»
23 месяца назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Guys, did you receive problems in math and physics of second day?

»
23 месяца назад, # |
  Проголосовать: нравится +34 Проголосовать: не нравится
»
23 месяца назад, # |
  Проголосовать: нравится +55 Проголосовать: не нравится

Hi everyone. IZhO is finished, and I want to share with my experience on this contest. I got 353 points (100/ 100/ 30/ 51/ 67/ 5). Sorry if I will make a lot of mistakes, it's 4 at night, and I'm writing this comment just because I'm bored. So, let's start.

  • Problem A of the first day. I got 100 points. It was pretty good problem for it's place as the easiest of the first day. It's not too hard, yet not that easy. You need some observations and simplifications to solve it. Points distribution was good. The full soltuion reminded me of the problem Farmer 2. I ain't got much to say about this problem.
  • Problem B of the first day. It was interesting problem in my opinion. First I quickly got first subtask. Then started solving for the line. I kind of moved my root through the tree, and when we more rood from position $$$i$$$ to position $$$i+1$$$, the only 2 subtrees that changes in the first tree is the sizes of the subtrees in $$$i^{th}$$$ and $$$i+1^{th}$$$ positions. So I can recalculate the subtree size for them, and for the next tree we need to keep the answer for all possible roots, we can do it in the segment tree. To do so, we need to look at the case when for the duplicate for the $$$i^{th}$$$ vertex, it's on the right or on the left or the root. We need to consider this two cases and calculate the subtree size in different cases and according to that update the answer for the possible roots to the left of it or to the right. After I solved for the line, I thought I came up with the full solution. But then realised that my soltion works in the $$$O(\sum deg^{1}_{a} \times deg^{2}_{a} \times log(n))$$$ (let's say that $$$deg^1_a$$$ is the degree of $$$a$$$ in first tree and $$$deg^2_a$$$ is in the second one) complexity. Each time I moved from let's say parent $$$p$$$ of the vertex $$$v$$$, I needed to go through all the kids of $$$p$$$ in the second tree. So in the worst case it's $$$O(N^2log(N))$$$. So I kind of got upset. But I still tried it to get 4th subtask, because maximum degree of the vertex in this subtask is $$$3$$$. After I submitted it passed for full. I was surprised and confused if I calculated the complexity correctly. I thought a win is a win, so I didn't spend much time on this and passed to the next problem. I may be wrong, but I think that test data was week. Let me know if you wrote similar solution and it also passed for full. Also, I came up with the $$$N\sqrt{N}log(N)$$$ solution, uptimizing times where we need to update the tree. It might somehow pass for the second subtask, but I doubt it.
  • Problem C of the first day. Maybe I was tired after previous two problems, or was very happy to get 100 on two problems in one day of the contest, I'm not sure. But I didn't felt like solving this problem and just got 30 points and I was done. Or I just didn't like this problem. Also I was sick on both days, so that may be the reason I didn't want to solve this problem.

Any way I finished 13th (with like 10 people having the same points as I got). So I needed to do good in second day, in order to keep my position.

Next day, when I woke up my throat hurt a lot. So I took some medicine from my teacher, and 2 hours before the contest, I started feeling sleepy. Fortunately, at the beginning of the contest, my mind cleared, after I started solving problems. Also 2 hours before the contest all our participants received message with the problems of the second day in math and physics. After like 5-10 minutes, the link to the access to the problems was closed. I thought that second day may be postponed because of this, but organizers simply said to maintain academic integrity. This was very weird. I guess they tried to send this message to the translators for the international participants, but they accidently sent it to the participants. Anyway, let's talk about problems.

  • Problem A of the second day. I solved it for 51 points. I think it's an interesting problem. I think after I solved it for 51 points, I came up with the solution for the 63 points. But I thought like, I will probably spend like 15 minutes writing this segment tree, while I already spent an hour, so I decided to move to the next problem.
  • Problem B of the second day. I got 67 in this problem. When I started solving this problem I misunderstood problem, and spent 35 minutes on it. After I submitted my code for first subtask, it got 0. So for some time I tried to find the bug in the code, but I couldn't. And then, I reread the problem statement, and finally understood that I was solving totally different problem. Then I quickly changed the code, and got the first subtaks. I came up with the solution for the case where they choose just start the game, without doing any moves. I coded solution for the line, writing some of the part of the solution for the tree. But I had some stupid bug, and I wrote the solution just for line, and stresstested using it as the brute force solution. After getting points for line, I changed some parts of the code to get the points for the tree. But this solution also contained some bugs, which were pretty stupid as well, so I needed to code the solution for the $$$n, q \leq 10$$$, and stresstest using this solution. And finally after getting 56 points(it was already 4:15, I had like 45 minutes till the end), I decided to finish this problem for full, I didn't even read the problem C, but I had 44 points left in this problem, and clear solution in my mind (I thought it was crystal clear at the time). So after changing solution for full, I got 67 points. So it passed for little tree, but it didn't for the big one. I tried so hard to find some bugs or cases I didn't take into account. I found some, and fixed them, but it still didn't pass. When 20 minutes left, I decided to get at least few points in the problem C, and gave up B.
  • Problem C of the second day. I rushed to problem C, read it really quickly, and got 5 points. I did what I could in this 10-15 minutes I had. Also, since I was in a rush, my mind didn't work clearly, so I couldn't get any more points.

And that's how my contest ended. I was unsure with my position in the ranking, but obviously I hoped for good position in top 30 (usually they give gold to top 30). I was very nervous but the next day morning my coach sent me the message that I'm 22nd, and I was very happy. I'm happy with my performance, although I think I could have done a little better. I still don't understand the problem in my solution for the B of the second day and why my $$$N^2log(N)$$$ solution for the B of the first day passed. Anyway, I am waiting for the problems to be posted in the ACM Kazakhstan group or in the oj.uz. Congratulations if you achieved your expectations, if you didn't, it's the experience which worth the most, so keep up the work, do your best in the next one. It was my last IZhO, so thank you for reading this story and bye.

  • »
    »
    23 месяца назад, # ^ |
      Проголосовать: нравится +19 Проголосовать: не нравится

    It passed 6 minutes since I posted this comment, and while I was rewatching my screencast video, I found one more mistake. I need problems to be posted somewhere for upsolving, so I can check if this was the reason my code failed. Please release them as soon as possible.

  • »
    »
    23 месяца назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится

    In B1 you can just sort the kids of every vertex in the second tree by their sizes, then you don't need to go through each kid of p, you can just binary search for the first kid, whose subtree will be increased.

    • »
      »
      »
      23 месяца назад, # ^ |
        Проголосовать: нравится +16 Проголосовать: не нравится

      Ohh, that's nice. I didn't think about that. But still, why my solution where I went through each kids passed for full.

  • »
    »
    23 месяца назад, # ^ |
    Rev. 5   Проголосовать: нравится +10 Проголосовать: не нравится

    UPD: Now you can solve problems in group ACM Kazakhstan.

    I was looking for different cases to find my mistake in the solution for the problem B2. I spent like an hour or so writing stres to check, and I accidently realised that I didn't print $$$":"$$$ in some of the cases. I had a lot of this kind of stupid moments on different contests on codeforces and even on IOI, but I guess this is my biggest and at the same time so tiny mistake. I feel so dumb right now. I guess this will be a big lesson for me, so that I won't make any this type of stupid mistakes from now on. Be very careful reading the problem and looking at the output format, and hope my story helped you.

    here is the difference between correct and incorrect solutions.