Hi, everyone!
Unfortunately, the round was moved two hours later. Sorry for the inconvenience.
It is my honor to announce that the Codeforces Round #408 rated for the second division is going to take place tomorrow at 16:35 UTC. As usual, participants from the first division will be able to participate out of competition.
As the author of this contest, I (zoomswk) would like to thank PoomrokC, nisaruj, and Phoom for testing the problems, KAN and netman for their help in contest preparation, and MikeMirzayanov for the awesome Codeforces and Polygon platforms. Cute graphics in this round are designed by my friend Chonphuech Sripongtanakul, so thanks to her also!
In this round, you will be given 6 problems and 2 hours to solve them. Zane the Wizard, along with his puppy and his crush, will be asking for your help. It is advised that you read all problems and read them carefully.
As per tradition, the scoring distribution will be announced later.
I hope you will enjoy the problems.
Good luck! :D
UPD: The scoring distribution is 500-750-1000-1500-2000-2500.
UPD: The round has ended. Thanks everyone for participating. I'm deeply sorry that the problems turn out to be way harder than I expected. Please stay tuned for the editorial. T_T
UPD: The system testing is complete. Congratulations to the winners!
Div. 2 Winners
Div. 1 Winners
I sincerely apologize that slow input/output methods caused so many TLEs. Unfortunately, it is not possible to rejudge the submissions nor increase the time limit at this point. This is my fault, and I'm terribly sorry. I was not aware of this because my solutions run in < 500 ms of time limit in all problems. I hope you understand.
The editorial will be published in a few minutes, and I'll update this post when it's available.
UPD: The editorial is ready!
Good luck to you too! I wish your tests to be strong and your problems to be interesting to read, understandable and challenging! :)
Thanks! I'm trying my best to make all that happen. ;)
It's gonna be my first round after breakup :D
Meanwhile me "forever-single"
Zane is The Wizard but still can't make his crush into his girlfriend. I feel it.
Don't worry, you'll get to help him in the contest. XD
Why do i get the feeling that he is going to ask our help to make his crush into girlfriend.
LOOK AT THIS HANDSOME MAN
HOW DARE YOU SUGGEST HE NEEDS YOUR HELP IN GETTING A GIRLFRIEND
I can't register to unofficial participation.
Sorry about that. I've informed the coordinators of this. :)
EDIT: Len and abhishek_saini, it has been fixed.
Div 1 Users are not able to register.
How I wish there to be earlier contests since i'm in UTC+8 area.
Delaying it 2 hours makes me able to do this round, thank you! :D
Finally zoomswk is writing problems for CF! I heard your problems were really good from some other Triam Udom students in POSN camp 2. Looking forward to participating today!
Thanks! Hope you'll like my problems too.
Thanks for the delay zoomswk, I would have missed the round. Sorry for them who had suitable time.
Too bad, I can't do the round now :(
Rating prediction here
Extensions:
Have fun & high rating:)
I am unable to see the predictions.
When contest start, prediction will work.
Thank you as always ! :D
rip UTC+8
lets just stay up late tonight
lets just stay up late tonight
lets just stay up late tonight
same T_T
div 2 after long days. ;(
1900 a rating everyone must get a lving![contest:408]
It's not a good time for Chinese now, so sad. :(
Thank you zoomswk for giving us the opportunity to help someone.
*opportunity
That's why you don't have friends :D
Lol. Correcting something wrong isn't wrong i guess :D
We are not able to help our self with our crush. Lets see if we can help the wizard! XD
Such an interesting scoring distribution :D
It looks like : A-A-B-C-D-E :)
It looks like A-B-D-E-G-H !
After a long time, a 750 problem.
after locking can't see soln of others plz solve this problem as soon as possible
in problem b , for eg: 4 to 6 swap takes place then is it sure next swap will be from 6 only to somewhere else ?
I think "NO" !!
I can't understand how I managed not to read the only word in bold in the whole statement of C and spending the whole contest solving a different problem...
...You made me realize that i did the same thing lol
Damn it! I did the same thing.
Same to me
same here, read it only 15 minutes before the end :\
Look at first and second page of standings :D
remove them pls before rating update ;D
now it looks like 20+ people sit together and code together and submit at the same time :P
why this guy so boring?
These Bots!
rating army Lmao
And I'm pretty sure code obfuscation is against the rules!
Funny that one of these bots was hacked: http://codeforces.me/contest/796/submission/26272062
Thank you i am very proud of hacking a bot, there was an edge case for all the bots probably that would break them
Hello guy, I wanna know how to show predicted rating changes in standing page like yours, some extensions in browser? Thank you!
Check here.
Thanks a lot!
Codeforces Round #408 (Div. 1,5) :)
is there any better order for F that O(n*sqrt) ?
My solution works in O((n + m)logn). Please stay tuned for the editorial.
what is test 4?
Am I right that answer for D is always K - 1 (may be someone even can proof that)?
UPD Regarding to comment below that's actually number_of_cities_with_police - 1.
If so, that will explain why we had to print sertificate for an answer.
I guess because the tree is arranged according to the law. So the question is actually how to destroy some roads in order to get number_of_cities_with_police connected components. The best way is to have one police station in every connected component. And because in the tree every city is at most d units away, it is possible to keep this property in partition at the end. I hope you understand :)
Including multiple police stations in the same city in D was evil. Cost me 2 WAs. :(
Unbalanced problem set but nice problems! :D
Now I understand why my solution in D was wrong :(
Can someone please tell How to solve C ???? I spent all time on it ,yet no success :(
WTF is C. C is too difficult
Someone tell me how to solve Problem D & E please, I can't wait for the editorial xD
In problem D we can run a single bfs from every police station. Then for every city we have its distance to its closest police station as well as the number of different police stations that has its distance equal to the shortest distance. Run a single dfs from vertex 1. For each vertex, let's consider its children. If a children has abs(dis[v]-dis[u])!=1 then we will cut that edge. If dis[v] == dis[u] — 1 then we will count how many vertex like that and we will erase (cnt-1) of them because we only need one of them to maintain the distance. And for (dis[v] == dis[u] + 1), as we already have the number of ways to get to this vertex, we will delete this edge if way[v] > 1 and then way[v]--. That's all!
D is a simultaneously BFS from every city with police. Mark each connected city with nubmer of a source police city, then go through edges and if a "police number" on the left != one on the right, then the edge can be removed. You even don't need the d parameter.
I did mostly the same, but only marked cities as "connected" without the number of the source and also marked "used" edges. And if I come upon an unused edge that goes to an already connected city then it can be removed.
The girl's cheating algorithm in E is so complex, almost as if you have experience with it :P
For problem B, what is the expected output for this input?
4 1 3 4 3 4 1 3 3 2
2
My program prints 2.
Shouldn't it be 3? Confused.
When 3 and 4 are swapped, the hole should be underneath cup 3. Again when 1 and 3 are swapped, the bone gets into the hole. Now when 3 and 2 are swapped there should be no change. Did I understand the question incorrectly? :/
You input n m k then you input the places of the holes.
In your test case the hole is in number 4.
the hole can not be swapped its constant during swaps
The holes don't move when swapping cups.
Can we use greedy to solve the problem D ?
Can someone provide hack case for B?
2 1 1 1 1 2
i hack using this : 2 1 1 1 1 2
2 1 1 1 1 2
the answer is 1
TL hack with 10^6 numbers. OK if solution hasn't scanf/sync_with_stdio.
Wow, absolutely forgot about it:(
All the contest I couldnt find any other narrow places in B besides the cases above
I think TL was the main reason for so mane hacks
Is problem C just modified BFS starting in the vertex with max guard and max degree, or is there something more? (sorry for my English if it's bad)
(wrong solution)
No, this is wrong.
Take the case:
6
3 3 3 3 3 3
1 2
1 3
1 4
1 5
1 6
Answer would be m+1(4) for this.
Indeed, thank you for pointing this out.
What is the approach for C?
Let there be a set of nodes which have equal and maximum weight.
For each node 'x' from the set,
Final weight of x: Same as original weight
Final weight of neighbors of x: Original weight+1
Every other node: Original weight+2
Do this for each x in the set and calculate the minimum maximum weight.
EDIT: I got a WA. The reason is that we have to consider every node rather than just the max nodes.(Imagine case where all max nodes are connected to a single smaller node)
Shouldn't that get TLE if all of the nodes are with the same value ?
I used multisets so I only had to iterate through first node+neighbours.
It took 1s but TLE is still a worry.
5
5 5 4 5 5
3 1
3 2
3 4
3 5
Wouldn't your algorithm give 7 for this case? I think it should be 6.
"If t > 3, then the answer is m+2." I think it's incorrect. For example, there can be 10 nodes with maximum value, and one node which connects with each of this nodes.
I think starting from guard with a max strength and connected to maximum number of other max guards is correct, your algorithm will not work for graph: 10 10 10 10 1 1 1 1 ... 1 2 1 3 1 4 4 5 4 6 4 7 ...
Your algorithm starts from 4, and we should start from 1.
-8 in B because i forgot ios::sync_with_stdio(false) D:
it was a big leap from b to C hahaha
Each Id belongs to one person I guess! but if each code are same then they will be skipped without the first one. But he should get punished -_-
Hi, Could someone help me out with understanding an optimal solution for D ?
Thanks!
I think we can separate the tree in forest, where the root of each tree has a police office in it. This way the answer will always be P - 1
careful with several police stations on same node:)
S**t :( Failed to notice that multiple police can exist in one city :'( maybe that's the reason for getting wa on pretest 6
I don't think it is. I was failing on 6 for the longest time too. What does your solution output for this inout:
I believe the correct output is
(EDIT: Fixed it from 5 2 3 to 5 2 2)
1 3 And I believe that's a correct output :(
Sorry, the I actually gave you the wrong input, the first line should be
5 2 21 3 isn't correct btw, it should be 1 2
Damn. I failed to notice that too. My program was based on the assumption that there's only one police in one city ;-;
I believe that it is the same guy who have the ranks between 3, 30 :D
That feeling when you realized problem A minor bug... in the last 30 seconds
The problem set was really very nice. I have enjoyed all the problems. Thanks for the round. Hope to get such good problems from you again.
Submitted D with 9 seconds to spare, let the system tests be kind
Let's see.
You've got to be kidding me...
Fake , fake everywhere ..
How to solve E?
Who dis?
The reason why system test is pending
Поднимите руку те, кто счел, что в задаче D параметр d весьма никчемен.
How to solve B? I have wasted 1 hour and 53 minutes for damn pretest 3 on B...
1 ≤ hi ≤ 106, so you can keep them in bool array, like holes[hole] = true.
Then check if holes[bone] = true then print bone, break else continue swapping.
Link for submission: http://ideone.com/BvFVqI
So why didnt it pass?
What if the ball is in v at the beginning?
Because of you didn't check case when v = = ball
omfg im so fckin stupiiiiiiiiiiiiiiiiiiiiid 1:53 of hour lost for that
1) if first position contains hole , then obviously print 1 , return 0; 2) else -------> keep track of current position of bone in any variable(say boneVar) -------> Initial value of boneVal = 1(given in question)
----- > now iterate for k times and take values of cups to be swapped,,, suppose inputs are cup1 , cup2 for(int i = 0 ; i < k ; i++)
if(cup1 == boneVar) boneVar = cup2; else if(cup2 == boneVar) boneVar = cup1;When system testing will start?
I think it may take a while because as you can see, there are many many spam accounts in today round and moreover, their owners have used "Find and Replace" to replace names of all variables and functions which will make the CF anti-cheat accept their solutions UPD: All bots have been deleted
From rank 3 to rank 30 , will those people be removed and ranks will be updated ???
can we use this to solve E?
UPD: It works
If (p / 2) * k >= n. Obviously, It is the maximal point. Else we use dp with n * p * k states, each state has O(k) transitions.
Isn't that O(npk^2) complexity?
I came up with a solution with O(n*p*2*k) states and constant number of transitions but didn't manage to implement it during the contest. And it also took my a while to finally accept it afterwards. It turned out to be pretty messy :/. Here is my code if you're interested.
UPD: Ok, I missed the point. It's indeed O((n^2)k).
It is the intended complexity too. Again, timelimit is too strict :). 1000 * 1000 * 50 = 5.10^7.
The cheaters are removed from the rankings, except the one who got hacked on C.
koil (save the name to remove )
Not for all...:( :(
It's because C question was Tricky one :)
Contest was solely based on A and B questions for most of the people.
Test 66.........
Did it pass ???
in B many people might receive TLE.
me too :(
Yep, my code TLEd on that test aswell http://codeforces.me/contest/796/submission/26262616
Can we have an rejudge since my code is only reading the input in C++?
do you ever think about the ones using pascal? how bout their io?
Yeah, i was pretty selfish forgetting about pascal, java, etc
Why we should get TLE only for cin?? Even in CF ??
This should be rejudged :'(
I think rejudge won't happen unless there's problems with checkers\validators\tests.
:'(
Got to hate getting TLE for using cin instead of scanf
I think there were some problems with the server during system testing. At B, many people(as have I), have got a TLE even if the complexity was linear in the numbers read.
TLE on B? What is this dude?
slow io
In CodeForces we shouldn't get TLE for this -_- :\
Since our algorithm was right; we should get AC!
TLE on problem B because I forgot to use fast IO 26261895
Problem C TL is so tight... my solution passed pretests with 1500 something ms and so did many others. Now my solution got TLE (probably ran a test in about 2100 or so ms) while many others are getting AC with 1950+ms solutions.
Not fair in my opinion.
Could someone Please tell me why am I getting tle in Java in div2b problem. My code's complexity is O(K) . Here is my submission. please check Here..
Big input.... Feel ya
Time limit for problem C is too strict. Solution use multiset must pass.
I know right? I used multiset and got TLE... if TL was 3000 it would have passed. I'm pretty sure they are not gonna rejudge though, unfortunately :/
I used a multiset and passed. http://codeforces.me/contest/796/submission/26267399
I use multiset (C++) and it passed:)
After this comment I've checked time of my solution ... it is 1949!
http://codeforces.me/contest/796/submission/26276914
Used multiset and TLEd......... they should rejudge it with a higher TL imo. If you go ahead and check everyone's solution there's A LOT of them that passed with 1900 or more ms.
I agree that sometimes you may be lucky and get AC with a high time. However in this case half of the AC solutions (or even more) had 1900+ ms.
Here is my code: http://codeforces.me/contest/796/submission/26271475. Looks like you perform twice as much inserts/erases. That may be the reason why you've got TLE.
My solution with Segment tree passed in 1123 ms.
My solution using multiset passed with 1.85
Strange... I got AC with 1231 ms http://codeforces.me/contest/796/submission/26271625
you use C++14, this may be clue:)
I got good on problems A, B and D, but after tests i only got A... Failed on TL on B and wrong answer on test 13 on D. http://codeforces.me/contest/796/submission/26274912
Why TLE? http://codeforces.me/contest/796/submission/26277280
for cin, cout use these two lines in front of main: ios_base::sync_with_stdio(false); cin.tie(0);
The core of the task consist in using these "two lines in front of main: ios_base::sync_with_stdio(false); cin.tie(0);" with cin,cout?
Or you can use old, fast scanf and printf :/ I also got TLE on that problem :/
Why did your do it?
I used cin with sync...
Why is the system testing so slow? It seems like it is hung...
Failed Test 64 :-(
http://codeforces.me/contest/796/submission/26274847
Why?
I failed on 64 too!
http://codeforces.me/contest/796/submission/26275877
why system testing does not finishes?
Am I only one who couldn't access codeforces for about 5-7 minutes?
I really hoped the purpose of Question B was more than just rejecting cin and accepting scanf -- it probably shouldn't have been a CF problem if that was really the case.
Really this problem shouldn't be in CF. Today I will become a pupil :'( :'(
Welcome to our school!
I've solved with cin/cout (1185 ms)
You have
In your code!..
But this shouldn't be a problem in CF. Right Algo should get AC :'(
this is very common trick and it known by everyone who use cin/cout :)
What I really meant was that I didn't expect the entire purpose of the question to be testing fast I/O...
Slowest System Testing Ever.
Too long testing today. Eyes are on the screen for a long time, now tired :(
B and C are all about file reading optimizations. Had to switch pypy to cpython for it.
How to solve C?
It's time to eat breakfast.
They should mention about the faster I/O method in the question
Is it just me or recently in div 2 rounds the difficulty gap between problems is getting larger?
They removed bots !
Seems like they made case #66 of B only for removing solutions with cin/cout >_<
They should have made that test #1 for faster testing :D
The entire purpose of that problem was to test fast i/o ? >_<
I used cin/cout in B and got AC!
How? I used too and go TLE, with scanf it passes tests
Use this in main() to avoid TLE due to I/O!
in C, my O(n) solution with printf/scanf got TLE :|
I managed to think nlogn. How to solve in O(n)?
One possible O(n) approach is realizing that we always start with the node that is neighbouring to the most nodes with maximum value. If the node itself has maximum value it is also counted as neighbouring itself. In the case of a tie choose a node that is maximal itself. Then hack from there.
This works in O(n) and can be implemented quite cleanly: submission
Problem B:
How is this submission displaying an additional "1" at the end? It's driving me crazy.
The output on my IDE doesn't include the additional "1" at the end.
You shall end program here if (holes[1] == 1) { cout << "1" << endl; break; // return 0; }
Still, the 'break' instruction will exit the 'while' loop to the "return 0" line.
EDIT: removing the entire if(holes[1]==1) part from the code and running it on codeforces will still display "1" at the end.
The other 'break', when the ball is dropped into a hole, won't exit the 'while' loop though, since it is located inside a 'for' loop.
Пытался загнать в E следующее жадное решение: за линию считаю какое максимальное количество вопросов она сможет списать. Прибавляю к ответу это количество. Удаляю у гениев вопросы, которые она списала. Снова пересчитываю все. И так p раз. Не могу придумать контртест (
I tried dfs on the problem D,and got a wrong answer on 6.26286839 I saw the others used bfs.So dfs is a wrong way?Can someone help me ?
Got runtime error test 38 Problem A http://codeforces.me/contest/796/submission/26263998
Later tried test 38 in Codeblocks, works normally and correct
WHY?
I recommend you to check whether the index is in the bounds before accessing the array elements.
http://codeforces.me/contest/796/submission/26289242
Where can you see the standings (scoreboard) for the Div 1 users?
DIV2-C: Got TLE in testcase 35. can anyone help me in analysing the time complexity of this submission Thank you in advance :)
I got a WA on test 6, whose input is: 5 1000000000 0 1000000000 0 1000000000 1 2 2 3 3 4 4 5 and the answer is 1000000002 ; but I think the right answer is 1000000001(with hack order 3 1 5 2 4)....I need help...I can't understand why..TAT
Read the three conditions carefully. After the bank 3 is hacked, you can only choose to hack banks 2 and 4. Banks 1 and 5 cannot be hacked yet because they are not neighboring to any offline banks.
I just wonder if the algorithm still work when the city is not a tree in problem D.
It will still work. The solution would be more obvious could the input be any graph, wouldn't it? XD
Is problem C in this contest updated ?
I haven't done anything with it. What's the matter? :O
I am so sorry .The wrong with me i thought this is another problem :D.Thank u for caring.