Hi to all!
A few hours later you're lucky to participate in Codeforces Round #149 for Div.2 participants, but traditionally the others can take part out of the competition. It has been prepared by me (NALP), Igor Kudryashov (Igor_Kudryashov), Pavel Holkin (HolkinPV) and Gerald Agapov (Gerald). Also we express thanks to Mary Belova (Delinur) and Mike Mirzayanov (MikeMirzayanov).
Traditionally I wish good luck, accepted solutions and successful hacking attempts for you!
The standart scoring system will be used: 500-1000-1500-2000-2500
UPD: The contest is over, thanks to all!
UPD: Congratulations to the winners:
UPD: the tutorial has been published.
Traditionally, the above comment is destined to be negatively rated.
If someone wish for making successful hacks , He also wishes for another one to be hacked . So you can say : traditionally I wish someone hack you :|
Why don't you simply take a positive look at successful hacking? It gives people chances to correct their mistakes :)
also a successful hack increases the total score of the contest by 50 (+100 for the hacker and -50 for the one hacked)
it's fail, if you locked the problem, and someone hacked you :|
And if someone who was hacked won't send the right solution, it will be +100.
hacked participant loses all his points for the problem. So hack always decreases total score of the contest :D
That's not always correct. If the participant is not hacked, he will fail system test --> his score = 0. If he is hacked, he has another chance to submit and be correct --> his score can be > 0
Yes, you're right. The world "always" not compatible in our situation. Maybe "sometimes"?
Hacked solution is wrong solution. So hacked person's score does not decrease ("hackable" solution should fail the system test) And if his solution had been hacked, if he/she had not lock the problem, he might recognize his solution will fail, so he might increase his score.
I believe what was meant was the Maximalist's points (maximum reachable score) and not sum of scores of individuals.
it's just a small joke to entertain before the contest. the example of being optimistic. besides, it is possible to happen, so who knows.
oh c'mon, again
In problem C, the ri more than defining a row, it defines a column I think, please correct me if I am wrong.
Wrong output for 2snd sample. Problem D We have 1 in each vertex after increasing. But we should have 0!
Actually it was asking to not have zeros in any of the counter. (in 2nd example) I too initially missed the not part. :)
Ask the admin please :)
Seems like problems C, D & E (div.2) are much harder than other contests unlike A & B which are easier than other contests
Funny, the pretests for E are so weak, that I've wrote an TLE code intentionally, so I could hack some people on E :)
Pretests seldom check for TLE.
seems that any attempts of brute-forcing the xor function work for the pretests...
I have always wondered, what happens on server side during the "Pending system testing" phase? Does anyone know the answer?
They add "hacks" to test cases before final judgement.
Maybe out of topic, but how can we undergo a BFS with time complexity O(n) in a tree?
At the first sight I thought that D is Union-find Data Structure E is Segment Tree and jumped into coding. Soon I realized that I was coding the wrong solution.
Lesson learnt: Never code without proving correctness and reading the entire statement.
I solved E using Segment Tree.
Each time we have 2 division contest simultaneously, we have less than 500 coders in 1 div. Now, we have a lot of new coders in first place each time we have only second division. Are they the same with a new user?
top 20 ---> 13 new users. Good Luck in 1 div!!!
Well, the part "It is guaranteed that the total length of all given segments doesn't exceed 10^5." in the problem C is SO TRICKY :D
I got very amused when I realized that TRICK. :D
My god, I thought they were repeating the same sentence below, that the "total number of segments" was <= 10^5 =.=
Could you tell me why?
Because if we use BFS, there will be at most 10^5 states. Which passes tests with good time.
I am not sure about we have at most 10^5 states. What will happen with this case? BFS works? Overflow in the queue?
King's Path = 100000 (Main Diagonal)
"It is guaranteed that the total length of all given segments doesn't exceed 10^5."
total length != number of
total length of all != length of each
How solve problem E ?
You make a segment tree for each bit.
a segment tree for each bit? i don`t get it
For each bit, you will build a segment tree which contains the sum for the intervals. This way you can update an interval in O(logN).
BFS gets AC in problem C?
I got it!!! If you have a doubt with your algo but you don't have anything else, try your doubt. BFS is the first technique I learnt.
just wait,may be will not accepted with strong tests :)
I think bfs is perfect to solve it. there are at most 100000 points you may reach
I have some problems with the C: I pass with sucess the samples given on the statement on local, but on ideone.com or when I submit here, I have runtime error for the same input. Can someone help me, please? http://codeforces.com/contest/242/submission/2537756
When you define the structure i think you should define the members before initializing them.
That is not true. The order inside structure does not matter. Constructor is always called after intialization of instance variable. There is something else wrong with it. (running fine on my local)
My task B failed because i read 10^6 instead of 10^9 limit :@
Mee too! :( , i initialized with 10^7 for max calculation, it should have been 10^9. :(
If you use C/C++ I recommend you this :
I used a stack for bfs, instead of a queue. It's a good lesson to learn : search for trivial mistakes line by line without any assumptions.
My submission at contest! 2539880
My submission after Contest! 2540107
I didn't solve it because of a 2 characters sooti [= bug] in my code. what can I name it?
I offer my condolences :(
My submission for E (i.e. 2537727) produces all zero in CF but it works fine on my machine (g++ on ubuntu with same parameters as CF) and also on ideone (here) can anyone tell me why this happens?
Common Rank it.
Is it going to be rated?!! about 3 hours after the contest, it hasn't been rated yet!!
I am also waiting for that and nothing yet.
Rating update is slow :(
So slow... slow... slow... ZzZZZZzzZZZzzz...
so slooooow :(
Is this contest will rated? I'm waiting... for 3:30 hours...
Well, I'm aware that CodeForces team work hard to maintain the system and sometimes something wrong happens and we can't handle all of them instantly. But I think it would be better for us if we get an update explaining the reason (or not) and/or just a short note, "Due to some unavoidable circumstances, rating will be updated after X hours." It will save a lot of F5 pressing and a lot of contestants won't need to sleep on the keyboard (Later one is not assured, as a lot of programmers like to sleep on the keyboard/desk first and then roll to the bed :P)
And in blog there was not written "Contest will be rated!" or something like this
It is not gonna be rated for you, for sure :)
Yeah I know. But I wonder about my friends. Are they will pass me or not. I'm wondering that... :D
Rating is up now :-)
thanks a lot bro :)
When will the editorial be published? It would be very helpful.
Can someone explain why BIT doesn't pass on task E?
You can't make update segment, get sum on segment at same time using only BIT. It can be done with Segment Tree
Any idea how to solve problem D. Dispute ?
There is always an answer, I'm not sure how to prove this. The solution is BFS. Put all vertex that have value == a to the queue. Then on each step we take vertex, increase it's value and values of it's neighbours and add to queue neighbours which values == a. Just look at my code.
Since one move fixes the problem for one vertex forever, and we can perform up to n moves, this algorithm fixes all the problems and always produces a correct result.
Not just BFS, DFS will also work.
waiting for the editorials.... :D :D
please post editorial.
why I got a wrong answer on this submission?2555192
I'm not sure, but I think, that when you increment the value of the neighbours you forgot that their values can become a.
Thank you ! But according to greedy algorithm, it doesn't matter.
Now I know what you said is right....
It fails because you could go through a vertex and nd[i].a == b[ad] might be false at the moment but then b is updated by a neighbour and now it could become true. You need to do the increases when it becomes true.
thanks a lot!
Have any English editorial?
See the post body :)
Oh,I see.http://codeforces.com/blog/entry/5837 is in Russian,but http://codeforces.com/blog/entry/5837 is in English.