We hope you liked the problems! Before we go ahead with the editorial, let us make some general comments about this round.
Problems A, B, C, D, E, F are "div 2" problems, while problems G, H, I are meant to be solved by Grandmasters. Overall, our goal was to provide a problemset that could be enjoyable for a wide range of participants and such that the winner could solve all the problems.
There were three big "jumps" in the difficlty gaps between consecutive problems. Problems A and B are meant to be easy, many contestants have the skills and the techniques to attack them (and, maybe, to solve them). Problems C, D, E, F are gradually harder but the difficulty gap between C and F is not as large as usual (and this is reflected in the score distribution). The same holds for problem G, H, I; the difficulty gap between G and I is relatively small (but there is a big score difference because coding I is much harder). Sadly, we discovered 14 minutes into the round that problem I has already appeared in a contest (most likely also in Polish contest, if you know it please tell us in the comments). See also this comment.
Let us now make some predictions (you, future reader, can check whether we were right or wrong). We promise not to change these predictions after the beginning of the contest.
- After 20 minutes someone has solved 4 problems.
- After 40 minutes someone has solved 6 problems.
- After 70 minutes someone has solved 7 problems.
- After 100 minutes someone has solved 8 problems.
- At least one contestant solves all the problems.
- There is a big difference in number of solves between F and G (let's say a factor 3).
- The best Italian contestant solves 6 problems.
- There are $$$\ge 10\,000$$$ solves for problem A.
The contest is now finished and our predictions are far from being perfect, but, for intellectual honesty, we are not changing them.
In problem 1552A - Перестановка подпоследовательности you had to sort a sequence by changing the minimum number of elements... you better not touch elements which are already in the correct position! Fun fact: this problem appears again, as an optimization step (not really required to get accepted), in problem G.
Problem 1552B - Забег за золотом, about the ongoing Olympic Games, had a real-life statement and an obvious quadratic algorithm which had to be improved to get accepted. It could be solved either by an intuitive observation (only one athlete can win the gold medal!) or with a super-simple randomized approach. This problem was added (and changed) last-minute (that is, 2 days before the contest) to make the problemset more balanced. Bonus version: with the same constraints, find the number of athletes who are "likely to get a medal", i.e. who are superior to all but (at most) $$$2$$$ other athletes.
In problem 1552C - Максимизируйте пересечения you had to maximize the number of intersections of chords in a circle. It's natural to add the new chords so that they all intersect each other... it turns out that this is enough to solve the problem! This was a subproblem of a harder problem that we discarded because it did not fit the problemset (and it was not particularly nice).
Problem 1552D - Массив как разность, in which you had to write an array as differences of the value of another array, was an undercover graph problem. Once the necessary and sufficient condition is identified, coding it is very easy. Until 5 days before the contest, this was problem B. Since it was too hard for a B, it was moved to D and a new problem B was added.
Problem 1552E - Цвета и отрезки is a combinatorics problem that asks you to select some "almost disjoint" intervals respecting certain properties. It can be tackled by unexpected simple greedy algorithms. Some variations of this problem appeared in the past (we know of at least two similar problems), but since it is a nice problem and nobody found this version anywhere we decided to give it anyway.
At first sight, problem 1552F - Муравьепортация, about an ant moving and teleporting, seems to require an exponential amount of time to be solved. Once one notices that the states of the portals satisfy a rigid property, it is not hard to come up with a polynomial (actually pseudo-linear) solution. If one drops the assumption $$$y_i<x_i$$$ it becomes impossible for the authors to solve it.
Problem 1552G - Серьезный судья presents you with a daunting task: you are given a "generalized" sorting network and you must tell whether it really is a sorting network or not. Standard knowledge about sorting networks is useful but not sufficient to solve the problem.
Problem 1552H - Угадайте периметр is a strange interactive problem in which you must guess the perimeter of a hidden rectangle. The number of available queries in astonishingly small and one has to come up with a way to find the perimeter without really identifying the rectangle. Initially cip999 had proposed it with $$$7$$$ queries, then dario2994, after failing to solve it for a couple of days, came up with the $$$4$$$ queries solution.
In problem 1552I - Организовываем музыкальный фестиваль you have to count the number of permutations with certain sets of values which are contiguous. The statement is very simple but the solution is a bit of a mess to find and also to code. This is the only problem of the problemset whose implementation is involved. It entered in the problemset when we noticed that the previous problem I could be solved by a dull heuristic (which made cip999 really sad). The first version of the problem had $$$n=20$$$, it was a problem E/F and could be solved by subsets-dp, but antontrygubO_o said (and rightly so) "I am afraid this is too standard". This rejection pushed dario2994 to solve the problem in polynomial time and send it back to antontrygubO_o, who finally accepted it. The official solution can handle also $$$n=1000, \, k=1000$$$, but, since it was only a bigger pain to code, we decided to give the "small constraints" version. Sadly, it turns out that the problem was not new for some participants (but there were also some genuine solutions to the problem during the round).
- A: Original statement by cip999, current statement by dario2994. Prepared by cip999.
- B: Original statement and preparation by dario2994.
- C: Original statement by cip999, current statement by dario2994. Prepared by cip999.
- D: Original statement and preparation by cip999.
- E: Original statement by cip999, current statement by dario2994. Prepared by cip999.
- F: Original statement by cip999, current statement by dario2994. Prepared by dario2994.
- G: Original statement by cip999, solution by dario2994. Prepared by dario2994.
- H: Original statement by cip999, solution by dario2994. Prepared by dario2994.
- I: Original statement and preparation by dario2994.
This was the first round ever that I (co-)organized, so I'm eager to share some of my experience with the Codeforces community!
During the problemsetting phase of the preparation I've been the main proposer, basically for two reasons:
- dario2994 didn't have much time to think about problems;
- I was totally new to problemsetting and felt the need to propose every problem I came up with, no matter how horrible it was. (Regarding the second point, I believe I am going to write a separate blog post, where I will comment on the negative aspects of some of the ugliest problems I proposed, so that, hopefully, future problemsetters won't repeat my mistakes.)
As a result, most of the problems ended up being mine, at least in their original formulation (with most of their optimal solutions being dario2994's).
However, the more problems I proposed (and the more feedback I received from dario2994, who, during this stage, acted as a coordinator), the better I became at inventing problems: I began to notice when a problem was too mainstream or technical or didn't require any interesting insight; I gradually developed an eye for statements that seemed nice and "natural"; I aimed at the right amount of beauty and originality. I still got rejections, but fewer of them. In the end, I feel that I am now a way better problemsetter than I was in the beginning, and I have to thank dario2994 for that!
The problem preparation phase was another thing entirely. Previously, I had prepared a reasonable amount of problems for the Italian Olympiad in Informatics and the Italian training camps, but in a Codeforces round (and, to a greater extent, in a Global Round) everything must be thought of with the utmost care: there is no room for major mistakes.
- Statements must be clear. As I'm writing this, dario2994 is telling me that the statement of problem A has to be clarified (and it's less than 24 hours before the contest!).
- The generation of tests is by far the most critical part. If you want to avoid heuristics to pass systems tests (or, maybe worse, pass pretests and get FST), tests must be strong.
- In order to test the generator, it is essential to write a lot of heuristic/suboptimal/slow solutions and make sure they fail on a reasonable amount of tests.
- On the other hand, writing the validator and (when needed) the checker is way easier and almost relaxing.
Two problems were discarded after or during their preparation because we found unbeatable heuristics: one was the former problem C, the other was former problem I. Both problems were proposed by me, so I was a bit disappointed when that happened (especially for problem I, which neither dario2994 nor antontrygubO_o could solve). However, we were lucky to find those heuristics and save us from unwanted AC on wrong solutions. Hopefully we have caught them all!
I had a whole lot of fun organizing Global Round 15, and I discovered that I like inventing problems more than solving problems invented by others! For this reason, I think that, sooner or later, I will try to organize another round here on Codeforces (provided that I find the time to do so).
Hints and solutions
For sure, one must permute the $$$k$$$ characters by sorting them alphabetically.
If a character is not among the $$$k$$$ shuffled characters, then it must be already in the correct position.
If a character is not in the correct position, then it must belong to the $$$k$$$ shuffled characters.
The "superiority" relationship induces a complete directed graph with $$$n$$$ vertices and $$$\binom{n}{2}$$$ edges.
There can be at most one athlete who is superior to everyone else.
Morally, the problem is equivalent to finding the maximum of an array (performing not too many comparisons).
Try to optimize the obvious quadratic solution.
Maybe put in some randomization?
If two chords do not intersect, "swapping them" so that they intersect strictly increases the number of intersections.
If we repeat the above-described strategy, we will end up with a configuration where all added chords intersect.
There is only one configuration so that all added chords intersect.
Consider the graph induced by the edges $$$(j, \, k)$$$ so that $$$a_i = b_j - b_k$$$.
Such graph contains $$$n$$$ vertices and $$$n$$$ edges, so it has a cycle.
The sum, with the right signs, of the $$$a_i$$$ over the vertices of a cycle is $$$0$$$.
The above condition is necessary and sufficient.
It is always convenient to choose $$$a_i, \, b_i$$$ so that the color $$$i$$$ does not appear in $$$a_i + 1, \, a_i + 2, \, \dots, \, b_i - 1$$$. So, for each color there are $$$k - 1$$$ "candidate intervals".
$$$(k - 1)\left\lceil \frac{n}{k - 1} \right\rceil \ge n$$$.
Choose the intervals in chunks of $$$\left\lceil \frac{n}{k - 1} \right\rceil$$$. The intervals in the first chunk should be strictly to the left of the intervals in the second chunk, which should be strictly to the left of the intervals of the third chunk, and so on.
For the $$$t$$$-th chunk, only consider (among the remaining colors) the candidate intervals whose left endpoint is the $$$t$$$-th occurrence of its color.
Try to come up with a greedy algorithm.
Order the candidate intervals (defined as above) by second endpoint.
Scan the sorted intervals and always select one if you are allowed to.
If you are at position $$$x$$$, what can you say on the state of portals with $$$x_i < x$$$?
All such portals must be active.
Try to solve the problem under the assumption that initially all portals are active.
You must compute the time necessary to go from $$$x_i$$$ to $$$x_i$$$ again assuming all portals are active.
Testing only arrays with $$$0$$$ and $$$1$$$ is sufficient (why?).
A quantum array is a $$$0$$$-$$$1$$$ array so that some entries can be both $$$0$$$ and $$$1$$$. Start with a completely undetermined quantum array and apply the algorithm, fixing its values only when necessary.
How many quantum arrays will this algorithm have to deal with?
The perimeter is twice the base plus twice the height. Figure out them both!
Ask a query with all points. The result is a simple expression in terms of base and height.
Ask only queries of the form $$$(di, \, j): 1 \le i \le \lfloor \frac{200}{d} \rfloor, \, 1 \le j \le 200$$$. Let the result be $$$f(d)$$$.
For which values of $$$d$$$ is $$$f(d)$$$ nicely related to $$$f(1)$$$?
Binary search on the $$$2$$$-adic evaluation of the number of points on the base of the rectangle.
The valid orderings have a rigid structure.
Let $$$S_i$$$ be the singers liked by friend $$$i$$$. Consider the graph on the friends where there is an edge between $$$i$$$ and $$$j$$$ if and only if $$$S_i \cap S_j \ne \varnothing, \, S_i, \, S_j$$$.
Distinct connected components are independent.
Up to obvious identifications, each connected component has exactly $$$0$$$ or $$$1$$$ or $$$2$$$ valid orderings.
If you find any typo, feel free to tell us with a comment. Moreover, if you want to share your opinion on the problemset, we are eager to read it.
Great problems, but too hard for me :,(
Sad round for me, too. ToT
same here, the ideas behind each problem are brilliant, but.... (I can only solve A :'( )
Solutions and Implementations aren't visible. Kindly fix it. Thanks.
Just read what the editorial says, "As of now, only hints are available"
One of the finest rounds on codeforces. kudos to the problem-setters!
for me UNO reverse :(
Great Problems.
Tooooooooooooooooooo.. Hard. Yet, very interesting.
.
In problem B, won't only the winners(getting best standings) of the 5 marathons be the only potential candidates for the gold medal? Please, someone, help
Consider this case:
1
6
2 2 2 2 2
1 6 6 6 6
6 1 5 5 5
5 5 1 4 4
4 4 4 1 3
3 3 3 3 1
1 is the only one that can get a gold medal, but he didn't win any marathon
Thanks Man
Yeah, I tried to solve similar way, whose rank-sum will be less than will be a potential winner but I got WA.
Just consider the following case:
Number of participants: 5
Marathons and ranks:
M1: 1 2 3 4 5
M2: 1 2 3 4 5
M3: 1 2 3 4 5
M4: 4 2 3 5 1
M5: 3 2 4 5 1
2 has the lowest 'ranksum', still 1 is the winner.
Yeah, but in this case, we simply take a lower index if the sum is equal???
By 'ranksum', you mean the sum of the ranks of the player across the 5 marathons, right?
What I am trying to say is that the concept of 'ranksum' is of absolutely no use in some cases, as the superior athlete might not actually have the lowest ranksum.
In the above example itself, the ranksum of the superior athlete 1 (0 + 0 + 0 + 4 + 4 = 8) will be greater than the ranksum of the athlete 2 (1 + 1 + 1 + 1 + 1 = 5), even though 1 is the superior athlete...
Yeah, now I got your point but I am unable to find any such example. Below is my code it's a little bit hard to understand. Thanks.
Your code is throwing a lot of compilation errors.
You could try attaching a link to your WA solution instead, though I don't feel that it's necessary.
Your code should fail this Test Case (the correct answer here would be 1):
Edit-> defnotmee already answered it above, Thank you
Why do you think your #2 will always pick the right candidate (if there's any) ?
In Problem D, I wrote down some examples and observed 3 ways to get a YES answer (First of all I converted all the negatives elements to positive because since we have been given differences, the sign doesn't matter) :- 1) If there exists a 0 in the array. 2) If there are repetitions in the array. 3) If there exists more than one subset sum in the array. :)
I had the same solution XD The fun part is that I didn't fully understand why would this work but it passed pretests.
But if you look at the formula in the editorial and move all the negative elements onto the right hand side of the equation (either because they were negative in the first place, or because $$$s_i = -1$$$), suddenly we have the formula we came up with: sum of at least two subsets of absolute values must add up to the same value. It is $$$O(2^n)$$$.
I have an $$$O(2^n\cdot n)$$$ solution for D. I don't know why does it work:
Generate all possible subsequences of a and keep their sums in a set. If the length of the set equals to $$$2^n$$$, then the answer is "NO", else the answer is "YES". Don't forget to handle the case when there's a zero in the array!
Great approach but how it works
it is basically same as editorial solution . Let there exist 2 subset A and B which have equal sum then we can take element of A with positive sign and element of B with negative sign so the total sum of subset (A +(-B) ) =0.
Can you give an example how to construct the array b given two subsets are equal? Thanks.
Suppose A[] = {5,3,8} then you can generate an array B[] = {5,8,16}, we can generate this because we have two subsets (1,2) and (3) with equal sums.
Thanks. Can you explain the construction for A[] = {-3, 6, 10, 1, 12, 100} subsets (1,2,3) and (4,5) have same sum (-3 + 6 + 10) = (1 + 12) = 13
I have understood. {0, -3, 3, 13, 1, 100}
The target of this problem is to build an array b that contains n numbers instead of n+1 so that if there are 2 subsets have the same sum S, you can build an array b having n+1 numbers with S appears twice, and you just delete one of it to make an array b have n numbers.
Thanku
Thanks!
you can build an array b have n+1 numbers with S appear twice
Can you explain this line?
We call 2 subsets have sum $$$S$$$ with $$${a[i1], a[i2], ..., a[ik]}$$$ and $$${a[j1], a[j2], ..., a[jr]}$$$ We know that these $$$r+k$$$ elements have distinct index in $$$a$$$ which mean $$$r+k \leq n$$$.
Let build array $$$b$$$ in this way :
$$$b[1]=0$$$
$$$(2<=y<=k)$$$ $$$->$$$ $$$b[u+1]=b[1]+a[i1]+...+a[iu]$$$
$$$(k+1<=u<=k+r)$$$ $$$->$$$ $$$b[k+u+1]=b[1]+a[j1]+...+a[ju]$$$
For any element in other $$$n-(r+k)$$$ elements in $$$a$$$, we can easy set to last $$$n-(r+k)$$$ elements in $$$b$$$. Now we have array $$$b$$$ with $$$n+1$$$ elements and we also have $$$b[k+1]=b[k+r+1]=S$$$. Now just remove $$$b[k+1]$$$ to make array $$$b$$$ with $$$n$$$ elements.
Thanks!
Hey I used the logic that if there is atleast 1 combination of Ai whose sum is equal to the some Aj then we don't have to make a segment for it and it can be done in n Bi otherwise n+1 Bi will be needed but it is giving me NO instead of YES for this test case. 9 25 -171 250 174 152 242 100 -205 -258 Can anyone explain why it is not working? Here is the code for reference
Thanks it helped me a lot
you can forget to handle the case when there's a zero in the array. Because one of the subsets is empty set and the sum of it is equal zero. so if there's any zero in the array , the length of the set(sum) will be less then number of subsets.
I also did problem B in O(nlogn) but i used sorting
if you used the STL sort then I think it is a UB.suppose A,B,C are any structs that you sort,the STL sort only works when if A>B,B>C,then A must be bigger than C,Otherwise the sorted result might be a complete mess.Sorry for the bad grammar.
I used sort with comperator function and also after sorting I iterate over all thing to check weather it holds satisfies condition or not
can u elaborate more??
Did the setters anticipate non-bitmask solutions to G? It seems that even with some careful book-keeping to avoid performing any $$$O(n)$$$ calculations at the critical deepest level of recursion, the time limit is still pretty strict for these solutions.
My contest solution (123766099) keeps the non-recursive part of every loop at $$$O((k+1-i) \cdot (1 + |S_i \setminus T_{i-1}|))$$$ by following the set and un-set bits to their destinations in advance and attains something close to $$$O((\frac{n+k}{k})^k)$$$ performance. (It's technically a bit worse for large $$$k$$$, but that's not very relevant to this problem.)
It is possible, albeit requires some optimization (or, for example, the second observation described at the end of the editorial), to get accepted without using bitmasks.
While preparing the problem, I wondered if it was better to give the problem with $$$n=50$$$ (which obliged to use bitmasks) or $$$n=40$$$ which allows many more solutions to get accepted. At the end I decided to go for the "low-constraints" version since the gap between F and G was already rather big.
I don't think the second observation by itself would have been enough for my own implementation, since the ratio $$$5^{10} : 6^4 \cdot 5^5 \approx 2.4$$$ it seems to actually save isn't very big, and my own idea (which I estimated saves a factor of about $$$40/5 = 8$$$) didn't yield so much headroom. I should look over the other slow solutions and try to see what ideas they used.
It's also very possible that my implementation is just rather slow. But if non-bitset solutions were intended to pass, it seems perhaps a bit strange to keep the time limit at one second.
I did problem B using a comparator function 123741857
Hey, I also used a similar approach(123769494), but I'm not sure how is this working because,
If A is superior to B and B is superior to C, then it is not always true that A is superior to C(like in the given test case). This would probably give the wrong sorted order, right?
Can you please explain why is it working?
Suppose A,B,C,D is the order you get after sorting. Then, D cannot be the answer as C is superior to it, similarly C cannot be the answer due to B, B cannot be due to A. So if any answer at all exist it has to be A.
Thanks a lot!! Got it
Typo: The latex in hint 3 for H is currently broken
Thanks, it has been fixed!
Is it only me or the "Hint 3" in problem H is bugged?
It's fixed now. :)
I have another way to do in problem D. First, if there is some zero in the given set, the answer is YES. Otherwise, consider the absolute values
|a1|, |a2|, ..., |an|
and check whether there are two distinct subsets of the new set s.t their sum are equal. This can be done inO(n.2^n)
.deleted
why is true ?? I cant figure it out ??
How is it supposed to solve D in $$$O(3^n)$$$? Is it a typo, while the actual complexity is $$$O(3^n\cdot n)$$$?
You are right! It has been corrected in the tutorial, but it might take some time to render in the blog.
I solved it in O(3^N). Precompute the sums in O(2^N) or O(2^N*N) then iterate through the pairs of non-intersecting subsets.
I used that approach too (123745577)
Hello authors,
Thanks for the great contest, all the problems I read were interesting and entertaining to solve and think about.
However, one decision I am confused about is the omission of a max pretest for D. There was no pretest that had 20 test cases of n = 10, and this lead to people FSTing. My solution ran in less than 200 ms on pretests, and so even though I was suspicious of my complexity, I figured that my solution for D was okay, yet it still FSTed.
Next time, please include max tests in the pretests so contestants can be rather certain their solution will pass under the time limit.
What does FSTed mean?
Failing system tests
Sadly, I got FSTed for D. Interesting problems btw. Kudos!
Edit: Can anyone explain why I got TLE for D while the time complexity seems to be n * O(2 ^ n)? 123771731
rep(i, 0, elements.size()) { rep(j, i+1, elements.size()) { if(abs(elements[i] - elements[j]) == curr) { return rec(arr, idx+1, elements); } } }
Just because of this loop your complexity is already at least O(n^2*2^n). There are also 20 test cases. That already puts you at O(10^8). Add any major inneficiency and it's time limit (like what happened).
For that solution you could just store everything on a set end check in the end if the size of it is equal to 2^n, you really didn't need to make your life hard. Also cout.tie(0) litterally does nothing
1552C - Maximize the Intersections I still completly do not get why we can ignore the initial chords configuration. The editorials seems to not explain it further. Is that something so obvious?
It's not obvious, but the idea is that you can consider a pair of new chords separately from any pre-existing chords. Let's say there are multiple chords already drawn, and you now have 4 free points ($$$A,B,C,D$$$ in that order), and you must draw two chords. You can convince yourself that the configuration $$$AB$$$ + $$$CD$$$ intersect the same number (or fewer) previously drawn chords as the configuration $$$AC$$$ + $$$BD$$$, but since $$$AC$$$ and $$$BD$$$ intersect themselves, this configuration is better.
I hope that it's somewhat clear. It's the usual swapping argument employed in proofs of greedy solutions.
As there is only one configuration that is giving the maximum we can ignore initial chords. If that is not the case then we can't ignore the initial chords.
"Problems A and B are meant to be easy!" Really?
I had a different approach for problem F:
First of all, compress all coordinates so each of them is not greater than $$$2n$$$. The solution below uses 1-indexation for compressed coordinates. The original coordinates are kept in array c.
Then do some kind of right-to-left dp, let's call it over.
over[i]
means the number of times the ant goes from pointi - 1
to pointi
. Then the answer is clearly $$$\left(\sum_{i = 1}^{2n}over[i] \cdot (c[i] - c[i - 1])\right) + 1$$$.The point is how to calculate the over dp. There are two cases:
over[i] = over[i + 1] - cnt
where cnt is the number of telepantings through the portal p. It can be easily found asover[p.x] - over[p.x + 1]
.over[i] = 2 * over[i + 1] +- 1
(+-1 depends on the initial activity of the portal).You can read the code here (123756889) or
I think I have done problem B in more simple way. All I did is 2-d vector sorting using my own compare function.
Compare function code:
Only first athlete in sorted vector will be contestant to be superior. Just have to check that.
D can be solved in O(2^n). It's sufficient to check if two subsets have the same sum.
Can you explain how does this works?
Shouldn't they need to ne non intersecting as well? For ex-: If we have a1+a2-a3-a4+a5-a6=0 => a1+a2+a5=a3+a4. I think that's why you are telling that the two subsets should have the same sum. But, then won't they also need to be non-intersecting?
What do you mean by non-intersecting?
Two sets having no element in common. Like {a1,a2} and {a3,a4} are non-intersecting but {a1,a2} and{a2,a5} are intersecting.
Okay, then we don't need to check if they are non-intersecting. Take the example, {a1,a2} and {a2,a5} which are two intersecting subsets which have same sum. a2 is common. so we can find {a1}, {a5} which are two non-intersecting subsets which have same sum. It is same for each intersecting subsets. I hope you understood :D
Thanks ! Learnt a new thing!
2 problem is similar to find the celebrity problem which can be done using recursion https://www.geeksforgeeks.org/the-celebrity-problem/
Alternative solution to 1552F - Telepanting
Let $$$z_i$$$ be the index of the teleporter reached immediately after using the teleporter $$$i$$$ (it can be calculated by binary search).
Let $$$dp_{i,0}$$$ be the number of times $$$x_i$$$ is reached. Let $$$dp_{i,1}$$$ be the number of times the teleporter $$$i$$$ is used. Then, the answer is easy to calculate (you spend $$$x_{z_i}-y_i$$$ time for each teleporter, and if the teleporter is inactive you spend $$$x_{i-1}-x_i$$$ time).
You can calculate $$$dp_i$$$ in decreasing order of $$$i$$$ by obtaining it from the recurrences
$$$\displaystyle dp_{i+1,0} = \sum_{z_j=i+1}{dp_{j,1}} + \lfloor \frac{dp_{i,0} + (s_i \oplus 1)}{2} \rfloor$$$
$$$\displaystyle dp_{i,1} = \lfloor \frac{dp_{i,0}}{2} \rfloor$$$
As there could be multiple possible values of $$$dp_{i,0}$$$, you have to choose the one with the same parity as $$$s_i \oplus 1$$$ (because all the teleporters are active at the end). This can be done by using mod $$$1996488706 = 2 \cdot 998244353$$$.
Submission: 123775629
Nice solution! If I had to guess, I would have said it is impossible to solve this problem without the observation that all portals with $$$x_i < x$$$ are active when the ant is located at $$$x$$$, but it looks like your solution doesn't require this (only that all portals are active in the end). Thanks for sharing.
I'll try to include it in the editorial, provided that the gods of Polygon are in my favor.
Edit: Solution added to the editorial (actually explained in a slightly different manner, but hopefully correct).
One of the best tutorial sections of all time! Though I got demoted to pupil :(, still a nice contest! @cip999
Magnificent editorial! I wish all editorials would be at least as detailed as this!
I really liked the contest, since it had a lot of interesting and fun problems.
For me personally it was a bit sad, that my "solutions" A, B, C & D all passed the pretest without any problems, but later my solution for D failed with a TLE although it only took me ~300 ms to pass the pretests.
Since I am new to codeforces, I would like to ask if this is the standard (you are responsible for your own code, so you have to calculate the complexity) or if you normally should be rather safe with a ~300 ms.
Great contest! Looking forward to more :)
Thank you for the contest!
bad pretest for B:,(
I think so :(
Finally I became an International Master after this Round.Thanks to cip999 and dario2994 :)
I can come up with a solution to problem B, which is referred to as 3rd Solution.
I define a comparison between athlete $$$i$$$ and athlete $$$j$$$, athlete $$$j$$$ is called "greater" than athlete $$$i$$$ if and only if athlete $$$i$$$ is superior to athlete $$$j$$$. After sorting the athletes by this compare, each of them, except the first one, will have at least one athlete that come up before and superior to them.
Finally, we check whether the first athlete is superior to everyone else or not.
Implement: https://codeforces.net/contest/1552/submission/123730552
This solution is broken, because it relies on undefined behaviour. The input data and the comparator do not satisfy the transitivity requirement. If A < B and B < C, then A < C must be also true. This kind of violation is similar to relying on a wrong use of <= operator in a comparator (which is known a bit better to the general public).
Now I'm not sure if it's really possible to hack your solution in practice. Some implementations of sort could theoretically go into an infinite loop and give you a TLE. The others could crash. Using various combinations of search keywords "transitivity", "sort" "crash", "segfault", "infinite loop" on google shows that bad outcomes happened to be a reality at least in some cases.
Just consider yourself lucky and don't do it again. An unintended bad thing about problem B from this contest is that it rewards incorrect code with a positive stimulus.
I solved the D problem with a approach different from the editorial . Have a look at it. I find it interesting. 123742321
The problem C is very very difficult.
Can someone who solved E during Contest explain what went through their mind while solving it? Did you prove the solution u coded ? And what's the first thing came to your mind when u looked at weird ceil(n/(k-1)) constraint?
What came to my mind was that there might be a way to split colors into groups of $$$k - 1$$$ such that the intervals in each group do not intersect with each other.
I tried basic strategy on samples + few handwritten tests, and it gave correct answers. I tried to prove but without hope. There was nothing to do. So I've just implemented it. It passed pretests, so even though if it was wrong solution, I didn't care. So if FST would happen I would just "well, shit happens". Ah... it was second solution from editorial.
If there is more than such one athlete, print any of them. Can Someone told me important of this line in Problem B.
I think they just didn't want to make the observation that there is always at most 1 athlete obvious
It's normal question from participant: what if several athletes might be answer, which one output? To avoid giving key hint that it's always unique, this statement is included.
Also, there is often statement "Output -1 if there is no solution" in problems that always have solution.
Anyone else try doing B with bitmasks?
Can anyone please tell me why I am getting a TLE in my solution of problem B?? 123801888
Your Solution is correct Just pass your 2D vector to check function by reference and it will get pass ! bool check(vector<vector> &m,int j,int k)
like this !
Thanks bro, Yeah it got AC but can you explain why it was getting TLE??
By default the arguments are passed by copy. Every time you call that function, the vector must be copied. But you don't need that, you pass it by reference so it won't be copied, it will use the original vector
Federico in B made me think about Federico Chiesa. LOL :)). Anybody have the same imagination?
I think I have an interesting and easy-to-understand solution for B.
Here's the idea:
Keep a knockout style tournament
Each player will play 2 other players ( n-1, and n+1)
Only those players who have won both their matches will advance to the next round
Eventually, only one person will remain. (Possible winner)
To check if he's the actual winner, see if he's superior to all other players.
Example:
Code: https://codeforces.net/contest/1552/submission/123742601
Complexity: O(n*logn)
What are your thoughts?
tourist is Lionel Messi of cp. GOAT.
Can anybody share the O(nlogn) algorithm mentioned in problem C solution?(=-=)
Submission Let's have two ranges [a,b] and [c,d] such that a<c. Now both ranges will intersect iff c<b<d. I used ordered_set to count the no of such endpoints for a range. Since I added the endpoints in increasing order of starting points, all such endpoints will be valid.
nu cuoi da tat vi mim qua dak
Best Editorial I have seen ever, thanks
I've seen some solutions for E that do not seem to explicitly check for the ceil(n/(k-1)) constraint and greedily make "n" passes over the array and on each pass tries to pick disjoint intervals whenever it can. (Here's a sample submission that does this).
Does anyone have a proof that this won't violate the ceil(n/(k-1)) constraint ?
O(N log N) solution for problem C:
I used indexed set but could also be done using segment tree.
Seems like sansen is hacking everyone's G and most of them are failing with TLE, does that mean the system tests were weak? Sorry if I'm getting this wrong
reference:
https://codeforces.net/contest/1552/hacks?verdictName=CHALLENGE_SUCCESSFUL&chosenProblemIndex=G
https://i.ibb.co/YPDkbV9/hacks-1.png
Actually I am curious about that. I had worked pretty hard to make the tests decent (both to fight against randomized solutions and to fight against slow solutions), but I must have failed if $$$\ge 10$$$ solutions out of 50 are hacked. Please sansen explain your trick.
Most of the hacked submissions are dp-like solution. The complexity is the same as Editorial, but it uses a lot of memory and has a large constant factor. However, in the prepared testcase, there were a lot of state collisions, so it was very fast.
problem E,why can construct it? I don't understand.who can help me?
What didnot u understand? I can try to explain it to u.
can you speak Chinese? ,my English is not good,but I accept English, my question is why can prove two intervals selected in different steps are disjoint,programme is understanded for me,but why?
Xi,s+1<Xj,s+1, because x was sorted and if Xi,s+1>Xj,s+1 we have took j first ans then i. Xj,s+1 <= Xj,t because s<t
P.S. Sorry for my English...
In problem E [n / (k-1)] can be 0, if k — 1 > n. In this case there is no answer, but "One can show that such a family of intervals always exists under the given constraints." Help me, please.
got it
Interesting observation in Problem E I haven't seen mentioned yet. One can look at the special case $$$n=k-1$$$. Then we have the case, that each number belongs to at most $$$1$$$ interval. We can solve this and use the solution to solve the general case.
In the general case we have $$$n$$$ and $$$k$$$ and at most $$$\left\lceil \frac{n}{k-1} \right\rceil$$$ intervals. Then we can split up the $$$n$$$ numbers arbitrary into $$$\left\lceil \frac{n}{k-1} \right\rceil$$$ separate groups with each containing no more than $$$k-1$$$ numbers, and solve each group separately. (I guess, this is the meaning behind hint 1.2)
This isn't the best way to implement the solution, but this train of thought really helped me to come up with a solution.
Can someone explain this part of greedy solution for problem E:
I agree that interval $$$[x_{i,j}, x_{i,j+1}]$$$ would come before $$$[a, b]$$$ in this case. But we might not select it based on requirement #2. Am I missing something?
The contradiction is exactly what happens if we don't choose any segments because of requirement #2.
For each of the k-1 segments we could choose there was already (n)/(k-1) segments that had their right endpoints inside of [xij,xij+1] (otherwise, it would come before in the ordering and be choosen instead).
That way there should be (n)/(k-1)*(k-1) distinct segments, or n segments for n-1 colors, leading to a contradiction.
He was asking why $$$[x_{i,j}, x_{i,j+1}]$$$ must have been selected if it comes before $$$[a, b]$$$.
And i was answering that. Funnily enough i think we both said the same thing with different words
My bad. I didn't fully understand your comment so I wrote my own. Just reread yours and it's much clearer now.
Took me an hour to understand the explanation :D I finally did!
Thank you!
I think the author meant we can always find $$$\left\lceil \frac{n}{k - 1} \right\rceil$$$ intervals with their right endpoints inside $$$[x_{i,j}, x_{i,j+1}]$$$. If it were not the case, at the time we considered $$$[x_{i,j}, x_{i,j+1}]$$$, we would have selected it.
Now for each of the $$$k-1$$$ intervals for color $$$i$$$, we have $$$\left\lceil \frac{n}{k - 1} \right\rceil$$$ distinct intervals. In total, we have $$$(k - 1)\left\lceil \frac{n}{k - 1} \right\rceil \ge n$$$ distinct intervals, leading to a contradiction since we can not have $$$n$$$ intervals for $$$n-1$$$ colors.
in problem B, any two pairs, one must be superior to the other, right?
Correct
however you choose 3 chords that connect 3 disjoint pairs of points, no point strictly inside the circle belongs to all 3 chords.
what does this means?That means if you choose any 3 chords, they won't intersect in a single point (like this: "Ж")
even if they intersect at a single point, i think the number of intersection remains the same
Especially problem D was great.
Can someone tell me the $$$O(3^{n/2})$$$ meet-in-middle solution for D?
we want to check if there is some mask with sum == 0, we can split the array in two and for every mask in the first half with sum = x, we check if we can make sum = -x with the second half. of course if we can make sum = 0 using the first half only or the second half only we are done. you can check my code 124122316
You have nice problem ideas. You have good English skills. You are devoted to the thing you do. Although I just do the virtual contest (and solved only A), I can say: "Nice problemset!" Thank you very much, sir!
What does the anti-random case look like on problem G?
Here is how to construct an anti-random case.
Choose "reasonably" the first $$$k-1$$$ sets $$$S_1, S_2, \dots, S_{k-1}$$$ (reasonably $$$=$$$ each element belongs to at least one such set, they are not sufficient to sort); then execute the solution for this family. You will get a family of $$$(k-1)$$$-achievable functions.
As in problem A of the contest, for each of them you identify the minimal subsequence that needs to be sorted and you compute the union of these sets. This yields a set $$$Z$$$. Notice that for the family $$$S_1,S_2,\dots, S_{k-1}, Z$$$ the answer would be ACCEPTED.
Now, you remove from $$$Z$$$ the element $$$z\in Z$$$ which minimizes the number of $$$(k-1)$$$-achievable functions whose "minimal subsequence that needs to be sorted" contains $$$z$$$. Notice that for the family $$$S_1,S_2,\dots, S_{k-1},Z\setminus{z}$$$ the answer would be REJECTED.
Now you execute your favourite random solution (the most efficient one seems to be the one which simply tries random permutations). If, after $$$2$$$ seconds of computation it cannot find any permutation which is not sorted by $$$S_1,S_2,\dots, S_{k-1},Z\setminus{z}$$$ then you have found your anti-random case. Otherwise, you start again.
Why is the Task I a recurrence of 243E - Matrix? What a shame.
The solution to I contains a bug.
This doesn't necessarily hold. For example, if $$$(Z_1, \ldots, Z_3) = (\{1\}, \{2\}, \{3\})$$$ and $$$S = \{1, 3\}$$$, we have $$$I = \emptyset$$$.
This is not a critical one though. One can easily extend the solution's idea to the case of $$$I = \emptyset$$$ (and it's done in my submission: https://codeforces.net/contest/1552/submission/124438016)
Thank you for spotting the mistake in the editorial. Fixed.
My solution for H isn't based on any proof, only on the expectation that a lot of queried sets will give different answers for different shapes. I don't believe there's a single test where this doesn't hold.
Naturally, I start with finding $$$ab$$$, where $$$a$$$ and $$$b$$$ are the number of rows and number of columns of points belonging to the rectangle (why bother with writing $$$+1$$$). I find all candidate pairs $$$(a,b)$$$; quick testing shows there's at most $$$26$$$ of them, so we only need each query to select up to 1/3 of current candidates to succeed.
Let's pick a set where possible answers for each $$$(a,b)$$$ are simple to find. I go for some integers $$$d_a$$$ and $$$d_b$$$ and points $$$(x,y)$$$ where $$$d_a | x-1$$$ or $$$d_b | y-1$$$: rows with spacing $$$d_a$$$ and columns with spacing $$$d_b$$$. A rectangle with $$$(a,b)$$$ will cover $$$\left\lfloor \frac{a}{d_a} \right\rfloor \le k \le \left\lceil \frac{a}{d_a} \right\rceil$$$ of the selected rows and $$$\left\lfloor \frac{b}{d_b} \right\rfloor \le l \le \left\lceil \frac{b}{d_b} \right\rceil$$$ of the selected columns. That's up to $$$4$$$ answers, each is $$$bk+al-kl$$$.
For each query, I try all possible $$$d_a$$$ and $$$d_b$$$, since there are just $$$40,000$$$ of them. For each of them, I find all possible answers for each remaining candidate $$$(a,b)$$$, then find the answer that corresponds to the largest number of candidates. I pick $$$(d_a,d_b)$$$ which minimises this maximum, ensuring that the number of candidates remaining after the query is small even in the worst case. I ask the query and filter candidates that can give the answer returned by the judge. It works!
Very nice solution!
Very nice problems!
Another way to think of it is to find two disjoint subsets with the same sum, which has complexity $$$ O(n*2^{2n}) $$$ or $$$ O(n*4^n) $$$ and passes in the time.
Can anyone explain what this method is and why it is working on traversing all 3^n states?
Best editorial i had ever seen on codeforces. All soutions are explained very clearly and efficiently. UPVOTED.... I wish every editorial on cf would be like this.
Can someone explain the solution to my problem E? I just greedily choose the interval with the leftmost right endpoint (an interval refers to two adjacent points with the same color), and then choose it n/(k-1) times. Once a color is chosen, it is not chosen again. It's weird that I passed the problem.211917556
Graph solution to D is over complicated.
How to solve the bonus for C?