### MikeMirzayanov's blog

By MikeMirzayanov, 2 months ago, translation,

Hello!

Tomorrow (December 7th) the ICPC Northern Eurasia Finals (previously known as NEERC) will take place. The competition will be held at several venues: St. Petersburg, Barnaul, Kutaisi and Almaty. Almost 300 teams will take part in it.

Onsite Contest Current Standings →
Don't look in it if you take part in the online mirror contest

We invite you to join the online mirror of the competition: 2022-2023 ICPC, NERC, Northern Eurasia Onsite (Unrated, Online Mirror, ICPC Rules, Teams Preferred). It will start at Dec/07/2022 11:05 (Moscow time). We recommend participating in teams, but experienced individual participants will also have fun.

The duration of the competition will be 5 hours. Of course, the round is unrated.

Good luck!

• +158

 » 2 months ago, # |   +1 Typo: contest ID 1773, not 1733.
•  » » 2 months ago, # ^ |   0 Thanks, fixed.
 » 2 months ago, # |   +65 Hello! When will the contest be open for upsolving?
•  » » 2 months ago, # ^ | ← Rev. 2 →   -9 Hello! When will the contest be open for upsolving???
 » 2 months ago, # |   0 I thought of problem H's solution for the whole 5-hour period, but still I couldn't solve it. I hope I could get some help towards finalizing the current approach. Here's my current approach so far. My current approachBasically, 64 queries is not a very hard limit if we know what the word means. We would be even able to cut the limit to 40, by using binary search twice (once on the x axis, once on the y axis). Finding out the words' meanings is the hardest part.I thought it would be possible to find out the words' meanings by splitting the area in a few vertical/horizontal sections, each with odd length (so that we don't get ties), and then doing a case work. If we query the point between the section with the other parameter fixed, we would get something like CCC...CCFF...FFF. So the first one here is "Closer", and the last one here is "Farther". but I am not certain if we are able to construct a list of queries that makes the meanings clear. (Because we won't be able to extract any information from the first query in the search). If this is possible, the rest would not be too hard.
•  » » 2 months ago, # ^ |   +10 On the contrary, I was able to deterministically find out the language mapping in atmost $11$ queries but could not figure out how to perform the search in less than $4\log{10^6}$ queries. My approach to find the language mapping Terminate if any of the answers end with an exclamation mark. It corresponds to Found! Query $(0,0), (1,0), (2,0), (0,0), (0,1), (0,2)$. Let the answers be $x, s_1, s_2, y, t_1$ and $t_2$. If $s_1\neq s_2$, it means that $s_1$ corresponds to Closer and $s_2$ corresponds to Further. If $t_1\neq t_2$, it means that $t_1$ corresponds to Closer and $t_2$ corresponds to Further. If $s_1=s_2=t_1=t_2$, all of these correspond to Closer. If $s_1=s_2$ and $t_1=t_2$ but $s_1\neq t_1$, it means that either the x-coordinate of the treasure is $0$ or the y-coordinate of the treasure is $0$. Query $(10^6,10^6)$, $(10^6-1,10^6)$ and $(10^6-2,10^6)$ to get which string corresponds to Closer using similar observations as above. If you know the mapping for Closer, you can find the mapping for Further using a reverse query. You can know the mapping for Same distance by doing the same query twice.
•  » » » 2 months ago, # ^ |   +10 May I ask what your approach for $4 \log 10^6$ queries was? I have a guess for it, but I am not very sure. My guessWas it coordinate descent?
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   0 Do two binary search, one for the x-coordinate and other for the y-coordinate. To determine if the x-coordinate lies to the left or right of $m$, do queries on $(m,0)$ and $(m+1,0)$.Edit — Just got AC using $3\log 10^6$ queries for searching. You can do both binary searches simultaneously by querying $(mx,my)$, $(mx+1,my)$ and $(mx+1,my+1)$ to reduce the search space of both x and y to half in $3$ queries.
•  » » » 2 months ago, # ^ | ← Rev. 2 →   +36 Ask (0, 0), (0, 0) and (1, 1). Unless the answer is (0, 1) or (1, 0), you get first equal, then closer.
•  » » » » 2 months ago, # ^ |   0 Thanks. This seems much easier. I overkilled it.
•  » » 2 months ago, # ^ |   +19 Your claim for 40 queries in two separate binary searches is quite optimistic because it's not easy to do a binary search (though I believe it's possible in theory to approach this limit).As a side note, there was a similar problem on IOI2010 that focuses on the 1D version, where the words "hotter" and "colder" are known. It's quite tricky, you can try it in the IOI archive on Codeforces: https://ioi.contest.codeforces.com/group/32KGsXgiKA/contest/103756/problem/B.
•  » » » 2 months ago, # ^ |   +10 You are correct, 40 queries would be a theoretical limit. I think a ternary search would be possible within 52 queries, and it should be sufficient to pass the task.
•  » » 2 months ago, # ^ | ← Rev. 2 →   +2 Determining the language is easy, so focus on the search part.I solve for both coordinates independently (I always set the other one to zero), so let's think of it in 1D. The problem is that we are not able to do binsearch easily as for that to work we would need to be able to ask questions for out of bounds points. In my solution I keep an interval $[L, R]$, where the answer is within that and my last question was either in $L$ or $R$. I want to shrink this interval 3 times using 2 questions and maintain my invariant about last question being in one of the ends of my interval. For simplicity assume that last question was in L. Then I ask about $c = \frac{L + 2R}{3}$. If I get "further" then I know that my answer is within $[L, \frac{2L+R}{3}]$ and I already shrunk my interval 3 times and I can ask my next question in L to maintain the invariant. If I get "closer" then I ask about $c+1$. Depending on the answer I restrict to either $[\frac{2L+R}{3}, c+1]$ or $[c+1, R]$. That uses $4 \cdot log_3(10^6)$ questions for the search part, so in addition with constant number of queries determining the language, it barely fits into the limit
 » 2 months ago, # |   +23 When can we submit the problems in practice mode?
 » 2 months ago, # |   +17 Will we have the tutorial?
•  » » 2 months ago, # ^ |   +3 OK, it's here: https://nerc.itmo.ru/archive/2022/nef-2022-tutorial.pdf
 » 2 months ago, # |   0 any hint for I?
•  » » 2 months ago, # ^ | ← Rev. 4 →   +6 You can brute force it locally. Consider finding a place with the highest entropy (or similar).
•  » » » 2 months ago, # ^ |   +3 The first thing that came to mind was also entropy. But it worked for 11 queries. Is it different for you? (I changed entropy just to minimise max size of equivalent factorials)
•  » » » » 2 months ago, # ^ |   +3 Entropy worked for me using your definition, except I did these steps first: Spoiler Consider only the first 2000 digits. Start by asking position 1475. (actually there are multiple positions that do just as good or better in the initial split, but running the decision tree using that heuristic gives them depth 11.) Then it's possible to manually search the next digit to ask quickly enough, and it works in 10 queries.
•  » » 2 months ago, # ^ |   +8 Just always ask the question that minimizes the size of the biggest class that you restrict to after getting an answer. Though it will be a bit slow, but if you hardcode first move (that does not depend on anything) as 1475 (that you compute with your a bit too slow code) then it is fast enough
•  » » » 7 weeks ago, # ^ |   0 Is there any way to prove that minimizing the size of the bigger class after getting answer to the query guesses the answer in less than $10$ queries other than actually running the solution code on all $5982$ numbers locally? Because if that is the case, the problem is not very interesting.
•  » » » » 7 weeks ago, # ^ |   0 I doubt. But I mean, that should be the first thing to try if we are minimizing the worst-case and it works, I don't need the concise math proof. Talking about entropy a bit surprises me as we are not talking about the average case. It's not a mind-blowing problem, but I guess it's a fair one
 » 2 months ago, # |   0 how to solve problem D ?
•  » » 2 months ago, # ^ |   0 Could not write an AC solution yet, but these should be the cases of the two cells that make the tiling impossible. The two cells are on a different connected component. The two cells are on the same connected component, and are on the same color (The color being $x+y \bmod 2$) The two cells are on the same connected component, are on the different color, and the two cells divide the component to more than one so that at least one of the divided components are invalid (i.e. odd area or invalid color matching),
•  » » 2 months ago, # ^ |   +11 Covering with dominoes is of course matching between white and black cells. Let $w, b$ denote number of white and black cells that remained. Of course we have $w=b$ and if we remove cells of the same color then we win, so the true answer is at least $2 \cdot {w \choose 2}$, so if $w > 1005$ then we are done, because we simply output $10^6$ and we are allowed to solve the rest of the problem in quadratic complexity in terms of number of free cells. We compute the matching. The answer will be ${2w \choose 2}$ minus the number of pairs so that after their removal there is still a full matching, so we focus on counting these. Then, for each white cell, we unmatch it and remove it and want to count how many black cells we can remove so that there is still a full matching. These are simply reachable vertices from the black cell that was matched with the removed white cell, so we count these using one DFS.
 » 2 months ago, # |   0
 » 2 months ago, # | ← Rev. 3 →   0 I have $O(3^m \cdot m)$ time and $O(3^m)$ memory in G (and it passed). That sounds like a lot. Was that intended that it passes or was there some better solution? Being afraid of that was the main reason why I decided to focus on J instead of G, which was a bad decision.
•  » » 2 months ago, # ^ |   0 I don't know how to optimise the time complexity, but space complexity isn't hard to cut to $O(2^n)$.
•  » » 2 months ago, # ^ |   0 can you explain your solution as well?
•  » » » 2 months ago, # ^ | ← Rev. 2 →   +16 I want to compute for each subset of people, the prob of Genie winning if this is the subset of people that are alive. Key observation is that this value does not depend on the history of questions.In order to compute that dp, from each state I iterate over all possible submasks that I can get to with the soonest question that tells apart some of the people in it. For that I need to know following values $f(A,B,C)$ denoting what is the number of questions that has zeros on set A, ones on set B and whatever on set C (where A,B,C is some partition of all people). I compute these in SOS-like manner in $O(3^m \cdot m)$ time and array storing there takes around 520MB
 » 2 months ago, # |   +3 can someone please give hint for problem A
•  » » 2 months ago, # ^ | ← Rev. 2 →   +15 HintTwo random permutations have 1 element in common in the expectation
•  » » » 2 months ago, # ^ |   +6 coudle you please express more clear? i am not so clever,can not understand it
•  » » » » 2 months ago, # ^ |   +1 Well, that was supposed to be a hint, not a full solution :P. The more direct hint is that HintYou can try drawing q randomly and checking if it leads you to the solution
•  » » » » » 2 months ago, # ^ |   +7 thank you very much, maybe i have kown how to solve it, because permutation "q" have restrict, so we can use bipartite to get q. is that? i get this idea at first,but i worry about it will spend much time, because Hungarian algorithm need take O(n*m) time,and in this problem one point have n-2 edges,this is the thing that i worry about
•  » » » » » » 2 months ago, # ^ |   +6 It's nothing like that what you describe. Draw random q. It uniquely determines p. Check if neither q nor p have any fixed point. If they do, repeat from scratch. If not successful in some number of turns (I tried 700 times), declare as impossible.
•  » » » » » » » 2 months ago, # ^ |   0 why 700 is enough
•  » » » » » » » » 2 months ago, # ^ |   +3 Intuitively, the chance that a random permutation has no fixed point is around $1/e$, so for two permutations it would be $1/e^2$, which is more than $1/9$. 100 may be too less for $10^5$ test cases (and indeed I got WA), but 700 sounds more than safe
•  » » » » » » » » » 2 months ago, # ^ |   +3 Even better would be to check if there's some answer by using Hall's theorem. There's a valid answer iff there isn't a value blocked by N positions and there isn't 2 values blocked by N-1 positions. 2 values being blocked by N-1 positions doesn't happen for N > 3 so checking these conditions is easy.
•  » » » » » » » » » 2 months ago, # ^ |   0 That's probably clever and all that, but one would need to get any understanding of the structure of this problem first xD My approach has this advantage that it is basically brainless and super easy to code making it probably the optimal approach on the competition, though solutions like yours are of course much more legit from the theoretical point of view
•  » » » » » » » » » 2 months ago, # ^ |   +31 Actually, the only test data for which no $p$, $q$ exists is: [1] [2, 1] [1, 3, 2] [2, 1, 3] [3, 2, 1] So if you know the answer exists, you can just use "infinitely" many turns. Proof by AC: 184521024
•  » » » » » » » » » 7 weeks ago, # ^ |   0 Thanks for your approach..., in these contests we are not allowed to see others code even after getting AC. Could you please post your code here?
•  » » » » » » » » » 6 weeks ago, # ^ | ← Rev. 5 →   0 Ig the reason WA for c=100 times is not because of 10^5 test cases, but because of probability of failing can be made greater than (1-1/e^2) according to input, due to dependency. Correct me if i m wrong, if we use std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count()); within each test case, then it's like each test case being independent, as the seed will be different.Also, can anyone say upper bound for probability of random permutation to have no common point wrt any two permutation.,I m curious to know it.
•  » » » » » » » » » 6 weeks ago, # ^ |   +1 I added srand(clock()); on th beginning of each test-case and my code passed with c=100, but I think that is a pure luck as it gets WA with c=90 and I think 100 is just on the verge of getting accepted.However I have to agree that 100 should sound fairly safe if it was indeed independent 1-1/e^2 on each try (80 wouldn't though). I don't feel like delving into details what causes that difference though
•  » » » » » » » 4 weeks ago, # ^ |   0 How can we generate random permutation repeatedly more times can u explain.
•  » » » » » » » » 4 weeks ago, # ^ |   0 I don't get your question. Do you know what random_shuffle is? If yes, just apply it many times and you get various random permutations
•  » » 2 months ago, # ^ |   +4 You can treat it as a bipartite matching problem. A greedy approach will find a matching of size at least N-2. We want a perfect matching, so starting from a matching of size N-2 we can find O(1) augmenting paths in O(N).
•  » » » 2 months ago, # ^ |   +1 could tell me why from n-2 nodes to get path one need O(n)
•  » » » » 2 months ago, # ^ |   +4 Find the path with BFS. From unmatched vertex, you can reach N-2 vertices in the other partition. From that point onwards, keep the unmatched vertices in the other partition in a vector, there'll be <= 2 such vertices. You can check if an edge to a vertex exists in O(1).
•  » » » » » 2 months ago, # ^ |   0 thanks ,i have understand your idea, i think maybe it can use humgry algorithm to solve from n-2 nodes,
•  » » » 5 weeks ago, # ^ |   0 hey can you please specify exactly what you mean or give code.
•  » » » » 5 weeks ago, # ^ |   +3 No.
•  » » » » » 5 weeks ago, # ^ |   0 Okay.
•  » » 2 months ago, # ^ | ← Rev. 4 →   +4 the ideas other people proposed are a bit simpler than my way but I started off by thinking about cyclic shifts — for a cycle of length $>2$ mapping each element $a_i := a_{a_i}$ results in a valid $q$ which allows you to derive $p$ for the elements in that cycle. So then you just have to figure out how to cover the cycles of length $\leq 2$
•  » » » 2 months ago, # ^ |   -8 what cycle mean? and how you get q by mapping?
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 I originally tried so too, but I couldn't figure out how to cover cycles of length less than 2. Like what if we have a large enough cycle (say, of length 100) and a smaller cycle of length 1? Then, if you map $a_i := a_{a_i}$, the smaller cycle can't get covered.How did you deal with that edge case?
•  » » » » 2 months ago, # ^ |   +6 I inserted into the cycle in some arbitrary spot and then just reversed the edges of the cycle.
•  » » 2 months ago, # ^ |   0 Ok, so let's suppose that there is a set of integers that doesn't occur in $q$ at given moment. If this set has at least 3 elements, for every $i$, we can set $q[i]$ as one of these elements (as every $q[i]$ has at most two integers that cannot be put there). Problem starts when there are only 2 elements left in this set. So we only want to make sure that remaining 2 elements will suit in remaining positions. Rest of the solutionFor some small $n$, let's say $n \leq 7$ we can use brute force, just check every possible $q$. For $n > 7$ let's fix 2 elements that will be the last in the set. Let's say it'll be 1 and 2. We want to be sure, that these elements will suit in two positions in $q$ at the end, to do this first we'll fill the positions where 1 and 2 cannot be put. There are no more than 4 these positions, so we can fill them using remaining elements for sure. Then we do our algorithm: we iterate over $i$ where $q[i]$ isn't filled yet and we check at most 3 elements from the set to find any number that suits here. Remember that this set doesn't have elements 1 and 2, as we want to leave them for the last steps. At the end we'll get two unset positions, but we know that we can put 1 and 2 there, as we eliminated all the positions where 1 and 2 don't suit. Note that we don't need to use set here, normal vector is enough.
•  » » 2 months ago, # ^ |   0 my solution$q[i]$ = $p^{-1}[x]$$a^{-1}[i]$ = xthen for any i, q[i] can be equal to anything except i and xso now make a graph x->i, it wont be difficult to prove this graph will be union of disjoint cyclesand if you print the nodes in dfs order( arr[i],arr[i+1] in this order implies q[arr[i]]=arr[i+1] ) then that would give the correct answer, the problem occurs if the cycle was of length two.So handle them separately, first do the above step for != 2 length cycles and make array arr1then, let other length 2 cycles be a->b, c->d, e->d make new array as arr2 = a,c,b,e,d,f... in this fashionthen merge and get array q which uniquely determines array p
 » 2 months ago, # | ← Rev. 2 →   +23 Is there any editorial ?
 » 2 months ago, # |   0 Hey MikeMirzayanov. Thank you for making the contest available for upsolving. Unfortunately, task K can not be submitted now (only PDF statement can be downloaded). Can you please fix this?
•  » » 2 months ago, # ^ |   +11 maybe you can submit here(https://codeforces.com/contest/1773/submit)
 » 2 months ago, # |   +5 Any hints regarding problem K, please.
•  » » 2 months ago, # ^ |   0 Try reducing problem for (n, k) to problem for (n-2, k-2). For that to work you will also need solutions for base cases k=1 and k=2.
 » 2 months ago, # |   +8 Am I the only one who doesn't see others' submissions? Even for solved problems
•  » » 5 weeks ago, # ^ |   0 i am too
 » 2 months ago, # |   0 Can anyone help me how to solve A?
•  » » 2 months ago, # ^ |   +3 random
•  » » 2 months ago, # ^ |   +3 If you can determine $q$, then you can determine $p$ (because it is essentially $a^{-1} \circ q^{-1}$). The probability that a random permutation will have fixed points is pretty low (probably $\frac{1}{n}$, without proof). Knowing this, you can shuffle $q$ multiple times, until you can trust yourself that the answer will be found if it exists.
 » 2 months ago, # |   0 from editorial of c, what's topological structure of a graph? for the grouping what operation is considered? is there an alternative approach to think? any helpful reading material?
 » 2 months ago, # |   -8 Can anyone help me with E I tried it by comparing a[i-1] > a[i] then we will do split++ and tower++ for each of the n array then splits will be split and combine will be tower-1 but it gives WA dont know why
 » 7 weeks ago, # |   0 MikeMirzayanov, when submissions of other participants of this round will be opened?
 » 5 weeks ago, # | ← Rev. 4 →   -8 Nothing
 » 4 weeks ago, # | ← Rev. 2 →   0 Hi! I am getting TLE continuously (at the very first test case). Here is the input for which the TLE is happening:566 239Znaydeno!Daha yakinDalejSama distancoTabilmadiHere I have a few questions: The question says: "All phrases contain only Latin letters, spaces, and exclamation marks.." — how come the numeric input "566 239" has come? Numbers are not letters. It is not even generated from my program, as the program starts running by printing the point "0 0". Why there are inputs even after "Znaydeno!" (which indicates termination)? Am I missing something? Some information: I have used std::getline(std::cin, command); for taking inputs. General output format std::cout << x << " " << y << std::endl;. I believe, std::endl performs flush itself. Just after getting "Found!" (or any other string containing an '!' sign), my program terminates by returning void, i.e, return; I think there is a very basic thing I am missing, I cannot understand the root cause of the TLE. Thanks!
 » 4 weeks ago, # |   0 How to solve Problem E?
 » 2 weeks ago, # | ← Rev. 2 →   0 Will we be able to see the submissions of other participants at any point? I'm kinda stuck on E. I've read the tutorial and understand the general idea but I think I'm still missing something and get WA on one of the testcases.