### NALP's blog

By NALP, 7 years ago, translation, ,

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 (KudryashovIA), 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.

• +93

 » 7 years ago, # |   +11 good luck
•  » » 7 years ago, # ^ | ← Rev. 2 →   +6 Traditionally, the above comment is destined to be negatively rated.
 » 7 years ago, # |   +4 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 :|
•  » » 7 years ago, # ^ | ← Rev. 2 →   +35 Why don't you simply take a positive look at successful hacking? It gives people chances to correct their mistakes :)
•  » » » 7 years ago, # ^ |   +3 also a successful hack increases the total score of the contest by 50 (+100 for the hacker and -50 for the one hacked)
•  » » » » 7 years ago, # ^ |   0 it's fail, if you locked the problem, and someone hacked you :|
•  » » » » 7 years ago, # ^ |   -7 And if someone who was hacked won't send the right solution, it will be +100.
•  » » » » 7 years ago, # ^ |   -13 hacked participant loses all his points for the problem. So hack always decreases total score of the contest :D
•  » » » » » 7 years ago, # ^ | ← Rev. 2 →   +1 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
•  » » » » » » 7 years ago, # ^ |   -6 Yes, you're right. The world "always" not compatible in our situation. Maybe "sometimes"?
•  » » » » 7 years ago, # ^ |   0 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.
 » 7 years ago, # |   0 I believe what was meant was the Maximalist's points (maximum reachable score) and not sum of scores of individuals.
•  » » 7 years ago, # ^ |   0 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.
 » 7 years ago, # |   +9 In queue..
•  » » 7 years ago, # ^ |   +1 oh c'mon, again
 » 7 years ago, # |   0 In problem C, the ri more than defining a row, it defines a column I think, please correct me if I am wrong.
•  » » 7 years ago, # ^ |   0 Wrong output for 2snd sample. Problem D We have 1 in each vertex after increasing. But we should have 0!
•  » » » 7 years ago, # ^ |   0 Actually it was asking to not have zeros in any of the counter. (in 2nd example) I too initially missed the not part. :)
 » 7 years ago, # |   +9 Seems like problems C, D & E (div.2) are much harder than other contests unlike A & B which are easier than other contests
 » 7 years ago, # | ← Rev. 3 →   +11 Funny, the pretests for E are so weak, that I've wrote an TLE code intentionally, so I could hack some people on E :)
•  » » 7 years ago, # ^ |   +1 Pretests seldom check for TLE.
•  » » 7 years ago, # ^ |   0 seems that any attempts of brute-forcing the xor function work for the pretests...
 » 7 years ago, # |   +14 I have always wondered, what happens on server side during the "Pending system testing" phase? Does anyone know the answer?
•  » » 7 years ago, # ^ |   +1 They add "hacks" to test cases before final judgement.
 » 7 years ago, # |   0 Maybe out of topic, but how can we undergo a BFS with time complexity O(n) in a tree?
 » 7 years ago, # |   +3 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.
•  » » 7 years ago, # ^ |   +1 I solved E using Segment Tree.
 » 7 years ago, # | ← Rev. 4 →   -6 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!!!
 » 7 years ago, # | ← Rev. 2 →   +33 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
•  » » 7 years ago, # ^ |   -10 Me too!
•  » » 7 years ago, # ^ |   +1 I got very amused when I realized that TRICK. :D
•  » » 7 years ago, # ^ |   +5 My god, I thought they were repeating the same sentence below, that the "total number of segments" was <= 10^5 =.=
•  » » 7 years ago, # ^ |   0 Could you tell me why?
•  » » » 7 years ago, # ^ |   0 Because if we use BFS, there will be at most 10^5 states. Which passes tests with good time.
• »
»
»
»
7 years ago, # ^ |
Rev. 2   0

I am not sure about we have at most 10^5 states. What will happen with this case? BFS works? Overflow in the queue?

 1 1 100000 100000 100000 1 1 100000 2 1 100000 .................. (ith row -> 1 100000) 100000 1 100000

King's Path = 100000 (Main Diagonal)

•  » » » » » 7 years ago, # ^ | ← Rev. 2 →   0 "It is guaranteed that the total length of all given segments doesn't exceed 10^5."total length != number oftotal length of all != length of each
 » 7 years ago, # |   +5 How solve problem E ?
•  » » 7 years ago, # ^ |   +11 You make a segment tree for each bit.
•  » » » 7 years ago, # ^ |   0 a segment tree for each bit? i dont get it
•  » » » » 7 years ago, # ^ |   0 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).
 » 7 years ago, # | ← Rev. 4 →   0 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.
•  » » 7 years ago, # ^ |   0 just wait,may be will not accepted with strong tests :)
•  » » 7 years ago, # ^ |   +4 I think bfs is perfect to solve it. there are at most 100000 points you may reach
 » 7 years ago, # |   0 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
•  » » 7 years ago, # ^ |   0 When you define the structure i think you should define the members before initializing them.
•  » » » 7 years ago, # ^ | ← Rev. 2 →   +1 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)
 » 7 years ago, # |   -9 My task B failed because i read 10^6 instead of 10^9 limit :@
•  » » 7 years ago, # ^ |   -8 Mee too! :( , i initialized with 10^7 for max calculation, it should have been 10^9. :(
•  » » » 7 years ago, # ^ |   +1 If you use C/C++ I recommend you this : # include // for INT_MAX , INT_MIN , LLONG_MAX , LLONG_MIN and so on... //... int int_mn = INT_MIN ; long long ll_mx = LLONG_MAX ; 
•  » » » » 7 years ago, # ^ |   0 I will surely pay more attention next time:)
 » 7 years ago, # |   -9 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.
 » 7 years ago, # | ← Rev. 2 →   0 My submission at contest! 2539880 { some code } #define U 4 // I set it to 4 only for test my code { some code } My submission after Contest! 2540107 {some code} #define U 20 // input values can have up to 20 bits! {some code} `I didn't solve it because of a 2 characters sooti [= bug] in my code. what can I name it?
•  » » 7 years ago, # ^ |   -7 I offer my condolences :(
•  » » 7 years ago, # ^ |   0 bettered experience
 » 7 years ago, # | ← Rev. 2 →   0 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?
 » 7 years ago, # |   -11 i am ready to fight
 » 7 years ago, # |   +5 Common Rank it.
 » 7 years ago, # |   +7 Is it going to be rated?!! about 3 hours after the contest, it hasn't been rated yet!!
•  » » 7 years ago, # ^ |   0 I am also waiting for that and nothing yet.
•  » » » 7 years ago, # ^ | ← Rev. 3 →   +5
 » 7 years ago, # |   -9 Rating update is slow :(
•  » » 7 years ago, # ^ |   -7 So slow... slow... slow... ZzZZZZzzZZZzzz...
•  » » » 7 years ago, # ^ | ← Rev. 2 →   -8
•  » » » » 7 years ago, # ^ |   0 so slooooow :(
•  » » » » 7 years ago, # ^ | ← Rev. 3 →   0 The ranges will be given today? It is very, very long time and still nothing.
 » 7 years ago, # |   0 Suspense (waiting for rank) :D
 » 7 years ago, # |   0 So better not ask for tutorial :D
•  » » 7 years ago, # ^ |   0 Possibly for next year.
 » 7 years ago, # |   0 Is this contest will rated? I'm waiting... for 3:30 hours...
•  » » 7 years ago, # ^ |   +9 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)
•  » » » 7 years ago, # ^ |   0 And in blog there was not written "Contest will be rated!" or something like this
•  » » 7 years ago, # ^ | ← Rev. 2 →   +2 It is not gonna be rated for you, for sure :)
•  » » » 7 years ago, # ^ |   0 Yeah I know. But I wonder about my friends. Are they will pass me or not. I'm wondering that... :D
•  » » » » 7 years ago, # ^ |   +3 Rating is up now :-)
•  » » » » » 7 years ago, # ^ |   0 thanks a lot bro :)
 » 7 years ago, # |   +11 When will the editorial be published? It would be very helpful.
 » 7 years ago, # |   0 Can someone explain why BIT doesn't pass on task E?
•  » » 7 years ago, # ^ |   +5 You can't make update segment, get sum on segment at same time using only BIT. It can be done with Segment Tree
 » 7 years ago, # |   +4 Any idea how to solve problem D. Dispute ?
•  » » 7 years ago, # ^ |   +6 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.
•  » » » 7 years ago, # ^ | ← Rev. 3 →   +8 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.
•  » » » » 7 years ago, # ^ |   +1 Not just BFS, DFS will also work.
 » 7 years ago, # |   +14 waiting for the editorials.... :D :D
 » 7 years ago, # |   +6 please post editorial.
 » 7 years ago, # |   0 why I got a wrong answer on this submission?2555192
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 I'm not sure, but I think, that when you increment the value of the neighbours you forgot that their values can become a.
•  » » » 7 years ago, # ^ |   0 Thank you ! But according to greedy algorithm, it doesn't matter.
•  » » » 7 years ago, # ^ |   +1 Now I know what you said is right....
•  » » 7 years ago, # ^ |   0 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.
•  » » » 7 years ago, # ^ |   +1 thanks a lot!
 » 7 years ago, # |   0 Have any English editorial?
•  » » 7 years ago, # ^ |   +3 See the post body :)
•  » » » 7 years ago, # ^ |   0 Oh,I see.http://codeforces.ru/blog/entry/5837 is in Russian,but http://codeforces.com/blog/entry/5837 is in English.
 » 7 years ago, # |   0 editorials:
 » 7 years ago, # |   0 How do you solve problem E?