MikeMirzayanov's blog

2021-2022 ICPC, NERC, Northern Eurasia Onsite (Unrated, Online Mirror, ICPC Rules, Teams Preferred)
By MikeMirzayanov, 3 years ago, In English

Hello.

In the meantime, the onsite event has already begun. You can follow the results at the link https://nerc.itmo.ru/archive/2021/standings.html (refrain from viewing if you want to plan to write a mirror and want the conditions as close as possible to the participants in the competition).

There is great news. This year it was possible to get together without any online participation. Teams write from one computer! Good old ICPC.

And I suggest you join the online mirror. It is designed for team participation by those who have passed the qualifying competitions. Ready to try? Use the link: 2021-2022 ICPC, NERC, Northern Eurasia Onsite (Unrated, Online Mirror, ICPC Rules, Teams Preferred).

Good luck!

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

Comments Comments (18)
| Write comment?
»
3 years ago, # |
  Vote: I like it -23 Vote: I do not like it

Why was memory limit so tight in problem L
Got 10 MLE. How to solve it without bfs or dfs?
Because I tried both and it gave MLE.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    we solved it using dfs and without any MLE

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Not sure what you did but BFS worked for me. At first I tried DFS but got wrong answer, probably just my mistake. No memory issues though.

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I got MLE too. For me it was because I didn't mark the source as visited. So after reaching destination when I generated the paths it got into an infinite loop which overflowed the vector memory.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve E?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Binary search the minimum length of segments, and then binary search the maximum one.

    I'm not able to prove it, though.

    → Reply
»
3 years ago, # |
← Rev. 5   Vote: I like it +8 Vote: I do not like it

Why are time limit and memory limit so tight in problem A ?

I submitted 30 times and finally passed all tests.

Also, I think this problem is a trash. I claimed that the answer is not so big (maybe $$$\sim \frac{n^2}{2}$$$), so you just need to write a $$$\mathcal O(n^2\log n)$$$ code, and use some trick to optimize it (ML & TL), then it passed.

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +10 Vote: I do not like it

    Do u mean "trash" instead of "trush"?

    And i think that there exist an $$$O(n^2+\frac{n^2\log n}{w})$$$ solution using bitset.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, "trash".

      I wonder if there exists an solution better than $$$O(n^2)$$$. One of my friends says he can solve it in $$$O(\frac{n^{9/4}}{\omega^{1/2}})$$$ :D

      → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +57 Vote: I do not like it

How to prove that both minimum of maximum length and maximum of minimum length is achievable at the same time on E?

→ Reply
»
3 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Any idea how to solve I?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +45 Vote: I do not like it

    Scan top left (1, 1) and bottom left (N, 1) to get the sum of x coordinates and the sum of y coordinates. Then, scan (sumX/2, 1) and (1, sumY/2) to get the difference between x coordinates and the difference between y coordinates. Knowing information about the sum and difference gives us the chance to get individual values of x and y coordinates. Dig (minX, minY) to determine if the treasures are at points (min, min) and (max, max) or (min, max) and (max, min). We used 4 scan queries and 3 dig queries which fits perfectly to the query limit.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I see. Thanks! It seems your idea makes sense. I did a bit math and obtain this :

      Spoiler
      → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 3   Vote: I like it +5 Vote: I do not like it

    I want to write about my idea cause it is different idea from Zappeko. My idea is kind of using idea for build a decision tree (sorry if it's not). Let's say currently we have K possibility of placement for that 2 treasures (in the beginning, K = C(N*M, 2)).

    You can just try every N*M way of asking a SCAN operation with calculation to the K possibility. if you are the jury, if you asking by a SCAN operation, one good way to answer is with the number with most occurrence in K possibility. So, you will use a SCAN operation in a cell with the least number of most occurrence in K possibility --> because in worst case it will give you maximum reduction of K possibility of placement.

    Can't prove it will be fit for 7 times of using operation, i just code it and getting accepted.

    Sorry for my bad english, hope you all that read my comment can understand that. :)

    → Reply
»
3 years ago, # |
  Vote: I like it +14 Vote: I do not like it

When I was checking the shortest solution of problem E, I found this submission.

It seems strange, so I modified the 5000 in the code to 2000, and it gets WA on test 19.

Maybe weak tests lol, can anyone give a hack?

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +22 Vote: I do not like it

NERC standings

Mirror standings

Combined standings

→ Reply
»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Here is the link to the editorial if anyone's looking for it: https://neerc.ifmo.ru/archive/2021/nerc-2021-tutorial.pdf

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody help me with L ? I am finding the common node using visited array which stores the sub-tree node number as the visited integer. Then I could just check if this node wasn't visited from the current sub-tree. If it is, it immediately backtracks and returns the answer. For path, I'm again doing a dfs which maintains a single visited array and backtracks as soon as the destination is found. I am failing test case 65. I tried checking for multiple edges and self nodes, but that didn't work. 184063528

→ Reply