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!
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.
we solved it using dfs and without any MLE
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.
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.
How to solve E?
Binary search the minimum length of segments, and then binary search the maximum one.
I'm not able to prove it, though.
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.
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.
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
How to prove that both minimum of maximum length and maximum of minimum length is achievable at the same time on E?
Any idea how to solve I?
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.
I see. Thanks! It seems your idea makes sense. I did a bit math and obtain this :
Assume treasures are located in (ra, ca) and (rb, cb)
Grid size is R x C
Scan :
1 1
R 1
(ra-1) + (rb-1) + (ca-1) + (cb-1) = ans0
ra + rb + ca + cb — 4 = ans0
(R-ra) + (R-rb) + (ca-1) + (cb-1) = ans1
ca + cb — ra — rb + 2R — 2 = ans1
2ra + 2rb — 2R + 2 = ans0-ans1
2ra + 2rb = ans0 — ans1 + 2R + 2
ra + rb = (ans0 — ans1 + 2R + 2) / 2
sumr = (ans0 — ans1 + 2R + 2) / 2
2ca + 2cb — 6 + 2R = ans0+ans1
2ca + 2cb = ans0+ans1 + 6 — 2R
ca + cb = (ans0+ans1 + 6 — 2R)/2
sumc = (ans0 + ans1 + 6 — 2R) / 2
Scan :
sumr/2 1
1 sumc/2
|ra — sumr/2| + |sumr/2 — rb| + (ca-1) + (cb-1) = ans2
|ra — rb| + ca + cb — 2 = ans2
|ra — rb| = ans2 + 2 — sumc
difr = ans2 + 2 — sumc
|ca — sumc/2| + |sumc/2 — cb| + (ra-1) + (rb-1) = ans3
|ca — cb| + ra + rb — 2 = ans3
|ca — cb| = ans3 + 2 — sumr
difc = ans3 + 2 — sumr
Assume
ra >= rb
Then :
sumr = ra+rb
difr = ra-rb
2ra = sumr+difr
ra = (sumr+difr)/2
2rb = sumr — difr
rb = (sumr-difr) / 2
Assume
ca >= cb
Then :
sumc = ca+cb
difc = ca-cb
2ca = (sumc + difc)
ca = (sumc + difc) / 2
2cb = (sumc — difc)
cb = (sumc — difc) / 2
If both our assumption is correct, then answer is (ra, ca) and (rb, cb)
However if there's no treasure at (ra, ca) then ca < cb, therefore treasure is located at (ra, cb) and (rb, ca)
(P.S. Im too lazy to write in latex format)
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. :)
When I was checking the shortest solution of problem E, I found this submission.
It seems strange, so I modified the
5000in the code to2000, and it gets WA on test 19.Maybe weak tests lol, can anyone give a hack?
NERC standings
Mirror standings
Combined standings
Here is the link to the editorial if anyone's looking for it: https://neerc.ifmo.ru/archive/2021/nerc-2021-tutorial.pdf
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