Дорогие друзья!
Мы рады представить вам Codeforces Round #363, который пройдёт с частичным использованием задач прошедшего в начале июля в Санкт-Петербурге VK Cup 2016 Final Round. Вторая часть задач чемпионата будет использована при проведении Codeforces Round #364. Разумеется, мы дополнили набор задач до полноценного раунда Codeforces, чтобы каждый мог найти задачу подходящей сложности, которая ему будет интересна.
Не желая изменять доброй традиции, мы опубликуем разбаловку непосредственно перед началом соревнования.
Желаем вам удачи и удовольствия от решения задач!
UPD1. Стоимости задач будут стандартными 500-1000-1500-2000-2500-3000 для обоих дивизионов (да, в обоих дивизионах будет предложено для решения шесть задач).
UPD2. Задачи были подготовлены для вас MikeMirzayanov, Errichto, fcspartakm, qwerty787788 и Radewoosh.
UPD3. Системное тестирование завершено, поздравляем победителей!
Div. 1:
Div. 2:
UPD4. Разбор уже здесь, планируется в скором времени перевести его на русский язык.
You are a bit of shit:D
second comment :D
third comment :D
Check the first comment:D
What gets upvoted and downvoted in CodeForces, as usual, is beyond prediction...
Very inconvenient time.
As my college has started now i have to wake up early and get ready for the class and late Codeforces round make my routine little bit hactic...Thank you so much GlepsHP for choosing such a nice time for the contest.. Hoping to gear some of my rating points and wish everyone a high rating :)
The way the TooDifficult has been improved with past rounds , one day sure he may defeat even Petr and tourist . Waiting to see that happen.
Wow!! You made all three of them Headquarters. Mike has got competitions
I still don't get it. Why is his title "Headquarters" ?
Because he's in the Headquarters of Codeforces
.
So that people don't compare themselves to him.
Also, he's the fucking admin so he can do whatever he wishes. Hell, he can define his rating as touristsrating + 1 if he pleases.
Я так понимаю что призыв не участвовать в ближайших 2х раундах тех, кто участвовал в онсайте отсутствует, потому что он очевиден.
Тем не менее, единственное упоминание что в этих раундах будут задачи с финала VK Cup только в этом посте. Никакого предупреждения в соглашении об участии нет и зарегистрироваться на раунд мне тоже дали. Поскольку и раунды обычные и нумерованные, полагаю что можно совершенно случайно пропустить блог пост и принять участие в раунде, заметив знакомые задачи только во время контеста.
Yesterday I thought I'll be able to participate in two CF rounds this week... Ouch :)
Can you add part about VK Cup to the contest registration message as well?
Want another Christmas tree?
What do you think dreamoon_love_AA is trying to paint, sir?
Maybe he is a mountaineer?
I'm the mountaineer
Yours is more like two-hump camel now :)
I...I thought they were boobs at first.
tweety himself was producing a very nice sine curve, but he just had to break it :v
SRM 695 ends just 5 minutes before the CF contest.
How so, by my calculations it ends 30 minutes before the CF contest? As TC contests are 1hr35min, not a full 2 hours right?
Oh yes! You are right! I don't know why the Coder Calendar chrome extension shows that duration is 2h. :P
Wait but doesn't that mean that the contest isn't going to be rated?
"we made some new problems to complete the set to fulfill the requirements of the regular round"
"the requirements of the regular round"
"regular round"
(there, tried to make that as dramatic as possible)
Good attempt, but make a picture next time :P
At first I was very happy about the upcoming round.
Then I noticed the starting time.
...why 16:05 and not 19:35 as always?
However, a Chinese is cheering for that. :P
Palindrome Contest "363" :)
Thank you for changing the start time! The usual 16:35 UTC is in the middle of work for me and I feel guilty doing CF at work :)
Who are the problemsetters of the round?
UPD: thanks for adding them into the main post.
I think you forgot about saying this "..I want to thank Mike for legendary platforms of Codeforces and Polygon. " :D ;
Many user will miss this contest for unusual time
Come on, do you think users don't miss contests at the regular time?
I haven't done a contest since 351. It's not because I didn't want to, it's because almost every contest is at 2:35am here.
So yes, I'm a little bit salty that some people get almost all competitions at a decent time and then start complaining as soon as one competition is at a different time.
(btw nothing personal to you, I just didn't know which comment to reply to so I just chose one)
Hey it's even worse (4:35am) here in New Zealand ok.
Actually I tried to say that regular codeforces round always starts at a common time. For this reason some user never check the time.
:)
Very convenient time.
Feels good to have an early contest. :D
The starting time is very good for those living in Eastern Asia, since most of the CF rounds ends at 2 AM for us. I'm really happy.
Wow,what a special time! It's very good for us.We dont't have to stay up late for the contest. :)
CF can consider arranging contests at different times regularly I think. It's a big community from all over the world and definitely some times are completely impossible for some people. I am in a time zone where usual time is at 9/10 PM and this contest will be at 7pm. Very much convenient for me but this is not the case for all.
Но могут ли участники "VK Cup 2016 Final Round" участвовать ??!!
Sure, no.
your question is equal to !("is it rated?").
No, it's equal to is it unrated.
!("is it rated") == ("is it unrated")
Do you mean !("is it rated") == ("is it unrated")== true == true == ....
No, I guess as Mike is saying the round is rated
Good revision saved yourself from an wrong answer. :D
Are you banned on GoogleTranslate?
Dont know if it is true or not, but if some problems are from vk cup 2016, then it is possible that some of us already know some of the problems!
The participants of final round cannot participate in this round.
And the problems of the final round were not disclosed?
Does this contest contain original problems of VK Cup 2016 Final Round or easier version of them?
for the sake of tradition, is it rated?
i hope the problems will be short like this entry
This VC Cup 2016 Final Round problems will be only at div1 problemset or only at div2 problemset or both :/
More and more comments like " oohh .. good time " ; " bad .. bad time "...))) Despite of fixed time for constest , it be always inconveniently for part of us , but convenient for other, or it is not clearly? :D ... The earth is round and here are contestants from each part of earth , it's impossible to set a good time for all.
There aren't many competitors living in the middle of the Pacific Ocean. (And those that do aren't able to code during the day.)
This Time i will be in top 10.
of your room ?
No......overall
Counting from the last ? :D
p.s No offence !! Wish you to be first in TOP.
It was my turn XD
So excited to participate in a Div.1 round after a while.
P.S: tourist is not participating, so it could be the one(if Petr participates)!
How do u know tourist won't participate?
He just asked his astrologer
The participants of final round cannot participate in this round.
Rated or not?
No matter what the starting time is, The servers will be slow and by the time I'm able to see problem A 100 people would get AC already, as usual. :P
As a Chinese student, late Codeforces round make my routine little bit hactic...Thank U so much for choosing such a nice time for the contest.. Hoping to gear some of my rating points and wish everyone a high rating~~ :)
666
77777
How can i register ? It shows extra registration has time left, but how to register ?
Thanks
Уже второй раунд подряд предлагается 6 задач. Это новая традиция?
What is pretest 5(Div2D)?
I got past it when I fixed the case
4
2 3 4 2
Answer should be:
1
2 3 4 4
so maybe it was something similar to that. Then I got stuck on case 8 :(
some thing like it
3
2 1 3
answer is
1
3 1 3 or 2 3 3
I solved problem A and B very quickly, but failed C for the rest of the contest. Anyone know what test case 6 for C is?
I think it is 3 1 1 1
Mine gives answer 1 on this but fails Test case 6.
The answer is 1, Wright? (Ahahaha)
(People who didn't understand the joke: don't downvote, okay?)
Will Petr overtake tourist today? He's in rank 1 of the standings !!! If it happens, it will be after long time (does someone has the data) for someone else to take 1 in overall rankings.
EDIT : He does it infact. :D Glad to see him at the top here.
Does anyone know the hack for Div 2 B?
4 4
...*
....
....
*...
Also 500 * 500 star grid for tle test.
Answer should be yes (1,1), correct?
Yes.
Or YES (4,4)
2 cases:
Answer: YES 3 3
Answer: YES 1 1 (or any other valid position on table)
1st one should be:
YES 3 3
and 2nd one should be:
YES 1 1
right? Or should the second one be No cause there are already no bombs so you can't destroy all bombs?
The answer for 2nd one is Yes (we can put the bomb in any position). My solution will fail this kind of test :(
:( That test case had me worrying the entire contest.
A cool one:
I am not really sure why I am getting memory limit exceeded for Div2D. Can anyone explain?
http://codeforces.net/contest/699/submission/19249990 Thanks!
Seems to me you getRoot(i) can not deal with the situation when cur is a "tail" to a loop. For example: 1 -> 2 -> 3 -> 4 -> 2 if you call getRoot(1), "start" will be set to 1, but you will never reach 1 again.
The best way to deal with this (as I read somewhere on this site before), is to have two pointers, say l and r, l goes one step each time while r goes two steps each time. If r==l for some timestep, it is a loop.
Oops , that should be it, thanks! should have simply used a visited array. But with the MLE I was thinking in the opposite direction :/
Why this O(n²) solution http://codeforces.net/contest/699/submission/19241016 didn't exceeded the time limit? My hack attempt failed :(
ignore.
Maybe compiler threw away for with j during optimization, since it is never used.
How to solve Div1-B correctly?
I managed to pass pretest with union find — disjoint set.... but I think there may be some corner cases that I haven't handled
this is how my solution work : iterate ocer all i : 1 -> n et for each i , if it isn' t marked " visited " , you use a recursion to search for his lowest unvisited ancestor : if you find a cycle in the tree ( same method as searching for cycles using dfs ) , you push its root ( highest parent ) into a vector v containing root of different connected componnents .... after iterating over all i , you sort v such that for i < j , cyc [ v [ i ] ] <= cyc [ v [ j ] ] to make sure that you make less changes and you consider v [ 0 ] as the root of the only new tree ...sorry for my bad english link : http://codeforces.net/contest/699/submission/19261372
Good day to you, here's my approach:
A) Try to find "ANY" root (node which points too itself)
B) Re-edge all other roots to it
C) Do cycle-finding dfs (Open+Closed states) from all nodes (going to parents). If a cycle is found, re-edge ANY node which is in the cycle to "chosen" root.
If none root chosen in "A", then promote the first one found in "C" as "chosen root".
Here is link to solution (anyway not self-documenting :'( )
Don't hesitate do discuss more of it, if not understood anything or if you have doubts :)
Complexity O(N)
Good Luck & Have Fun ^_^
I was thinking again, and you can avoid step "B", if you forbid visiting "chosen root" in dfs (because in "C", the self loops will do the "B" step automatically — silly me)
New (but almost same) code.
GL & sorry for the inconvenience ^_^
I think it only have two case like number 6 (loop) and 1 (or a point) :)) :)) The first line ans is total tree — 1 (if have at least 1 tree like number 1) or total tree (if all tree like number 6)
I guess that we will have an another unlovely system testing with a lot of wrong answers on main tests.
Div 1 C — DP with matrices?
Nope :D
Since the operations are completely independent, try making them in reverse. Now question is "what is the probability that i is among the first k videos accessed in the first 10^100 hits?"
But it is extremely likely that you will access at least k videos before you do that many hits, so you can simply ignore the last part and answer "what is the probability that i is among the first k videos accessed?"
Well.. This seems easy. But what then? I got stuck on writing DP in less than O(2^n * n^2)...
Well, you only care about the current set of "activated" videos and the next video you add, O(2n * n). But I think O(2n * n2), whatever the idea is, could theoretically also pass TL...
2^n*n^2 is 4*10^8 so if the constant factor is large it will fail. In this problem we need double computation so it is not surprising if it fails.
We had O(n2·2n) during the original contest and it passed
Ignore.
What do you mean by making operations in reverse? Could you elaborate? It seems to me that processing request in reverse is a totally different game.
Well,the fact that moves are independent of each other helps much. Don't take into account the LRU game,the problem reduces to the last k different videos in the end.
Take it this way: I want to know which are the last k videos <=> I want to know which are the first k videos looking from the end. BUT the moves are independent,so the probability of choices x1,x2,..,xn with fixed y1,y2,...,yk at the end is the same as the reversed one with fixed y1,y2,...,yk in the beginning.
You can also see it as a bijection,pointing a sequence to the reversed one. If video i is in the last k videos of a sequence,it is surely in the first of the reversed one. So the answer for video i will be calculated correctly.
Making the reverse problem may not seem different,but it is much easier. There is no game to apply now,as we calculate the answer for bit masks with at most k 1 bits. So no need to remember the order of videos ,which was a pain.
How to solve Div 2 D ? My approach was to count total components and number of such components which are cyclic among them. If all components are cyclic then answer is
No. of componentsand then we can assign root to any vertex and then print parents accordingly. Now, if at least one component is non-cyclic then answer isNo. of components-1and main root can be assigned to the any vertex which is root in its corresponding non-cyclic component. But it fails on pretest 5. Any hints where I should think more ?I followed exactly your method and managed to pass pretests. Must be some small bug in your code. And I think my solution may also fail in main test. I can't shake off the feeling I missed some corner case :/
You forgot about jellyfishes ( cycles with "legs" attached to various nodes on a cycle). You can't assign root to any vertex. It has to be a vertex belonging to the cycle.
For example in this graph below you can't set 3 as root.
I think it is better if an example about how LRU algorithm works couble be added on the Note part of problem LRU.Just discribing it by works is a little bit ... confusing.
Like this :
We have 4 videos and 3 caches
the queries are {4,3,4,2,3,1,4}
at first the caches are 0,0,0
ask 4,then become 4,0,0
ask 3,then become 3,4,0
ask 4,then become 4,3,0
ask 2,then become 2,4,3
ask 3,then become 3,2,4
ask 1,then become 1,3,2
ask 4,then become 4,1,3
In todays contest, Div 2D/1B considered only sample 1 as non penalising pretest, which is slightly unexpected and odd. I think such cases should be mentioned in the Problem Statement(I got -1 due to this). It was also slightly confusing as I thought it wasn't same as Sample 3 and something else instead.
UPD: Sorry, my bad. I always thought all samples were non penalising. I'm not sure why they wouldn't be? Is there a good reason behind this?
The only time that you don't receive a penalty for a problem is on Test Case 1 (whether it be Compile Error, Wrong Answer, Time Limit Exceeded, etc.). Even if Test Case 2 is a sample and you get it wrong, it will count against you.
In all problems and all rounds only sample 1 is nonpenalising.
It says that somewhere in the rules, which you confirmed to have read when you registered for the round, so you must know them by heart, right?
Had he known the rules, this wouldn't have happened.
What is N equal to in Div2A test8?
Same here. I got WA at 2A test 8 and 2B test 53. It's weird.
BLUE?
Purple?
Yeaaaah! Grats to your purple. Switching to C++ has made me more powerful (see my new pic)! No more random time outs like with Python.
So close to solve Div2 F... but close is not solved (unless you are at Hackerrank where you sometimes get 72 out of 80 with brute-force)
semiexp and I think the testcase of F is weak.
In our solution, We check only the map is surjective, not injective. Our solution get WA on the case N=14, p[5]=7, p[14]=14, and others are zero. The answer should be zero but our solution outputs some positive value.
It's my fault, I'm very sorry for that. I will add this exact test today, for upsolving. The already accepted submissions won't be rejudged (of course). If you have some more thoughts about this problem (any particular big tests that should be added?), please write PM to me. Thanks for sharing.
That moment when you have to switch to windows to hack, because your ubuntu doesn't have adobe flash player >_>
Isn't it a bit strange the N<100 for Div2C. I kept on thinking that my solution (which is correct) must be wrong because the time constraints can't possibly be so lenient. :(
Petr > tourist!!!!!
My solution for D failed for a really minor bug, such a weak pretests :(
P.S: Was backtracking intended? Mine got AC in practice.
Finally Petr Beats tourist
Now Petr Top Rated 3597.
Petr got rating 3597 now! It's rank 1!
So tourist has to settle for second on CF even after winning the official VK Cup Finals. #JustTouristThings
:D
Can someone please help me. The output is correct but it says the formats mismatch. submission for div2-B
I believe that is caused by the extra space at the end.
Oh! But it never was there in other problems right? Dunno why is it called "format" then..
Thanks man! It indeed was the problem. Corrected solution worked.
I always thought the judge is lenient about "\n" and " ". But I did learn my lesson with 1 hr of contest time. Should be careful in the future.
This shouldn't have happened. :( Judge should usually ignore trailing white-spaces.
Is it possible to tag some admin to see this post so that they notice this and it doesn't happen to anyone in the future?
1 hr of contest time is significant...
I don't know actually if this will work or not:
MikeMirzayanov, can you please look into this matter?
And desikachariar, you may write a blog entry explaining what happened.
Whether format about whitespaces matter depends on the checker of the problem. It's obvious that for this problem, the author needs to write a checker by himself.(The checker cannot just compare tokens like yes/no, integers or floating point numbers) And it tends to has less tolerance about wrong formatting.
It is jqdai0815 when you Top3 but still fell in rating..
So.... What is test 107 in problem D, i can't seem to have any idea why i am giving wrong answer
Here is a shorter test, your answer is 25 but it is possible to get all 26:
The idea is that you have to first kill
(9, 3), then it opens paths to both(6, 0)and(12, 0), and finally, you can get to(18, 0).Thank you very much for the test!
To make
(18, 0)safe, add something like(9, 4), right above the center monster. There will be 27 monsters, but only 26 will be endangered. (This is an answer to rev.1 of the comment.)Thank you very much! Both test cases work well with my solution, but I still get WA on test 5.
Consider this example, where the last monster (5, 0) is unreachable: 2 3 1 0 3 0 2 0 4 0 5 0
when will be editoral?
Can someone explain me the dp solution for the Div2-C/Div1-A ?
dp[i][0] :- Represents answer when you choose gymming on ith day. dp[i][1] :- Represents answer when you choose contest on ith day. dp[i][2] :- Represents answer when you choose to rest on ith day. Clearly, dp[i][0] = min(dp[i+1][1], dp[i+1][2]) dp[i][1] = min(dp[i+1][0], dp[i+1][2]) dp[i][0] = min(dp[i+1][0], dp[i+1][2], dp[i+1][1]) + 1
Do this for all i b/w n-1 and 0. Finally answer is min(dp[0][0], dp[0][1], dp[0][2])
http://codeforces.net/contest/699/submission/19242139
Thanks.
Petr _/_ won SRM,won CF round same day!
After seeing nice codeforces round problems eager to see nice editorial soon to learn from my mistakes. PLEASE upload it quickly can't wait more.I think other people are waiting too :)
Congratulations to Petr for becoming the highest rated person at the codeforces site. <3
Gosh, forget to set a good value of maximum in Div.2 Problem A gets me a WA.
My ratings...
Can Div2 D / Div1 B be solved using Disjoint Sets?
Could you please tell me how it is solved?
Thanks
First find out that there can be any root of the given tree(if any make ans = -1 otherwise 0)
ans = -1 is for when you have p[i] == i case , the root of the tree.
For every i , check whether (i,p[i]) are from the same set , if it is then make the parent of i as root(if any or create this i as root ) and increment ans each time when you find they are from same set.
Here is my code : 19259242
А за сколько решение D работает?(например такое 19256185)
Несложная оценка сверху на перебор N·K!·(K - 1)!: для каждого из N монстров запускаем рекурсию с маской из K единичных битов и одним этим монстром в качестве цели. Каждый вызов функции с X битами и Y целями повлечёт не более X·Y вызовов с X - 1 битом и не более чем X - 1 целью. Получаем (K·1) × ((K - 1)·(K - 1)) × ((K - 2)·(K - 2)) × ... × (2·2) × (1·1).
Получается 1000·5040·720 = 3 628 800 000. Естественно, на практике будет на порядки меньше вызовов, потому что далеко не любой выбор пары (бит — цель) порождает множество целей максимального для этой глубины рекурсии размера.
Ещё есть предподсчёт: для пары (точка — монстр) найти набор монстров между ними. У Петра это место за
. Можно тривиально реализовать за N2·K.
Update: ещё я читал в решениях (19249890), что один из факториалов не нужен: можно класть цели в стек и всегда убивать верхнюю на стеке. Тогда и рекурсия не нужна. Тесты это прошло.
E was such a beautiful task <333
Are you kidding? :D
I'm surprised I was the only one who used Python's builtin time libraries :P
http://codeforces.net/contest/699/submission/19240157
Почему оно работает?
In B problem (Div 2) for test case:
2 2 .* *.
My answer is: YES 2 2
But the system said: NO
Why my answer is wrong?
You are mistaken.
The case is that your answer is NO
While the right answer is :
YES
2 2
Still wondering why my code fails for test #45 of Div2 B. The report says "There is an obstacle after the bang". Can someone give a simple testcase that breaks my code? 19245284
There are still a wall left after the bomb placed. E.g.
give answer 4,2 and wall at 1,1 still survive. It should be placed at 1,2
Thanks everybody for participating, especially all those guys who were so glad to let me into top-10 without participating in a contest :)
Div2 D,
19261965 Where did I go wrong?
This test case has 0 roots.
Can someone please help?
Good day to you,
I'm not sure, whether this will help you, but here's a more simple TC, which it might fail:
Input:
Your output:
Well it seems you counted "2" changes but made only one (2 is correct but well... :))
Good Luck!
Thanks for the test case!
19278465
we need one more nice tradition: to announce when editorial will be published can't sleep without editorial :( awhhhhhhhhhhh sorry for my impatience
Finally the legander of tourist had destroyed. petr became the first in codeforces
I think copied code not only skipped your submission. I think should subtract rating of copier code. (sorry my bad EL)
Why does it seem that Petr has improved dramatically recently based on CF rating, while tourist seems to be plateauing a bit relatively? It is a bit surprising given that Petr is older, and one would expect greater improvements in younger contestants. Of course I guess question could be a bit meaningless given variance in contests.
Hello people, Can you give me a code, which shows my mistake in Problem 2, Division 2: http://pastebin.com/HsG1G5YV
The test that breaks it does not show fully.
I just brute forced Div2 B. Store how many walls are on each row and column at each x and y, then iterate through each pair of x and y. If the amount of walls on the row of y and column of x (I use y for 'i' and x for 'j') subtracted by the overlap wall in the intersection of the row and column (if there exists one) equals the total amount of walls, then you know that pair of x and y is a viable place to put the bomb. If you don't find a working pair then output "NO".
19242096
Hope this helped. :)
Thanks, plenty of good solution out there, but I am just interested in why my solution fails. Unfortunately, the test on which it fails is too long and codeforces have not written it at whole. Thus, I can only guess.
Your welcome! There is a large variety of good solutions to learn from out there. As for your solution, I can't read C# so I'm not exactly sure what you are trying to do. Hopefully you figure it out. Debug will help out a lot too :)
Can anyone please tell me how to solve div2 D?
Let us make the graph from the sequence given in problem. You can make diagrams and see that in any component there can be at most one cycle, I don't have a proof.
Now for all components, when you get a cycle, just direct any edge of it towards any root(that is present in a component without a cycle). If all components have a cycle, just take any component and make any node on that cycle as root, and do the above things.
The proof is simple. If a component is tree it would consist of n — 1 edge. So the maximum wrong edge in the component is only one.
So...Since I started programming, tourist was always on the top. But now something is different!
Waiting for Round 364 :)
Congratulations on semiexp for becoming IGM in only 7 rounds!
I guess that is the fewest number of participation on becoming IGM in CF history!!
Can I solve problem D by choosing the root ( any vertex such that (p[i] == i) ) , and choose any vertex from each Cycle in the graph and merge it with the root ? . Thank you in advance :D
Yes , but not when there is no i such that p[i]==i. In that case, you need to pick root as one of the vertex forming a cycle.