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.
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!
Typo: contest ID 1773, not 1733.
Thanks, fixed.
Hello! When will the contest be open for upsolving?
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.
Basically, 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.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.
Found!Closerand $$$s_2$$$ corresponds toFurther.Closerand $$$t_2$$$ corresponds toFurther.Closer.Closerusing similar observations as above.Closer, you can find the mapping forFurtherusing a reverse query.Same distanceby doing the same query twice.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.
Was it coordinate descent?
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.
Ask (0, 0), (0, 0) and (1, 1). Unless the answer is (0, 1) or (1, 0), you get first equal, then closer.
Thanks. This seems much easier. I overkilled it.
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.
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.
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
When can we submit the problems in practice mode?
Will we have the tutorial?
OK, it's here: https://nerc.itmo.ru/archive/2022/nef-2022-tutorial.pdf
any hint for I?
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)
Entropy worked for me using your definition, except I did these steps first:
Then it's possible to manually search the next digit to ask quickly enough, and it works in 10 queries.
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
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.
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
how to solve problem D ?
Could not write an AC solution yet, but these should be the cases of the two cells that make the tiling impossible.
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.
NEF and Mirror combined standings
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.
I don't know how to optimise the time complexity, but space complexity isn't hard to cut to $$$O(2^n)$$$.
Let's compute DP[i] = chance of it reaching a state of mask i as in set bits represent people that haven't gotten any answer wrong. From state i, whenever it takes a question that "i AND question_mask != i" (all such questions aren't yet taken because otherwise the AND of all taken questions wouldn't be i) it goes to a state with less bits.
The problem is optimizing the transition and I guess you did that by iterating through submasks in some way. We can solve the problem from here in O(2^M * M^2).
Let's have an array A[i] = number of questions with mask of answers i.
At first we know the answer for DP[(1 << M) — 1]. If we use AND convolution of that DP array with the array A we almost have the contribution of transitions from state "(1 << M) — 1" to submasks of it. What's missing is dividing it by the number of masks that change result when we take the AND. A mask of questions "j" won't change the AND with "i" iff j is a supermask of i. So if we take B[i] = sum of A[j] for j supermask of i, then N — B[i] is the number of masks that will change state.
Now, to apply that transition in general we can simply apply it to states with M active bits, then M-1 active bits and so on.
The solution is: For each BITS from M to 1, take D[i] = 0 if pop_count(i) != BITS otherwise DP[i] / (N — B[i]). Then take the AND convolution of D and A, that'll give us the contribution of states with BITS active bits to states of less than BITS active bits. Add the result of that convolution to the corresponding positions for every position with less than BITS set bits.
can you explain your solution as well?
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
can someone please give hint for problem A
Two random permutations have 1 element in common in the expectation
coudle you please express more clear? i am not so clever,can not understand it
Well, that was supposed to be a hint, not a full solution :P. The more direct hint is that
You can try drawing q randomly and checking if it leads you to the solution
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
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.
why 700 is enough
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
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.
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
Actually, the only test data for which no $$$p$$$, $$$q$$$ exists is:
So if you know the answer exists, you can just use "infinitely" many turns. Proof by AC: 184521024
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?
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.
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
Hey, I know this thread is like two months old, but I'm wondering why this idea is "intuitive".
Obviously, it can be proven mathematically but I don't see how someone could figure out this probability on the fly.
Thank you.
I guess it helps if someone has seen similar facts/exercises about permutations and understands the intuition behind them. You may want to read up on derangements if you haven't heard about them https://en.wikipedia.org/wiki/Derangement
On a higher level, you may think that this problem is very loosely constrained. You have a ton of freedom. If you have a lot of freedom, there is a chance that some kind of random/heuristic solution may pass
Thanks for the quick response! I'll read that page now...
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.sorry, i was wrong there. In a multi-testcase problem, its about probability that it passes all test cases simultaneously. So, definitely probability of passing is decreased.
How can we generate random permutation repeatedly more times can u explain.
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
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).
could tell me why from n-2 nodes to get path one need O(n)
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).
hey can you please specify exactly what you mean or give code.
No.
Okay.
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$$$
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?
I inserted into the cycle in some arbitrary spot and then just reversed the edges of the cycle.
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.
For 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.
$$$q[i]$$$ = $$$p^{-1}[x]$$$
$$$a^{-1}[i]$$$ = x
then for any i, q[i] can be equal to anything except i and x
so now make a graph x->i, it wont be difficult to prove this graph will be union of disjoint cycles
and 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 arr1
then, 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 fashion
then merge and get array q which uniquely determines array p
Is there any editorial ?
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?
maybe you can submit here(https://mirror.codeforces.com/contest/1773/submit)
Any hints regarding problem K, please.
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.
Am I the only one who doesn't see others' submissions? Even for solved problems
Can anyone help me how to solve A?
random
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.
With randomisation: https://mirror.codeforces.com/blog/entry/109856?#comment-978371
Without randomisation: https://mirror.codeforces.com/blog/entry/109856?#comment-1007263
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?
MikeMirzayanov, when submissions of other participants of this round will be opened?
Solved A: Amazing trick without using randomisation.
Idea is to first make a parent graph(directed graph) where i is linked to a[i] (i-->a[i]). Now, there will be multiple disjoint cycles of this graph. Append all disjoint cycles in a single array (flatten it) such that [a-->b-->c-->d-->a], [e-->f-->e] is taken as a, b, c, d, e, f. Link by skipping 2 indices. So, a-->c-->b, b-->d-->c, ....., e-->a-->f, f-->b-->e. where first transition is linked by q and second one by p. This way fixed point do not occurs in p and q. Also, there is an edge case corresponding to this approach where there are two disjoint cycles with size [[n-1][1]](eg. a-->b-->c-->a, d-->d where c-->a-->a transition gives a fixed point for p). So, to tackle these test cases skip by 3 instead of 2. Impossible cases are [ n=1, [1] ],[ n= 2, [2] ], [ n=3, [1][2] or [2][1] ].