### NBAH's blog

By NBAH, history, 3 years ago, translation, ,

Hi everyone!

Codeforces Round #367 (Div.2) takes place on 11th of August at 19:35 MSK. As usual, Div.1 participants can join out of competition.

This is my first round on Codeforces! I advise you to read all the problems. Hope everyone will find something interesting.

I'd like to thank GlebsHP for helping me in preparing this round, Yury_Bandarchuk and IvanVan for testing tasks. Of course, many thanks to MikeMirzayanov for great Codeforces and Polygon platforms.

UPD: Scoring is 500-1000-1500-2000-2500

UPD: Editorial

UPD: The contest is over. Congratulations to the winners!

Div.1 winners:

1.anta

2.W4yneb0t

3.sugim48

4.uwi

5.Kmcode

Div.2 winners:

2.Shining

4.AwD

5.stjepanp

• +387

 » 3 years ago, # |   -74 kiram to tarrahe in contest
• »
»
3 years ago, # ^ |
Rev. 2   -39

#### The problems producer is just blue like me.Why can I use those problems to be purple?

•  » » » 3 years ago, # ^ |   +5
•  » » » 3 years ago, # ^ |   +10 Why do your comment is hidden every time.
•  » » 3 years ago, # ^ |   -15 كفو
 » 3 years ago, # | ← Rev. 2 →   +18 Simple brief statement, thanks a lot and hope high rating change for everyone =D
•  » » 3 years ago, # ^ |   +53 Sorry but that's impossible :(
•  » » » 3 years ago, # ^ |   0 yeah... these are CF contests.... (;
•  » » 3 years ago, # ^ |   0 i have to wait 10 minute compiling my answer -_- it was shit not contest :(
•  » » » 3 years ago, # ^ |   +7 RIP English
 » 3 years ago, # |   0 And as usual... scoring will be announced later! (maybe just before the contest! or after the contest!) Whyyyyyyyyy?!
•  » » 3 years ago, # ^ |   0 Does it matter?
•  » » » 3 years ago, # ^ |   +12 then why they announce?!!
•  » » » » 3 years ago, # ^ |   +12 It matters during the competition to help you divide your time
 » 3 years ago, # |   -8 "Div.1 participants can join out of competition" What does the sentence mean, please? Could Red users join on Div.2 contests? It's always the case? Thank you. :)
•  » » 3 years ago, # ^ |   0 Yes, they can participate. But their rating won't be affected.
•  » » » 3 years ago, # ^ |   0 Got it, thank you.
 » 3 years ago, # | ← Rev. 2 →   -60 Hope this contest will be better than last Div2 only contest. Hope there won't be such a long queue during the contest because of so many people. (Hate the feeling knowing the contest is unrated after a 2hr-hardwork at midnight)
•  » » 3 years ago, # ^ |   +168 How do you know about last contest? Oh it's your new Div.2 account...
•  » » » 3 years ago, # ^ |   +99 maybe he had new girlfriend ??!
•  » » » 3 years ago, # ^ |   +22 Round he's talking about was unrated. I think that's a reason he is still out of rating.
•  » » » » 3 years ago, # ^ |   +27 Look at his profile "Registered: 25 hours ago" -_-
 » 3 years ago, # |   +15 short GL & HF, I hope statement will be short as this :))
 » 3 years ago, # |   0 Hope for nice problems and strong pretests :)
•  » » 3 years ago, # ^ |   -16 Could someone explain to me the reason for downvotes on this comment?
•  » » » 3 years ago, # ^ |   +139 It's Codeforces. You never know what happens to your comment.
•  » » » » 3 years ago, # ^ |   -44 Well said Tweety. (y)
•  » » » » » 3 years ago, # ^ |   +13 Maybe you are new! but you can use up and down vote buttons instead of this comment!
•  » » » » » » 3 years ago, # ^ |   -13 Well said TD. (y)
•  » » » » » » » 3 years ago, # ^ |   0 In hindsight Maybe you are new! but you can use up and down vote buttons instead of this comment! FYI, I downvoted
•  » » » » » » » » 3 years ago, # ^ |   +2 but downvoting others won't decrease your negative contributions.
•  » » » » » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 I hope the community loves me again :) I wrote a lot of stupid downvote worthy stuff to earn -47. Guess I won't be doing that again.
•  » » » » » » » » » 3 years ago, # ^ |   0 actually we upvote a comment if it is useful, fun, interesting ,... and we downvote a comment if it is useless, spam, ugly,...if you want upvote then interest us!
•  » » » » » » » » » 3 years ago, # ^ |   0 That's not how this works. You never know which comment will be upvoted and which ones will get downvoted.
•  » » » » » » 3 years ago, # ^ |   0 Downvote doesn't seem to work for me whenever I hit downvote the comment rating stays the same, is there any reason for this?
•  » » » » » » » 3 years ago, # ^ |   0 because others upvote simultaneously...
•  » » » » » » » » 3 years ago, # ^ | ← Rev. 2 →   -10 d
 » 3 years ago, # |   +57 Today, give a stranger one of your smiles. It might be the only sunshine he sees all day.
•  » » 3 years ago, # ^ |   -13 +1 for pikachu dp
 » 3 years ago, # | ← Rev. 8 →   0 I hope this round will be more interesting than previous one)
•  » » 3 years ago, # ^ |   +11 Sorry, because of unknown reasons, I counldn't upload the picture)
•  » » » 3 years ago, # ^ |   +19 it's not an unknown reason the reason is that you don't know how to upload a picture anyway, click (CTRL + P) and put the link of the picture
•  » » 3 years ago, # ^ |   -7 You're supposed to get the link to the image rather than the google image link https://i.ytimg.com/vi/LNX4dFILlm8/maxresdefault.jpg
•  » » » 3 years ago, # ^ |   +3 Ok,thanks)
 » 3 years ago, # |   -53 NBAH will you be one of the contestants in this round ? :p
 » 3 years ago, # |   -44 "Are we poisonous?" the young snake asked his mother. "Yes, dear," she replied — "Why do you ask?" "Cause I've just bitten my tongue! "
•  » » 3 years ago, # ^ |   +70
•  » » » 3 years ago, # ^ |   0 I think They are using their time for coding :P so, they don't wanna waste their time and using random comments :P
 » 3 years ago, # |   0 MSK means??
•  » » 3 years ago, # ^ |   +5 Moscow Standard Time. Google it or click the link in the contest's description
•  » » » 3 years ago, # ^ |   -11 or ask here!
 » 3 years ago, # |   -43 Round of div2 member?
•  » » 3 years ago, # ^ |   -81 I hope there will not be an easy task!
•  » » » 3 years ago, # ^ |   -55 cried my contribution ((( Dislike for each my post((( soon the absolute value of my contribution will surpass Errichto
•  » » » » 3 years ago, # ^ |   -43 Dislike me who wants to help me!
•  » » » » » 3 years ago, # ^ |   -20 As u wish
•  » » » » 3 years ago, # ^ |   -26 sorry but i upvoted for u :)
 » 3 years ago, # |   +26 Fact : 367 is a prime number
 » 3 years ago, # |   -35 salamnamifahmid chi migam chera manfi midid?
 » 3 years ago, # | ← Rev. 2 →   0 a round without the IOIers ?
•  » » 3 years ago, # ^ |   +3 Not many of them are Div2 anyways.
•  » » » 3 years ago, # ^ |   +28 Did you just assume their division? triggered
 » 3 years ago, # |   -36 is it rated ??
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 Why everytime there is someone ask that?
•  » » 3 years ago, # ^ |   0 if a contest is unrated, they will tell it in announcement ... maybe as an update
 » 3 years ago, # |   0 Hope for a good and interesting contest. :)
 » 3 years ago, # |   0 I hope this contest won't have so many commercials for games and movies. Just clear tasks.
•  » » 3 years ago, # ^ |   0 You think the one about avengers was with help of commercials?, u think they ask codeforces community to create probs about them?..
 » 3 years ago, # |   +25
•  » » 3 years ago, # ^ |   +13 Yes,dude ... NEVER :)
 » 3 years ago, # |   -10 Too late for Asia......
•  » » 3 years ago, # ^ |   0 Too familiar :)) :))
•  » » 3 years ago, # ^ |   0 Ah
•  » » 3 years ago, # ^ |   0 I think it's too good time for Bangladesh <3
•  » » 3 years ago, # ^ |   0 I have a dream, that there will be more contests ends before 12 m.n. in my local area for me to get at least a purple... At this rate it would probably take several months to wait for a contest which my brain can function normally.
 » 3 years ago, # |   +3 Randomness of likes and dislikes will one day be used as a random number generator :vLike if you disagree :v
 » 3 years ago, # |   +4 Today is Codeforces NBA match ;) Wow!! That's great to play on computer too. Thank u very much NBAH. Best of performance for everyone in this match :)
 » 3 years ago, # |   0 Is there anyone who could help me to solve this problem or give any other approach.Thanks in advance http://codeforces.com/blog/entry/46505
 » 3 years ago, # |   -11 [user:jibancanyang]Come on,believe yourself,and tonight you must be the candidate master!
•  » » 3 years ago, # ^ |   -34 a;;;;;;;;;;;;;;;;flbgoqwgowqeiufhhdvbka;bdkasbf;efowofowjo#inwohndlandsfl!
•  » » » 3 years ago, # ^ |   +1 I guess you will be hidden again.... 0.0
 » 3 years ago, # |   0 Anyone here knows how to unregister I'm not sure if I will be able to write codeforces today PELASE HELP
•  » » 3 years ago, # ^ |   +11 Just don't submit anything or open page of participants >> find your handle >> click the red (X) button to the right of your handle to unregister yourself
•  » » 3 years ago, # ^ |   +3 If you don't submit, your rating won't be affected.
•  » » 3 years ago, # ^ |   0 If you didn't submit anything,they won't check your rating.
 » 3 years ago, # |   +3 We should wait 9 days for next contest :((
•  » » 3 years ago, # ^ |   +3 And two week for next div 1 contest!So far!
•  » » » 3 years ago, # ^ |   0 wow! it's a long time for you!!!
•  » » » 3 years ago, # ^ |   0 You can still practice with div 2 contests, and it's more comfortable since there's no rating on the line.
 » 3 years ago, # |   +18 The Olympic season is here and we have some Codeforces rounds scheduled too. We should have an Olympic themed contest.
 » 3 years ago, # |   +6 Wish Good luck to all :)
 » 3 years ago, # |   +26 Queue is back. :/
 » 3 years ago, # |   +9 my source is still in queue for long time. does this happens to anyone else?
 » 3 years ago, # | ← Rev. 2 →   +5 Codeforces queue :/ . Please do compensate for the time we have lost in this and are still losing.
 » 3 years ago, # |   0 queue 2 : the nightmare
 » 3 years ago, # |   +4 make it unrated:/
•  » » 3 years ago, # ^ |   -20 ياخرى حليت 4 شو unrated ؟unrated بطيزك يامنيك
•  » » » 3 years ago, # ^ |   0 behave your self . gotosleep
 » 3 years ago, # |   0 give us time so the queue is fucking us :(
 » 3 years ago, # |   +5 i hope it's not going to be unrated again!
 » 3 years ago, # |   0 Auto comment: topic has been updated by NBAH (previous revision, new revision, compare).
 » 3 years ago, # |   +9 20 pages of unjudged solutions
 » 3 years ago, # |   +5 I guess it's another unrated contest, unfortunately.
•  » » 3 years ago, # ^ |   +16 Stupid person shut ur mouth
•  » » » 3 years ago, # ^ |   +18 LOL
 » 3 years ago, # |   +18 I thought the queue problem was solved! I submitted B. Waited for 5 minutes, still in queue. Went to solve C, submitted C, found out B was WA. And now C has been on queue for 3 minutes. wtf! -_- Thank god it's unrated for me. I'm out.
•  » » 3 years ago, # ^ |   -10 لطيزي
•  » » 3 years ago, # ^ |   0 how did you make it unrated for yourself?
•  » » » 3 years ago, # ^ |   +9 he participated out of comptetion.
 » 3 years ago, # |   +7 My solution to C is not even in the queue. I am not able to submit it! -_-
•  » » 3 years ago, # ^ |   +3 Finally was able to submit by uploading the source file. I am having this problem since many days, not able to submit code that is copy-pasted in the editor.
 » 3 years ago, # | ← Rev. 3 →   -23 !
 » 3 years ago, # |   +13 Please, don't make it unrated.
•  » » 3 years ago, # ^ |   +10 It would be unfair for participants who got WA after one hour. :/
•  » » » 3 years ago, # ^ |   0 Who told you life is fair ;)Besides, it will be unfair to those who got their solutions judged in time. Its just like contest time. Some countries benefit from the time, some have troubles. You won't complain about that would you?
•  » » » » 3 years ago, # ^ |   0 if there's long queue, no one will get their solutions judged in time. and really a wa verdict after a long time makes it unfair for the contestant.
•  » » » 3 years ago, # ^ |   +8 R u sure u got wa after an hour? I really think what ur saying is false..All my submissions passed is <=10 mins...and just look at the number of people who solved each problems.. the stats say ur lying
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +7 One hour :o ? I submitted program at 5min, 10min, 30min, and 70 mins. I had to wait for more then 5 mins for pretests only for 2nd (which was at 10 min) Rest all submissions were quick in judging (less then 5 mins for sure)
•  » » 3 years ago, # ^ |   +1 Congrats, good work! ^==^'
 » 3 years ago, # |   +25 Wow, really great curve of number solved. And this is only halfway through the contest.
•  » » 3 years ago, # ^ |   -9 مو قلتلك حاج تعلق ؟! روح استمني عحالك .
 » 3 years ago, # |   -7 On a completely off topic, how many people on codeforces follow Silicon Valley (TV show) ?
•  » » 3 years ago, # ^ |   0 I do :D
•  » » 3 years ago, # ^ |   0 Well, I don't think you can get your answer if you ask this question here. After some yes/no, people will stop replying due to negative votes (spamming). You should rather create a poll externally and give the link here.
 » 3 years ago, # |   +1 C was a dp problem right? I was starting to get it but I didn't have enough time to debug :(
•  » » 3 years ago, # ^ | ← Rev. 2 →   +1 From the fact that it was called "Hard Problem" and that some people submitted it in 4 minutes, I am guessing there is a non DP solution but sadly I don't see it. Can anyone share their solution?
•  » » » 3 years ago, # ^ |   0 Can you explain what your DP solution was? Just so I know if I was on the right track (if you don't mind).
•  » » » » 3 years ago, # ^ |   +2 d[i][t] = minimal cost with last element i, and t = 1 if we don't reverse it, t = 2 if we reverse i-th string.
•  » » » » » 3 years ago, # ^ |   0 Glad to know I was pretty close lol. Thanks for the help.
•  » » » » » » 3 years ago, # ^ |   0 انت مخنث ؟
•  » » » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 Lol I like my hair though so I think I'll keep it (if you're making fun of my hair). Edit: Also I'm 100% male.
•  » » » » » » » » 3 years ago, # ^ |   0 العق مؤخرتيبندوق مغكر حالك بتعرف تستخدم google translate ?
•  » » » » » » » » » 3 years ago, # ^ |   +1 Don't even bother replying him.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 Apparently some people did write dynamic solution in 5 minutes e.g. #19788803. I'm impressed.
•  » » 3 years ago, # ^ |   +1 Yup. You could view it as a graph problem and then it is finding the shortest path in dag from 1 to n that could be done in O(n + m) There are 2*n vertex and every vertex has max of 2 outgoing edges.
•  » » » 3 years ago, # ^ |   0 I was considering representing it as a dag too. Thanks for the help.
•  » » 3 years ago, # ^ | ← Rev. 3 →   +2 let's call l[i] is the list of strings and r[i] is reserved string of l[i]. Then we have dp[i][0] means min cost of list from 1->i that l[i] is not reserved, and dp[i][1] means l[i] is reserved. First dp[i][0] = Inf, if l[i] >= l[i-1] dp[i][0] = dp[i-1][0], if l[i] >= r[i-1] dp[i][0] = min(dp[i][0],dp[i-1][1]). Then dp[i][1] = Inf, if r[i] >= l[i-1] dp[i][1] = dp[i-1][0] + c[i], if r[i] >= r[i-1] dp[i][1] = min(dp[i][1],dp[i-1][1] + c[i]). Res = min(dp[n][0],dp[n][1]). If Res = Inf then Res = -1. That is my solution and it passed present test.
•  » » 3 years ago, # ^ |   0 I implemented a 1D DP solution. Here is the link to the solution.
 » 3 years ago, # |   +19 I don't like man :P. When I get 20 minutes penalty and a WA just because I wrote a statement twice . :DAnd by the way was it only me who took Manhattan distance in Problem A and passed 6 pretests? :D
•  » » 3 years ago, # ^ |   0 I used taxicab geometry too, and I found out I was wrong about it on the 7th pretest :/
•  » » 3 years ago, # ^ |   0 same same :P
 » 3 years ago, # |   +1 Got response from judge after 20 min from submission.(long queue)Also sad as i got to know it was wrong after 20 min. :(Will this be a rated contest?
 » 3 years ago, # |   +1 How to solve D? Thank you.
•  » » 3 years ago, # ^ |   +9 I solved it using Trie
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 It can be solved by trie, easily. I supposed that you know task to find the biggest xor of two elements in array ( you can find solution on internet easily too). Here you only need to story how many times you went through some node ( because sometime you must delete some edges).
•  » » 3 years ago, # ^ |   0 Look at Problem 1 in this article: Trie Tutorial
•  » » 3 years ago, # ^ |   0 In my solution we write every number in binary using 35 bits, we use leading zeroes if required.I let the map M[i,j] save how many integers x satisfy that when you only look at the bits in the first j positions you get i.Both updates and queries can be done in time
•  » » » 3 years ago, # ^ |   0 Dang I wish I'd thought of this I made a mess trying to implement a Trie
•  » » 3 years ago, # ^ |   0 Use Binary Trie.
•  » » 3 years ago, # ^ |   +6 This is my idea, haven't tried it yet.Convert every input(number) to binary system. Put it in BST (1s go right, 0s go left). Make sure that all numbers in binary system are the same size. So 6 -> 110, but if max value is 1e9, it became 0000....110.When you search start from leftmost digit and go through BST and pick side different than current digit. When you reach the last node it's your answer.
•  » » » 3 years ago, # ^ |   0 It looks like greedy solution, can you prove that it right in all cases?
•  » » » » 3 years ago, # ^ |   +3 2^t > 2^(t — 1) + 2^(t — 2) + 2^(t — 3) + ... + 2^0.
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   +3 That part is not so hard, because the every bit is clearly more important than all of the bits to its right, combined .
•  » » » » 3 years ago, # ^ |   0 Thanks.
•  » » » 3 years ago, # ^ |   0 What will you do if both children have same digit with current digit?
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   0 Oh, stupid on me. Both children definitely won't have same digit with current digit at the same time.
•  » » » 3 years ago, # ^ |   0 It's efficient for searching. But wouldn't it be hard when we're gonna do deleting operation on the tree?
•  » » » » 3 years ago, # ^ |   +1 I would do same as search, when you reach last node, go up. while (true) { bool check = parent_has_one_child int digit = node_value go to parent delete child with value == digit if (!check) break; } 
•  » » » » » 3 years ago, # ^ |   0 Ah I see, I've already considered that method in contest but stumbled in delete operation. Thanks for the info.
 » 3 years ago, # |   +2 Wow, CF servers are fast, my first hack on this submission (19791945) takes over 5 × 109 iterations and it ran in sightly less than two seconds.
•  » » 3 years ago, # ^ |   0 It's not the "extremely fast servers", but probably the O2 optimization that cut the number of iterations.
•  » » » 3 years ago, # ^ |   0 What O2 optimization ?
 » 3 years ago, # |   +21 Had no idea Tries were this standard, so many people solved D.
 » 3 years ago, # | ← Rev. 3 →   0 I think my rating will drop to below 900 :/
•  » » 3 years ago, # ^ |   0 you guessed right
•  » » » 3 years ago, # ^ |   0 It is ok I am only doing this for fun for now.
•  » » » » 3 years ago, # ^ |   0 you mean you get fun by solving 0 problem?
•  » » » » » 3 years ago, # ^ | ← Rev. 4 →   0 I solved 2 actually just couldn't get them right within the contest time and 2A got rejected during testing(WA on test 41) because I didn't set precision to 7 digits after decimal point.
•  » » » » » » 3 years ago, # ^ |   0 well try to upsolve the rest 3 as well. It won't help unless you gradually develop some new techniques, will it ? :/
•  » » » » » » » 3 years ago, # ^ |   0 Yeah, I am learning some basic algorithms and doing problems on SPOJ, I only started doing this regularly from a month ago, at the moment I don't think I can solve C-E.
 » 3 years ago, # |   0 Anyone else think that the time limit for E was a bit too strict?
•  » » 3 years ago, # ^ | ← Rev. 2 →   +26 I don't know but if the target was split O(q(n + m)) and then it was not strict.
•  » » » 3 years ago, # ^ |   +6 There was a solution in q(n+m)? Wow... at least I managed to implement a working treap for the first time
•  » » » » 3 years ago, # ^ |   0 I wrote the same O(q*n*log n) with treaps as well. I think it was a bit too tempting to come up with some online algorithm that uses treaps of segment trees to fairy solve this problem.
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   +16 Yep, The good intuition to this solution represents the structure as beads that connecting by a thread with a neighborhood, in this case, you can split O(n + m) thread and connect it by another way.
•  » » » » » 3 years ago, # ^ |   +3 So, basically a quad-linked list? Thanks!
•  » » » » » » 3 years ago, # ^ |   +13 Yes
•  » » » » » » » 3 years ago, # ^ | ← Rev. 3 →   0 any full description of "quad-linked list"? is it smth like sqrt-decomposition of list? Google gives smth strange.Thanks in advanceTried treap but TA11:(UPD just wondering how the hell is possible to distinguish fast c++ qmlog(n) from slow java qm...
•  » » » » » » » » 3 years ago, # ^ |   0 Basically there is set of nodes representing the fields of the matrix. Each node is connected via a pointer to its upper, lower, left and right neighbor.
•  » » » » » » » » » 3 years ago, # ^ |   0 Statement that rectangles doesn't share common side makes so much more sense now ;) Actually I'm surprised that not much people came up with this solution, as it isn't complicated at all.
•  » » » » » » » » » 3 years ago, # ^ |   0 Ok thanks, already read it in solution, seems to me that coded something similar once
•  » » » » » 3 years ago, # ^ |   0 Thanks! So trivial yet so hard to think!
•  » » » 3 years ago, # ^ |   +16 What about this O(QNM) solution?http://codeforces.com/contest/706/submission/19802812I know, this solution utilizes the fact that modern machines are very good at copying large amounts of memory around.This just proves that the time limit itself, although the problem and its solution are very interesting, doesn't make any sense.
 » 3 years ago, # |   +1 This round is totaly interesting :) Although I couldn't solved problem D (wish that i could learn Trie earlier) but today it is fine!
 » 3 years ago, # |   +8 That moment when ur solution is in queue for more than 15 min. And On top of that you get a verdict as a wrong answer . Ruins everything :(
 » 3 years ago, # |   0 i always thought that the feature of rejecting the exact same submission was useless. after this contest i really appreciate it. it saved lots of precious 50-points as i had to submit 10 solutions to see one of them got into the queue.okay really codeforces what the fuck is happening!
 » 3 years ago, # | ← Rev. 2 →   -27 i get WA after 30 min from submit ! :) it should be unrated like Eran Contest
•  » » 3 years ago, # ^ |   -6 yup...i got WA after 20 min of Submit.
•  » » » 3 years ago, # ^ |   0 Same Here :(
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +3 Yeah now lucky people who didn't get Wrong answer will vote down this comment :)
•  » » » » 3 years ago, # ^ |   +2 if someone solved their solution correctly at one go, it doesnt make them lucky, it makes them more aware and smart
•  » » » » » 3 years ago, # ^ | ← Rev. 3 →   0 they are smart because they didn't get WA ? they are smart yeah but they are lucky too because they don't wait 20 min and lose many points and resubmit solution also lose 50 point :) in 20 min i can solve B instead of fix small mistake in 'A' problem smart only isn't enough
•  » » » » » » 3 years ago, # ^ |   0 Just solve all problems and your rating won't decrease:D
•  » » » » » » » 3 years ago, # ^ |   +3 u are so genius bro congratulations :D
 » 3 years ago, # |   0 Does anybody know why my submission 19801619 got compile error? Thank you!
 » 3 years ago, # |   +6 the queue was so long in the start of this contest please consider this.
•  » » 3 years ago, # ^ |   0 كول خرا
 » 3 years ago, # |   +5 Who else has used graph to solve C?
 » 3 years ago, # |   0 I spent an hour implementing D using multiset, so I guess this will be my motivation to learn trie finally :D
•  » » 3 years ago, # ^ |   0 Do you mean that you did it using standard multiset? Can you post a link please
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 http://codeforces.com/contest/706/submission/19810298 It should work, I tested it with a bruteforce solution and there was no difference, but of course I might be wrong. Edit : It works if anyone wonders :)
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   0 Can you light upon your solution? Your approach looks interesting. Implementing Trie is too mainstream for this problem. :P
•  » » 3 years ago, # ^ |   0 exact same thing happened with me .... difference being that I could debug my solution after the contest ended :(
 » 3 years ago, # |   0 I see many solutions who got WA#5 in problem D, like me. Good round!
•  » » 3 years ago, # ^ |   0 WA in #5 is probably from not considering that 0 is always in the set.
•  » » » 3 years ago, # ^ |   0 Yeap, you're right.
 » 3 years ago, # |   +4 I knew that the problem D could be solved by using Trie but I failed to implement it ;(
•  » » 3 years ago, # ^ |   0 same here...I had bugs in my remove number function...got it working 5 minutes after the contest ended. :(
•  » » 3 years ago, # ^ |   0 This is the second time I know that a problem can easily be solved by trie but failed to implement it. I think tries are tricky to implement so people must have coded them once and use their own code every time I guess.
 » 3 years ago, # |   0 Solved D 5 minutes after the contest ended! I'm too slow!
 » 3 years ago, # |   +17 I think, this contest should be RATED.
•  » » 3 years ago, # ^ |   0 it is unfair towards people who waited for 20 minutes for each problem
 » 3 years ago, # |   +13 I quite don't understand what everyone is so distraught by long queue of +/- 15 minutes. Every major competition. APIO 2016, CEOI 2016, JBOI 2015 all are really famous for their judging fuck ups. Why does CF need to make this unrated simply to prevent decrease of people's ratings, when such major competitions often end up deciding people's future and college etc.
•  » » 3 years ago, # ^ |   +8 The competitions you mentioned don't have time penalties. When there are fuck-ups in our local onsite contests, we usually blame the system saying to the organizers that in respectful contests like Codeforces rounds such things would be considered very wrong and wouldn't be allowed. Codeforces should stay an example for a good platform with good contests.
•  » » » 3 years ago, # ^ |   0 I'm pretty sure every platform is allowed to mess up once in a while. The first time they did, they made the contest unrated. Fair enough.About time penalty not actually mattering, really? You didnt feel that maybe if there wasn't the 1 submission per 5 minutes thing in APIO, your score would have not been affected?
 » 3 years ago, # |   +1 It was a really bad idea to make Eran's contest unrated. Cuz now a lot of people are upset with the system's speed and it would be kind of unfair to leave it as it is.
 » 3 years ago, # | ← Rev. 2 →   +6 E was very similar to problem G from Petrozavodsk Winter 2012 (standings)(the problem is great anyway)
 » 3 years ago, # |   +7 I think this contest should be rated. Judge lags were not bad than past contests.umm... I wonder how to hack Q1. How did you hacked Question No.1?
•  » » 3 years ago, # ^ |   0 of course because u didn't get WA :D !!!
•  » » » 3 years ago, # ^ |   0 No... This contest is much better than Round #365.
•  » » » » 3 years ago, # ^ |   0 yeah but the same problem ' long queue ' no metter if it better or not
 » 3 years ago, # |   0 Pretest Passed at one shot 3 seconds before the contest ends. Am I the latest to submit ? :P ![](https://imgur.com/a/v2raK)
 » 3 years ago, # |   -60 Making this round rated proves how unserious this website is
 » 3 years ago, # |   0 Submissions are being judged after 20 minutes. I came to know about my run time Error of question after 20 minutes. This round should be unrated. Many people would have been affected by this.
 » 3 years ago, # | ← Rev. 4 →   0 edit: nvm
 » 3 years ago, # |   0 What is the approach for D?
•  » » 3 years ago, # ^ | ← Rev. 2 →   +1
•  » » » 3 years ago, # ^ |   0 Wow! I never imagined a trie can be used in this problem
•  » » » » 3 years ago, # ^ |   0 Same approach :D. I finished debugging my sol two minutes late though.
•  » » » » » 3 years ago, # ^ |   0 At least you knew what to do!!
 » 3 years ago, # |   0 Any idea what Test 41 in A is? I assume it's one of the tests that was used to hack a bunch of solutions in A.
•  » » 3 years ago, # ^ |   +1 Precision Error,
•  » » 3 years ago, # ^ |   0 One of my friend that has almost same solution but used float instead of doubles got WA on this test.
 » 3 years ago, # |   +3 "In queue" for 15 minutes after submitting the question, has becomes a permanent feature of codeforces :(
 » 3 years ago, # |   +8 Make it rated please i have solved A and B under 20 minutes. and i am happy to do that !
•  » » 3 years ago, # ^ |   0 19793914 00:20:53 Hazemzz A - Beru-taxi Java 8 Accepted 20 mins, 53 seconds is not ''under 20 minutes'' :)
•  » » » 3 years ago, # ^ |   +16 Make it rated please i have solved A and B under 20 minutes 54 seconds. and i am happy to do that ![user:latvian]
 » 3 years ago, # |   +4 Nice contest! Brief statements. Unfortunately, finished D solution two minutes too late :/. Thoroughly enjoyable nonetheless.
 » 3 years ago, # | ← Rev. 2 →   0 In Problem C. I marked my dp[100005][2] with INF as 10e15 it gave a run time error. But when i use INF as 10e14 it works. Language used C++. Can anyone explain ? Thank you.Edit1 : It's behaving in a weird manner. Sometimes i get correct answer but sometimes i get run time error in custom invocation. I will update once i get to know the reason behind it.
•  » » 3 years ago, # ^ |   0 There are 10^5 numbers, so if you add 10^15 10^5 times, you get long long overflow. Maybe that's why
•  » » » 3 years ago, # ^ |   0 I was not adding them actually.I just initialised my dp table with INF. After that i was taking min of responses. It gave run time error on pretest1 itself. I later checked on custom invocation with 10e14 it works.
•  » » 3 years ago, # ^ |   0 In c++ upto 1234567890123456789 is accepted(>1e18)..then its not possible that 1e15 will give any kind of runtime error :D Check again may be some kind of segmentation fault error must be there.
•  » » » 3 years ago, # ^ |   0 I used 1e15 keeping those 1e18 limits in mind only. Later i tried in custom invocation 1e14 works but 1e15 gives "runtime error: exit code is -1073741819"
•  » » 3 years ago, # ^ |   -10 Always better to keep it as -1 and then add additional checks :). I have made the same mistake before.
•  » » » 3 years ago, # ^ |   0 Agreed.
 » 3 years ago, # |   0 Waited for 20 minutes to get WA, why codeforces is so slow again? Will it be rated?
 » 3 years ago, # | ← Rev. 2 →   0 Only I get #WA41 on A?
•  » » 3 years ago, # ^ |   +5 "Print a single real value — the minimum time Vasiliy needs to get in any of the Beru-taxi cars. You answer will be considered correct if its absolute or relative error does not exceed 1e-6." cout just give the answer that its absolute or relative error does not exceed 1e-5.
•  » » » 3 years ago, # ^ |   +14 Fuck that shit, Im out
 » 3 years ago, # | ← Rev. 4 →   +3 A solution for D without using trie (though it hasn't passed the systests yet). Let's store all numbers in STL multiset. To perform the third operation, we can find y that gives maximal xor going from the leftmost bit to the rightmost. Given the 10^9 constraint for x, 30 to 0 is enough. Let's say we know some binary prefix of the answer, and that a number in multiset with such binary prefix exists. If x has 1 in this bit, we can just find the the minimal y with such prefix (using multiset.lower_bound()), and if it has 1 in this bit, then add it to the answer. If x has 0 in this bit, we can find lower_bound(answer | (1 << i)) and see if it does exist and isn't greater than answer + (1 << (i + 1) — 1), in order to guarantee the existence of such prefix in multiset, then add to the answer.
 » 3 years ago, # |   0 Is this solution for div 2-b correct http://pastebin.com/jrpYFphS, I lost so much time in contest because I was in queue, and now I can't submit a solution.
•  » » 3 years ago, # ^ |   0 Just use upper_bound. No need to do all this stuff. :) Solution
 » 3 years ago, # |   0 It will be unfair towards Eran who has created good problems, if this contest is rated
•  » » 3 years ago, # ^ |   +1 the lag in this contest wasnt as bad as the lag in the contest you are referring too, at most it was ~20 min, you could have moved on to some other question while it was in the queue
•  » » 3 years ago, # ^ |   +8 No it won't. Just enjoy solving the good problems and stop complaining. The queue wasn't long enough for the contest to become unrated.
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 Who cares about rate, it's all about learning new things...
 » 3 years ago, # | ← Rev. 2 →   0 I got a weird WA61 on problem C. I am sure about the idea, and probably the WA is because of checking whether we can have an answer. Why is my check wrong?I've changed the way for checking the possibility to have an answer and now have an AC. Does anybody know why did this happen?
 » 3 years ago, # | ← Rev. 4 →   +48 O(nmq) solution for E. AC in 2464 ms =)Can be improved to 2121 ms and 1669 ms with SSE.
•  » » 3 years ago, # ^ | ← Rev. 2 →   +74
•  » » 3 years ago, # ^ |   0 I did it, too =)http://codeforces.com/contest/706/submission/19808842
•  » » 3 years ago, # ^ |   0 Have you tried combining your second solution with Duff's device?
•  » » » 3 years ago, # ^ |   0 That will not work for my cycle, because i have not only unrolled it, but also grouped some operations.
•  » » 3 years ago, # ^ |   0 Nice. And here I coded standard treap hoping it'll pass. Turns out 12 seconds is the least it needs for my implementation :/
 » 3 years ago, # |   0 Can we expect editorial today itself??
 » 3 years ago, # |   0 will there be an editorial ?
 » 3 years ago, # | ← Rev. 3 →   0 Here was my approach to D. It is easy to keep up with the set by using std::set and std::map to count the multiplicities.The real deal is how to deal with the query ?.First, change the given number to binary. We notice that we can take the high-value digits greedily.Therefore, we do the following. We set X as the optimal number in the set. Iterate through the bits 29 0. If the binary form of the given number is 0, we want 1 there. If not, we want 0 there. If there are no numbers in the set that satisfies this, we would have to go with alternate path.Here's an example.Assume that 111011, 011000, 101000, 000010 is in the set, and the original number is 001101. We want the first bit to be 1. Indeed, there are two such numbers — they are in the interval [32, 64). How do we check that there are numbers in that interval? By using lower_bound!So we chose [32, 64). Now for the second bit we want 1 as well. Such numbers are in the interval [48, 64). We see that there is one. We want 0 to be the third bit, and such numbers are in the interval [48, 56). However, there are no numbers in that interval! Therefore, we would have to go with the third bit 1.Continue this, and we would have our optimal X. Now compare ORIGIN XOR X and ORIGIN and return it. Complexity is
•  » » 3 years ago, # ^ |   0 I thought of this, but I couldn't convince myself that this is correct :/
•  » » 3 years ago, # ^ |   0 Wow! Great idea! I thought about greedy solution but I could not implement it. As for me, you solutuion is better then in ediorial. Thank you!
•  » » » 3 years ago, # ^ |   0 Where is the editorial???
 » 3 years ago, # | ← Rev. 2 →   0 Kindly have a look at this test case generation program for Question 2 . I was unable to figure out why it was showing (invalid input verdict ) when I tried to hack this submission . (http://codeforces.com/contest/706/submission/[submission:19798157])My code : #include using namespace std; int main() { int n=99999; cout<
•  » » 3 years ago, # ^ |   0 I think in hacking, you have to add a new line at the end of input
•  » » » 3 years ago, # ^ |   0 I tried that also but it did'nt work out . test
•  » » » » 3 years ago, # ^ |   0 There would be a extra space after printing values of each array in the above link but not in the original comment. Checker is strict for hacking maybe.
•  » » » » » 3 years ago, # ^ |   0
•  » » » » » » 3 years ago, # ^ |   0 In both there is extra space at the end of second line.
•  » » » » » » » 3 years ago, # ^ |   0 Thanks I found my mistake .
•  » » 3 years ago, # ^ |   0 You say there are 9999 values, but only print 9998
•  » » » 3 years ago, # ^ |   0 No I have printcout<
•  » » 3 years ago, # ^ |   0 For hacking you have to give input, not input generating program.
•  » » » 3 years ago, # ^ |   0 No , If the inputs are more that 250 Kb size you are required to write a generator program .
•  » » 3 years ago, # ^ |   0 Last line should be cout << 2 << endl;
•  » » » 3 years ago, # ^ |   0
•  » » 3 years ago, # ^ | ← Rev. 3 →   0 Extra space
 » 3 years ago, # |   0 in C anyone got WA in test case 18?
•  » » 3 years ago, # ^ |   0 Me too, I set oo = 1e9, however, it should be 1e18.
•  » » 3 years ago, # ^ |   0 Turns out i was using INT_MAX for the max value (initialized value) for the dp table, but the sums can sum to be greater than INT_MAX!i should have used 1<<60! such a silly mistake
•  » » 3 years ago, # ^ |   0 Hope we will never meet that mistake again.
 » 3 years ago, # | ← Rev. 2 →   +4 nice contest ,but slow system testing :P hoping to get high ratings
•  » » 3 years ago, # ^ |   0 Sum of lengths of strings <= 100000.
•  » » 3 years ago, # ^ |   0 The sum of lengths of all strings is at most 10^5, not the length of every string. So the worst case should contain all the strings with length , something like 315.
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 Total length of all string is 1e5. Incase n = 1e5, length of each string is just 1. Totally it is O(n).
•  » » 3 years ago, # ^ |   0 It was given in the question that the total length of the strings won't exceed 10^5.
•  » » 3 years ago, # ^ |   0 Why did you change your comment? Nobody answered your question so far.The number of operations is linear because every string is compared a constant number of times.
 » 3 years ago, # |   +23 Thank you guys for making this awesome contest.The difficulty of problems is moderate for Div.2 contestants and have great and beautiful "solved" distribution.I kept thinking and implementing the whole contest.It's really exciting and fun.Some personal experience: I got 2 RE on D for missizing the trie node pool and got 1 WA on C for a typo.When I start to handle E, I first thought to cope with it by splay tree(considering the difficulty of previous rounds) and failed to finish it.Right after the contest I figured out a better way(maintaining the position of original elements and do some interval add/distract, which can be completed in O(n) time because there is no online requests).Long queue appear again in this contest.I guess this is caused by problem A.Maybe the special judge part in A make the judging machine laggy.This contest is made by and for Div.2, this is awesome.Although the difficulty may seems lower than previous Div.2s(finish 3 and you and done, finish 4 for a high rank,finish all to go Div.1 directly), but it is really enjoyable for Div.2 contestants.Hope you guys can make more great contests.
•  » » 3 years ago, # ^ |   +5 I don't hate this contest. I'm just expressing my bad opinion about the problemset, which I didn't enjoy, authors did their best anyway. I do not consider this contest as "good". Here's a yellow point of view:-A was okay, like normal A-B was such a standard task... -C yet another DP with same pattern. There was even a pretty similar problem on CF once. -D come on, "code a trie" problem. There are many such problems in the internet. Seriously, even "find maximum xor" typed in Google would probably result in finding the solution immediately. -E that was a fun one. Nah, just kidding :P If coding N treaps is a model solution, then wonderful problem 10/10. MrDindows did something awesome, check it out! I'm not saying this contest was bad. But IMHO this contest should have been an Educational Round.
•  » » » 3 years ago, # ^ |   0 C yet another DP with same pattern. There was even a pretty similar problem on CF once. Which one?
 » 3 years ago, # |   +3 This problem set is so much interesting. Really I enjoyed it to much.
 » 3 years ago, # | ← Rev. 2 →   +3 Somewhat structured and verbose code for D: http://pastebin.com/Md2EtNXF (submission)
 » 3 years ago, # | ← Rev. 2 →   0 Can someone tell me why my solution to C (java) timed out?I saw some other recursive solutions also passing, so did I make some mistake in the implementation?Here's the code : 19801924Thanks.Edit : I got my mistake.
 » 3 years ago, # |   0 Someone can help me? In problem D, I'm use basicly pointers, in my computer it is ok, but in CodeForces gives Runtime Error.Submission
•  » » 3 years ago, # ^ |   0 I used only opinters, too. Check this code.
 » 3 years ago, # |   0 Why my all solution change to 'skipped' and I out of competition ?
•  » » 3 years ago, # ^ |   0 It happens when someone cheats.
 » 3 years ago, # |   0 Why I get different answers between custom invocation and problem test?In 19790402 I got WA on test 79, However, I thought I got the correct answer when I used Custom Invocation.What the problem is???I passed this problem by replace %ld with %d, but I do want to know Why I get different answers between custom invocation and problem test?By the way, I'm glad to know how to cause this WA, since I thought there is no different between %ld and %d in GNU G++11 5.10 :)
 » 3 years ago, # |   +1 Got 141 points, wow!
 » 3 years ago, # |   0 中文
 » 3 years ago, # |   0 Thanks for such a nice contest :)
 » 3 years ago, # |   0 where is the problem set ?
•  » » 3 years ago, # ^ |   0 here.