Hello everyone,
At May 19 there was an annual programming contest in Samara University, and yet again we copy it into Codeforces Gyms. The gym contest takes place on Saturday, May 25, at 10:00 MSK.
Contest link
Virtual participation link
Fourth time in a row it is a personal contest. So we ask everyone to participate solo. The contest is the most interesting for blue and violet coders.
The list of our previous contests
A merchant in Baghdad sends his servant to the marketplace for provisions. Soon afterwards, the servant comes home white and trembling and tells him that in the marketplace, he was jostled by a woman, whom he recognized as Death, who made a threatening gesture. Borrowing the merchant’s horse, he flees at great speed to Samarra, a distance of about 75 miles (125 km), where he believes Death will not find him. The merchant then goes to the marketplace and finds Death, and asks why she made the threatening gesture to his servant. She replies, “That was not a threatening gesture, it was only a start of surprise. I was astonished to see him in Baghdad, for I have an appointment with him tonight in Samarra.”
I felt like problem D is the hardest, so I was very surprised that relatively many people solved it. How to solve this?
Take the LCA of all blue nodes (bLca) and the LCA of all red nodes (rLca). Now iterate over every blue node b and if rLca is on the path from b -> bLca, then you can say for sure that you can't disconnect the blue and red nodes (since b has to cross over rLca and every red node also has to cross over rLca).
Do the same logic for every red node (check if bLca is on the path from r -> rLca) and if that occurs for any blue or red node, the answer is no, otherwise yes.
Here's what I did:
Find the lca of the red set (say, u) and the lca of the blue set (say, v). Note that all red nodes are in the subtree of u, and all blue nodes are in subtree of v.
If u = v, obviously it's not possible.
If u is ancestor of v, then check whether v is ancestor of any red node. If yes there's a problem, if not it is possible.
Similar case for v being ancestor of u.
If none of the above (so lca(u, v) != u or v) then it's possible.
How did you solve G?
G seems to be a DP problem.
Sort the initial array and Take the DP states to be dp(l,r,depth) and try breaking the state at all i between l to r.
taking min of all dp(l,i,depth+1) + dp(i,r,depth+1) should works.
I have not coded this solution but i think its correct.
After getting u and v.
For u, I am checking Is there any blue node in subtree of u by using IN-OUT time array ( I mean IN[u]<=IN[node] && IN[node]<=OUT[u]) If yes, then I will set flag for this case.
Similarly for v.
If both flags are set then answer is NO, else answer is YES.
Is there any wrong in doing this ? Beacuse I am getting WA on tese case 3.
Nothing wrong.
Could you please provide test case 3 ?
No. Find your mistakes by yourself. It is a useful skill on programming contests.
How to solve problem I?Just get wa on test 11.
You move in a spiral path!
In each move initially you keep painting new b squares. So initial uncoloured= a*a-b*b.
Also finally you will be left with a a%b*a%b square in middle while in spiral.
so in first type of move... (a*a-b*b-(a%b*a%b)) cells are covered with b per move.
Then you can cover the middle of the spiral in a%b moves,
Move in a spiral inwards, instead of zig-zagging down.
A small case where zig-zagging fails is
5 2
— you get 12 while the actual answer is 11.To (kinda) see why spiralling works, look at it this way — in each move, try to maximize the number of new squares you colour. For a while this will be
b
with both methods, of course, but when you spiral it reduces fromb
only when you reach the absolute center, whereas when zig-zagging you hit this for the entire last row.Not exactly a proof, just some intuition of why it might work.
How to solve G?
Problem G is actually not difficultest.
We can think about binary tree that each question divides into two sets (left child = "yes" person, right child = "no" person).
Let $$$d_1, d_2, d_3, ..., d_n$$$, the depth of binary tree with $$$n$$$ leaves. Here, we should minimize $$$a_1 d_1 + a_2 d_2 + ... + a_n d_n$$$. If the minimum value is $$$Z$$$, then the answer will be $$$\frac{Z}{a_1 + a_2 + ... + a_n}$$$.
Assuming $$$a_1 \geq a_2 \geq ... \geq a_n$$$, the optimal answer will hold $$$d_1 \leq d_2 \leq ... \leq d_n$$$. Then, we can say that node of person $$$l, l+1, ..., r$$$ will divide into $$$l, l+1, ..., k-1$$$ and $$$k, k+1, ..., r$$$.
This observation will turn to simple DP problem, where recording $$$dp(l, r, d)$$$ the minimum sumproduct of node $$$l, l+1,..., r$$$ and current depth is $$$d$$$. The time complexity will be $$$O(n^4)$$$ and it passed.
Also, if we think little more, we can erase $$$d$$$ from dimension in DP and the time complexity will be $$$O(n^3)$$$.(Sorry, this $$$O(n^3)$$$ solution was false...)P.S. Similar to Optimal Binary Search Tree Problem, this problem can be solved by $$$O(n^3)$$$ with Monge DP speed-up.
You can do $$$O(n^3)$$$ with Knuth optimization:
Let's $$$opt[l][r][d] = k$$$ is optimal index where we should divide $$$[l..r]$$$:
$$$dp[l][r][d] = f(dp[l][k][d + 1], dp[k][r][d + 1])$$$.
You can see that $$$opt[l-1][r] \le opt[l][r][d] \le opt[l][r+1][d]$$$.
So for fixed $$$l$$$ and $$$d$$$ we could calculate all $$$dp[l][r][d]$$$ in $$$O(n)$$$ with two pointers technique.
Yeah, that's what I meant by "Monge DP speed-up".
By the way, this problem is Huffman Tree Problem when $$$depthlimit = \infty$$$, and it can be solved by $$$O(n \log n)$$$ in this case. So, in my intuition, we can speed-up faster than $$$O(n^3)$$$ in general case, but I did not come up with it yet...
You say we sort an input array. Higher probability — lower depth. It's fine. But how does that imply we must divide any segment [L,R] to two segments [L,M] and [M+1,R] somewhere in the middle? Why can't any other division be better?
Okay, so, let me explain. Let $$$d_i$$$ the depth of leaf $$$i$$$, and let's assume $$$d_1 \leq d_2 \leq d_3 \leq ... \leq d_n$$$.
Note that $$$2^{-d_1} + 2^{-d_2} + 2^{-d_3} + \cdots + 2^{-d_n} = 1$$$ is the necessary/sufficient condition to be a binary tree. Let $$$d_1, d_2, d_3, ..., d_k$$$ already decided, and let $$$R = 1 - 2^{-d_1} - 2^{-d_2} - 2^{-d_3} - \cdots - 2^{-d_k}$$$. Here, since $$$d$$$ is an integer sequence which is non-decreasing, we can say that all $$$1-2^{-d_k}, 1-2\times 2^{-d_k}, 1-3\times 2^{-d_k},..., 1-R$$$ will appear in $$$s_l = d_1 + d_2 + \cdots + d_l$$$ for some $$$l$$$.
That's why it is enough to split $$$[L, R)$$$, into $$$[L, M)$$$ and $$$[M, R)$$$, as long as $$$a_1, a_2, a_3, ..., a_n$$$ is sorted.
Problem G can be solved in $$$O(n k)$$$ with Optimal Length-Limited Huffman codes. My submission, ideone
dmkz used not the best implementation of the algorithm.
Of course I have better 54980849.
Is there an article where I can get familiar with that approach?
I readed first article from searching in google by «Optimal Lenght-Limited Huffman codes». Huffman codes were developed for minimizing $$$\sum_{\text{letter}} \text{frequency}[\text{letter}] \cdot \text{codelength}[\text{letter}]$$$ so these codes solves problem by definition.
Thanks :)
Will be there be an editorial put up?
No. Better ask your questions here. Someone will answer.
How to Solve E?Getting wrong on TC 13.
I am pretty confident that I solved problem E with different way to other people.
Let's think about directed weighted graph $$$G$$$ with $$$m+1$$$ vertices, where vertices numbered $$$0, 1, 2, ..., m$$$. We will add edges as follows:
Then, we only have to search the shortest path from vertex $$$0$$$ to $$$m$$$. We can do with 0-1 BFS in $$$O(n + m)$$$ time.
However, the constraints says $$$m \leq 10^9$$$. So, we will get Runtime Error (or Time Limit Exceeded) on Test 13. We can solve this issue by doing coordinate compression, and $$$m$$$ will be at most $$$2n+2$$$. The bottleneck of time complexity is the time of coordinate compression, so this problem can be solved by $$$O(n \log n)$$$ or $$$O(n \times \lceil \log_n m\rceil)$$$ with radix sort.
I think this is the simplest solution:
It's pretty clear that the greedy strategy works. Say the lowest id function you need is id x. Consider all intervals that contain x. Of those, include the interval which ends latest.
To implement this efficiently, sort the intervals by their start time. Now process all intervals which contain the next program you need and choose the one that ends latest. You need just a few integers for state: the current interval you're considering, and the next program you need. This runs quickly, just a sort in O(nlogn) and a linear scan.
Can you explain a bit more on how to consider all intervals that contain x?
Sure. As I said in my answer, process all intervals in order of their start. An interval is a candidate if its left bound is <= x. Of all candidate intervals, take the one with the maximum right bound. Keep a pointer in the list of sorted intervals to know where to pick up for the next x. Maybe my code will be more clear? https://pastebin.com/N1PHuedG
Thanks! I actually had problems maintaining the pointer to know where to pick up for the next x in sample test case 2. After choosing the first interval, next x became 6. Now 6 lies in second interval but not in the third interval. But now I am thinking that we can actually ignore those types of intervals because they won't contribute to the answer anyways.
Can anybody explain why the sample case 2 of problem G's answer is 2/1? Thank you
You have to guess one of 4 people in 2 questions in worst case. You must ask the first question about any two people. With any other strategy, there could be a situation when 2 questions are not enough.
What's the mathematical proof behind C, I see everyone just looping until min(n, p (sometimes 2*p or 4*p) )?
Also can someone give a hint for problem L?
In C, note that every number we mark is of the form $$$0+1+2+...+i = i(i+1)/2$$$, modulo p.
If you substitute i = 2p, this is 0 (modulo p), and then the pattern just repeats because 2p+1 is 1 mod p, 2p+2 is 2 mod p, ... so you won't mark anything new from there.
L is just geometry — since the circles are guaranteed to have exactly 2 points of intersection, the region of intersection is going to look something like a lens (bloated towards one side, maybe, depending on the radii). The point you want is the midpoint of the line joining the top and bottom of this 'lens', and the radius is the distance of this point from either circle (note that any point on this line will be equidistant from both circles)
nishank.suresh do you mean the line that is between the two centers?
The midpoint will lie on that line, yes, but it will not (necessarily) be the midpoint of that line as well.
https://codeforces.me/gym/102215/submission/54724829 that is what i did here but i got a wrong do you know why?
i simply got the four intersection points with the two circles and got the middle two.
You don't need to find any intersection points.
If A and B are the centers of the given circles, then the center of the resulting circle lies on the line AB.
Why? Because of symmetry.
Let O be the center of the resulting circle, and C and D — the points where the resulting circle touches given circles.
Then OC == OD.
btw, cool link: https://csacademy.com/app/geometry_widget/
but we will have to find C and D which result from the intersection of the circles and the line between the centers.
No.
You just need to find the ratio AO / AB and divide AB according to this ratio.
and then we can scale any center by that distance to get C?
another thing i want to see test case 7 (the one that gets WA) do you know how?
=======================
Man, after these 3 hints it become trivial. Get your pen and paper and find what you need.
If you don't know how to divide a segment with a given proportion, read about it.
Test 7 contains some zeroes, I think you divide by zero.
thank you
dalex.can you send test case 7?
Why did I get TLE on test 4? Can someone explain? https://ideone.com/hJpngs
Change unordered_set to vector/array of 1e7 elements.
Thanks, got it AC now, but can you explain why unordered_set would not work in this case?
It is slow. 1e7 is too much.
How to solve problem K? Does a greedy solution work?
You can iterate over all possible permutations of result (RGB, RBG, GRB and others).
For each permutations next greedy approach works:
color 1 to the first deck;
color 3 to the second deck;
color 2 to the second deck, if there is only color 2; otherwise to the first deck.
After all cards were processed, you need check that the first deck is consistent (it should be exactly 1...12...2).
I thought K is top2 or top3 easy problem (along with I), but all participants started chasing yellow guys who solved problems in more or less alphabetical order. I think they just didn't read problems in the end till 2nd hour.
I am getting WA on TC13 after applying above logic.Can you please check what is the error? https://codeforces.me/group/Qgjrcj82Pm/contest/102215/submission/58248865
Where is
do ... while next_permutation
?Sorry I had understood it in a wrong way earlier.Now I got AC. Thanks :). But I wanted to ask instead of trying all permutations of "BGR" if I check for only the permutation in which B,G,R are in order of their occurrence in given string Will I be able to get the correct solution?
can some one help me in problem F
https://codeforces.me/gym/102215/submission/54701762
3
3 5
1 6
3 3
Ahmad thank you Accepted :D
How to solve the Problem J? Thanks.
You can represent every Jedi with the sum of it's three parameter to use the dark force
Then you should represent it again with the sum of the two smallest parameter.
Then sort the second representation and for every one in the first array do a binary search on the second array for the number of elements that smaller than it by 2 (to be strictly greater in two parameters ), there only one check that if the sum of Jedi is greater than it's min 2 parameters by 2 then you must subtract one from the binary search result.
Thanks for your solution.
I just now realized the real problem description instead Jedi only can use once dark force.
How to solve F and H?
In H you can just ask for every bit and generate the number. firstly, ask for the first bit in all the elements and count the number of Integers from 0->n that have one in this bit and you can simply know the bit of the required number and the elements that have the same bit then count again number of ones in the next bit and also have the same previous bits like the required one by this way you can know every bit in half questions from the previous one .
Thanks for your help.
I think problem H is just like Power Arrangers from GCJ Round 1C.
Problem H is taken from the old edition of the Cormen's book (the name Thomas was not just a random name!). Interestingly, this problem was removed from newer editions.
In F you can sort the input twice (two different arrays) the first time by the attack the second is by hit point in increasing order and for every one in the first array you see from the second one the elements that have hit points less than or equal to it's attack point and keep track of the largest two attack points from the second array and you sure you can attack it and then you must check if it can attack you There only one case so you track two integers is that if you can attack yourself so if the largest attack point is like yours so you take the second Integer (both Integers can be the same).
Can Yo please tell me the solution for problem M?? It's okay if you just show me a code Thank you for this great contest