Hi everyone!
Tomorrow, on the April 29, 2018, at 13:05 UTC we are holding the third round of VK Cup 2018 championship. This is the final online round, the next round is the final round in which top 20 teams from this round advance.
At the same time with the official round, we are holding parallel rounds for both divisions. Join them and see if you can beat top Russian-speaking teams! Top50 in the "Div1 Edition" contest will get t-shirts.
All rounds are rated, their duration is 2.5 hours.
The authors of the problems are Zlobober, Endagorion and me. Thanks qwerty787788 and vintage_Vlad_Makeev for their great help in round preparation!
Good luck!
Congratulations to winners!
- V--o_o--V, LHiC — solved all problems, two problems ahead the runner-up!
- craborac, demon1999
- el_sanchez, SpyCheese
- Melnik, hloya_ygrt
- egor_bb, Nikitosh
Mirror for the first division:
Mirror for the second division:
The editorial is here, thanks all for participation!
Parallel rounds, yeah! Hope translation of this round would be better.
Oh, 3 Consecutive Div-2 Rated contest in three consecutive days,
Its really amazing.
Hope problem statements are clear and concise as the announcement!
That happiness you get when you are going through your boring and monotonous life but you notice that codeforces added a new contest!
Today I was running in the forest, did pull-ups on the tree branches, drank spring water from my hands, watched squirrel removing shell from a nut... but I had been interrupted by an alarm on my phone which reminded me of the contest =)
Happiness is having codeforces round in 3 consecutive days. :D
Thanks a lot to the Codeforces team and the authors. :D
registration of Educational Codeforces Round 43 can be closed till the system testing of this round ?!
because anyone will become Div.1 in this round, the Educational Round will be rated to him as a Div.2 participantes (it's already done before)
They can move div 1 contestant from div 2 registration to div 1 manually. "it's already done before" too.
CodeJam and Codeforces round in the same day. This will be challenging :D
100000th contest!!!
http://codeforces.net/contests/100000
How many problems are there, and what's the score distribution?
Too close to Code Jam 1B round :(
tourist vs Petr
Vs Wael.Al.Jamal
And vs jqdai0815 and vs dotorya, I think.
Score distribution?
How many problems will be there?
delayed...
Please dont delay the contest. There's codejam today.
Delayed by 10 minutes. So now I have just 15 minutes for dinner before Code Jam. :(
Eat fast like Major Payne.
I just ate fast to finish before the start and now my stomach really hurts. (Didnt know there was a delay)
tourist is back!!!
Large number of hacks in Div.1 A.
Thank you, Cpt. Obvious. We would never have noticed that without you. You are truly the hero we need, although not the hero we deserve. /s
World champions got first place here too !
I sure am curious about the quality of system tests for D. I have a solution without proof that it works, but I sure made it hard to break without specifically breaking exactly this solution.
How to solve C/Div1 ?
The condition for increasingness is "when xor-ing X with bi such that the highest set bit of bi is the d-th, the d-th bit of X must be 0". Therefore, we can group bi-s by the highest set bit.
We can go from the highest to the lowest bit d and build the final sequence by merging everything with a given highest set bit with the sequence obtained in the previous step. We can't break that previous sequence this way and we only need to stuff the new bi-s at the beginning / after each 1 as the d-th bit; whether this is possible doesn't depend on what we did before.
Answer cant be more than 5 in D right?
I've proved that it's always smaller than or equal to 5, or no solution exists.
can you please explain why?
We can find a direct path as one option. Other one is think in terms of creating a cycle(precisely three length) and then reaching n. So for no three length cycle to itself.It should be connected to rest n-2 vertices. Otherwise 3 length cycle exist. If not move one vertex down and then take a three length cycle to n because otherwise graph of n-1 vertices must be clique.
What is the result on this test:
6 9
1 2
1 3
1 4
1 5
2 3
3 4
4 5
2 4
3 5
I see a path (1 — 2 — 3 — 4 — 5 — 2 — 6) of length 6... is there a path of length 5?
1 — 2 — 4 — 5 — 2 — 6 is a path of length 5, for example.
There are two cases(excluding the trivial ones when you can go to n using a short simple path):
1) If the connected component of 1 in the original graph is not a complete graph, we can go 1->a->x->1->n, where x is not connected to 1 in original graph, but a is.
2) If connected component of 1 is a complete graph not a triangle, we can go 1->x->y->z->x->1, where all x, y, z are in a's component. EDIT : This is incorrect.
On the second case, why can I go from z to x? Doesn't that edge erases when I visit x?
In case (2) won't the z->x edge be removed when we go x->y?
I think the second case should be: 2) If connected component of 1 is a complete graph, and n is not in it, then answer is -1. And also case 1) is not correct. We can have a path of length 5, ig the connected component of 1 is not complete. So, if we could not found a way as described above for the first case ( 1->a->x->1->n, where x is not connected to 1 in original graph, but a is.), we can find a way (1->x->y->z->x->1) where x, y, z are in the connected component of 1, and we have the edges 1-x, 1-y, 1-z, but we don't have z-x. I have got it accepted using these changes
Ok so I can detail a bit more (sorry for the late reply, I was doing GCJ). There is no solution if and only if all nodes except 1 from 1's component are directly linked to 1 and, removing 1 from its component you're left only with cliques (all the components are complete). Broadly speaking, my solution was something like:
Consider the optimal solution x1, x2, .., xK. Either they are all distinct which means the edges should be those from the initial graph, or at least 2 are equal. Let j be the smallest index for which you also have i<j so that x[i] = x[j]. The thing is that from the minimality of the sequence, you know that you couldn't have ended it earlier so none of x[1], x[2], .., x[j — 1] had a direct link to N. Also from the minimality of j, you know x[1], x[2], .., x[j — 1] are all distinct. Buut then x[j] = x[i] comes. x[i] didn't use to have a link to N, and after first traversing it, it does, so when we're at x[j]=x[i], we have a link to N (and it's obviously optimal to follow it). So either all elements are distinct and you choose the shortest path to N (if any) or j = K and x[i] = x[j] are the first and only pair of equal numbers. Also for the x[i] = x[j] thing to exist, you must have an edge from x[j — 1] to x[j] = x[i] at the point when you travel between the two, which means that you didn't have an edge from x[j — 1] to x[i] in the initial graph (cause x[i]'s edges flipped when you first went through it)
1) Direct link 1->N? Obvious solution
2) A direct path from 1 to N of length 2 or 3? Definitely optimal, cause you can't get any better by doubling a node (you'd need 1 x y 1 N in the best case for a node-doubling option)
3) Does the component of 1 also include a node that is not directly connected to 1? Then there must be a node at distance 2 as well (you can get it through bfs). You can then obtain 1-x-y-1-N which has length 4, definitely optimal
4) All nodes in 1's component are directly linked to it. Delete 1 from its component and now you may assume that you can start from any point. Since you can start from any point and you want to minimize j so that x[j] = x[i], you may choose i = 1, x[j] = x[1] (why not, there's no use into delaying the occurrence of that thing, provided you can start anywhere). If all components are cliques, you definitely can't do anything, cause as I said for that double node to exist there must be 2 vertices x[j — 1] and x[j]=x[i] which don't have an edge in the initial graph, and since it's impossible to find that here, you have no solution. If at least one pair of nodes S, T exists where S and T are connected (provided you erased 1), You may run a bfs from S, and find at least one node T' at distance 2 (since from the existence of T, you know they are not all linked to S). Then you may have the following path 1-S-midNode-T'-S-N which has length 5, again optimal.
what is the hack for div1 A?
2 5 1 0 1
2
1
1 4 1 5
LOL
![ ]()
Now, I regret why my solution wasn't hacked so that I can check this case! My solution will be wrong now! :(
What is pretest 11 in Div1D?
I am guessing it is: one's connected component is a triangle, not containing n. Answer is -1 then. BTW, Is the answer always <= 5?
My code works on this test case, but probably something similar fails it.
And yes answer is always smaller than 5 if not - 1, if 1 N is closed, and there is a vertex u at distance = 2 from 1, then the edge 1 u is intially closed, and opens once you leave 1, so you can travel from 1 to u to 1 to N.
EDIT: This is wrong, see my other comment.
I got WA on the same pretest. My solution was to do a DFS for paths of length no more than 3. If we are able to reach N than that is the solution. Otherwise if there is a path of length 2 from 1 to some other node X, then we can go from X to 1 (because the tunnel is now open) and then from 1 to N.
What is the flaw in this logic?
cerberus97 found a countertest (fails my code at least)
path is 1 2 3 4 2 5
Hate rounds with so many hacks. What's sad is that there are some people who treated that case, but treated it wrong (one of my few hacks was on a poor guy who was printing y1-y2, provided y1<y2). It sucks to let this kind of things happen
I treated the case correctly but forgot to add line separators :/
Forgot the "continue;" in Div1-A :D :D
I also forgot the
Even the mighty fall! :P
How to solve div1A? binary search + greedy? min(only run, min(take nearest elevator(left), take nearest elevator(right)))?
Yes, I did it that way, but I handled the binary search part by using Java's TreeSet (which internally is a red-black tree implementation). A special case is when the starting and the ending rooms are on the same floor — in that case you don't need any stairs, nor elevators. :)
we both are winning or losing together today.
yes if you consider a stair being an elevator with maximum speed 1
How to solve Div1B/Div2D?
I have written a greedy solution which passed pretests:
chose larger x (from x1 and x2).
Try to assign them greedily from larger server size. Choose lower server till it works (v/2, v/3, v/4..).
Then do the same with remaining one.
if any one doesn't work, swap x1, x2. Repeat.
Edit: It failed on test 40. Not sure why. Take this solution with a grain of salt.
Edit2: Okay, Algorithm is 100% correct. My http://codeforces.net/contest/967/submission/37727934 was also correct for test40. I switched the order while printing the answer, Also it was last damn test case.
mkagenius I did it the same way. And I also got WA on test 40 :)
Okay, that hints towards wrong algorithm unless we made same coding mistake (quite unlikely unless a silly one).
mkagenius ok, i was just simulating for max(x1, x2) and not for both. That's so silly.
Here's the Accepted sol: http://codeforces.net/contest/967/submission/37740696
bad luck, and only test was there with reverse order.
this is my Alg "not greedy"
https://ideone.com/kCGiVY
Could you please explain it?
How to solve div2 D / div1 B ?
Sort the array elements in pairs(ar[i],i). Now assuming each array element of the sorted array s_ar[i] as the minimum element for two types of services separately, find j so that (j-i+1)*s_ar[i].first >= x1 and store in cal[i] for 1st type and similarly store for 2nd type in val[i] . Now check if there exists i<cal[i]<j<val[j] or i<val[i]<j<cal[j].
Can O(m sqrt(n) log(n) log(sqrt(n)) solution pass Div 1 E?
Yes (sadly)
I gave up this contest after reading E cause I had no better idea...
I liked this contest a lot, the problems that I tried all seemed (particularly Div2D) were really interesting to think about but at the same time not all that hard to implement. Great job to writers! (Although div2 A was a bit hard)
Can someone tell me why this solution for Div 1 — C : http://codeforces.net/contest/966/submission/37727089 is giving me tle. It is a O(n * 60) solution.
What happened with D in official round? UPD: everything is okay now.
The night of failing system test... I just wanna cry.
Cheater exposed.
![ ]()
What the heck!!! in Div2C?
Div-2-D
1st testcase :
6 8 16
3 5 2 9 8 7
output:
YES
2 2
2 6
5 4
Whats wrong here???
It should be "Yes"
Got WA on 1st case
Maybe "YES" should be "Yes"
As far as i know , CF consider same between Yes and YES..
Not in this problem. I made the same mistakes too.
Each problems have their own checkers. If the checker considers them different, only Yes will be accepted.
Usually, problems give you know that there is no difference between Yes and YES.
I thought they didn't check case. They keep changing rules.
It's not that 'they' change the rules. It's the setters' responsibility to make checkers for each problem, and it's up to them whether they'll allow different cases or not.
Maybe it should not be left for the setter (unless explicitly specified that case matters) Coz people have lost points due to wrong hacking attempts in the past. Either way it should be documented either globally or per contest that case matters or not.
Explain me, please, which rounds have got "practice" and which — hasn't?
I think almost every CF contest have "pratice". But there is some time after the contest (approximately 30 minutes) when you can't submit your solutions
Thank you!
I don't understand why there is so few submissions for div1 D. It is just simple case analysis
How to solve Div1E?
You know you solved it, right?
Eh, my solution is really weird (O(qn^0.5log^2n)) and I bet there is a better one
I can offer O(n2) in 1.7s, Maybe it's better in some way =)
Wow, you always amaze me :o
i solved it in nlognsqrtn with some optimizations.
you solved it :)
Split queries in blocks of size k. For each block build compressed tree consisting of vertices that change in this block, their lcas and the root. For each edge in this compressed tree, store all balances for vertices on that edges in sorted order. When some vertex changes, change all its ancestors and for each edge on the path to root you need to add\subtract 1 from all balances on that edge. You need binary search for it so this solution works in . But you can get rid of it if you notice that you don't need to store balances with absolute value greater that k. Then it will work in . I had no time to implement this optimisation and got OK without it. Sadly I spent 40 minutes solving B, so I wrote E few minutes before the end and had no time to debug it.
last tshirt wowoowoooowow
Got WA on pretest 7 for problem C Div.2, does anyone know what this case was? My approach as just print abs(y1-y2) if on the same floor, otherwise binary search for closest elevator and for closest stairs and print the minimum of the two.
Closest may not be optimal. You have to check closest on both sides of your current location.
Still getting WA, here is a link to my submission if you would mind telling me what is wrong.
Why do they have to be equal to current location?
That's equivalent to
make_pair(lower_bound(stairs.begin(),stairs.end(),y1),upper_bound(stairs.begin(),stairs.end(),y1));
Okay. Well, that doesn't serve the purpose -- that will always fetch positions on the equal or right of current. left side remains unexplored.
Use lower_bound and lower_bound — 1.
Can anybody help me why my solution to problem c of DIV2 failing 8th test case. Actualy it is giving output in exponential form which I am unable to understand why?.Any kind of help would be appreciated. submission link
I'm pretty sure fabs(x) returns a double so replace it with abs(x) and it should print correctly.
Thanks..It worked !!
for div 1 C i chose greedily the minimum value with which we should xor so that we can find the next value in a which is greater than the previous value. I used trie with deletion. Here is the code . http://codeforces.net/contest/967/submission/37730673. Why doesnt it work ?
because there is a counterexample !
If you will "chose greedily the minimum value with which we should xor so that we can find the next minimum value in a which is greater than the previous value", you will get AC.
i am sorry for my english sentence, but i did what you told. plz see my submission.
I have solved the problem in that way during the contest. So it should work and you should look for bugs in your code. Btw, your trie implementation is a bit terrible at first glance =)
Ok. N dont we need trie ?
You have a bunch of places where you need to use
long long
. A few examples I found:1<<lvl
, types ofans
,x
andres
.i have given this statement #define int long long. N i corrected some places where i have given 1<<lvl to 1LL<<lvl and it got AC. Thanks.
A good contest.But it has too long background for its problem.
Damn, my solution got hacked just because I missed one
=
sign in comparison! This is gonna be a good lesson for me! :-(When will be my T-shirt for the 3 Round? I received a letter for address clarification three monthes ago and nothing after it, whereas my friends have received their T-shirts. Whom could I connect with about it?