### Zlobober's blog

By Zlobober, 4 years ago, translation, ,

Hi everybody!

Glad to tell you that tomorrow on 9:05 UTC there will be Codeforces Round #345. The round is formed of the first day of X Moscow Open Olympiad problemset with several additional problems created for this round. This round is brought to you by the scientific committee of Moscow Programming Olympiads controlled by GlebsHP, romanandreev and your humble servant, and also with a great help of fcspartakm who helped us make a complete problemset of our problems.

The round will be conducted under the standard Codeforces rules, you will be given 5 problems for 2 hours. Yes, this round is rated :)

Note that because of holding the main onsite round system testing and upsolving will be available no earlier than 12:35 UTC. Also we would like to ask you to not discuss problems in comments during the time between the end of the round and the end of the onsite competition. All comments with discussions will be removed and the most active violators will be punished. Thanks for your understanding.

UPD Sorry, the round start was moved to 9:25 UTC. It is not easy to run onsite round and Codeforces Round simultaneously!

UPD2 You may discuss the solutions! System testing will be run shortly.

UPD3 The editorial has finally appeared: http://codeforces.com/blog/entry/43677 Sorry for the delay!

• +443

 » 4 years ago, # | ← Rev. 3 →   +109 And Zlobober's serious work to get the first place in the contrib list!!Nice tag (best way to spend Monday)!! good luck;
•  » » 4 years ago, # ^ |   +30 But seriously though, who holds olympiads on Monday mornings?
•  » » » 4 years ago, # ^ |   +48 I can't imagine a better way to start your Monday.
•  » » » » 4 years ago, # ^ |   0 great minds think alike.codeforces makes my life better
•  » » » » » 4 years ago, # ^ |   +10 too bad difficult to hack!
 » 4 years ago, # |   -73 please change the contest time in this time in iran we are at school and we have Combinatorics class with Dr jamali (for informatics olympiad)
•  » » 4 years ago, # ^ |   +166 At any other contest time , someone else in the world might have Combinatorics class with Dr jamali (for informatics olympiad) . Ever think about that ?
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +136 Well, I doubt Dr. Jamali goes around giving Combinatorics classes the whole day, every day. For sure Jamali must take some time to rest, teaching must be exhausting.
•  » » 4 years ago, # ^ |   +6 It could be worse. It is going to be at 6:00 AM in my country.
•  » » » 4 years ago, # ^ |   +11 3 AM here, and school on the same day. :)
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 It is a egg pain. I didn't found another better translation hahaha
•  » » » » 4 years ago, # ^ |   0 Ohh
•  » » 4 years ago, # ^ | ← Rev. 3 →   0 Same here!!
 » 4 years ago, # |   +63 A better reason to leave Lecture :) .
 » 4 years ago, # |   +42 Russian contests are always good!Specially when this team( Zlobober + GlebsHP + romanandreev) are authors !
 » 4 years ago, # |   -121 First thank all people who prepare this contest. But i think the start time of contest is not good for iranian coder (or maybe for another coders who live in another countries too),bacause on this time we are in university... :(
•  » » 4 years ago, # ^ |   -32 oh my god!why vote negative??? :O
•  » » » 4 years ago, # ^ |   +32 because it's CF :D
•  » » » 4 years ago, # ^ |   -47 i can't believe this (O-O)!!! why???! 19 negative vote !!!for what??? -_-
•  » » » » 4 years ago, # ^ |   +49 Because every time will be good for some participants and bad for others. This time you had bad luck, other times the contest will be in good time for you and bad for others.Life is hard
•  » » » » » 4 years ago, # ^ |   -20 i just said its bad for IRANIAN coder!
•  » » » » » » 4 years ago, # ^ | ← Rev. 2 →   0 you'd better stop commenting :)))
•  » » » 4 years ago, # ^ |   +20 No matter what time they set the contest to start, it would be inconvenient for someone somewhere in the world
•  » » » 4 years ago, # ^ |   0 I can upvote your very useful comment
 » 4 years ago, # |   -66 Please postpone contest, I'm still at uni :'(
•  » » 4 years ago, # ^ | ← Rev. 2 →   +183 10 minutes delay, they did what you want :) UPD: another 10 minutes, please come home quickly
 » 4 years ago, # |   +15 Just came back from school and about to start the contest. I like these rounds with unusual times because I can actually compete on weekdays. Normally, they're hosted at 10 pm or 11 pm in my country's time :(
•  » » 4 years ago, # ^ |   +14 I'm agree with you :)
•  » » » 4 years ago, # ^ |   0 I agree*
•  » » » » 4 years ago, # ^ |   +125 I am disappoint.
•  » » » » » 4 years ago, # ^ |   +77 You're Errichto.
•  » » » » » » 4 years ago, # ^ |   +55 And you're not.
•  » » » » » » » 4 years ago, # ^ |   +45 I'm FamIsProud.
•  » » 4 years ago, # ^ |   +7 Arguably 10 or 11pm is better than 3am :P
 » 4 years ago, # |   +459 Rating!? Oh no! Sad end for my cat...
•  » » 4 years ago, # ^ |   0 My rating's just like mountains... :(
•  » » » 4 years ago, # ^ |   +41 Mine looks like shit hahaha
 » 4 years ago, # |   +7 the timing of the contest is probably one of the best timings for competitors from Korea; it's 6pm; an hour or two from now (so, 7pm or 8pm KST) would be ideal.
•  » » 4 years ago, # ^ |   0 It's 3am on a weekday in the US :P Oh well, better than 10am — at least I have a chance to participate. Looked like it got bumped back 10 minutes though.
 » 4 years ago, # |   +29 delayed for 10 mins
•  » » 4 years ago, # ^ |   +53 delayed by 20... :(
•  » » » 4 years ago, # ^ |   -7
•  » » 4 years ago, # ^ |   +19 I'm disappointed too. It was just that I would complete the contest and go to school, now I have either to skip the first class or solve for only hour and a half :(
•  » » » 4 years ago, # ^ |   +16 Why are you disappointed? you have a reason to skip the first class now :D
•  » » » » 4 years ago, # ^ |   +17 You might want to tell this to our history teacher :)
•  » » » » » 4 years ago, # ^ |   +8 History is a lie, Contest is real :D
•  » » » » » 4 years ago, # ^ |   +3 You want to attend history class! what's the matter with you :Dwhen I was in school I always skip history classes even if there's no contest :D
•  » » » » » » 4 years ago, # ^ |   +160 We have a badass among us
•  » » » » » » » 4 years ago, # ^ |   0 Really you have badass among your school?
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →   0 If it were about a Math or Info or Physics class, maybe he would have been more rational, but in this case, man, I'm sorry for you :))
•  » » » » » 4 years ago, # ^ |   +10 All of you didn't understand. My history teacher will surely kill me for being absent(it's sad because I'm a math/informatics competitor, history is one of my worst subjects :)) ).
•  » » 4 years ago, # ^ |   -40 暴走漫画。。。。。
•  » » » 4 years ago, # ^ |   0 no zuo no die
•  » » » 4 years ago, # ^ |   0 Hey guy ! why so many people got unhappy with you !
•  » » » » 4 years ago, # ^ |   0 Because it's CF :D Maybe most of the people who got unhappy with him is Chinese. Why? I don't know QwQ
•  » » » » 4 years ago, # ^ |   -10 All are unhappy with anyone comments in language different from English..
•  » » » » » 4 years ago, # ^ |   -9 I'm sorry.I don't konw it before.
•  » » » » » » 4 years ago, # ^ |   0 "know", not "konw"
•  » » » » » » » 4 years ago, # ^ |   +9 My English is not good...
 » 4 years ago, # |   +19 Guys, I must go to school today ;)
•  » » 4 years ago, # ^ |   +4 Same — could've gotten 20 mins more sleep. Some of my classes probably are unimportant enough I can use them as nap time though :) Bets it will be delayed 30 mins?
 » 4 years ago, # |   0 Delayed ! :(
 » 4 years ago, # |   +72 5pm in China. Hungry... Please start...T T
•  » » 4 years ago, # ^ |   +4 but it's so nice to take part in the contest during the day for Chinese=w=
•  » » » 4 years ago, # ^ |   0 exactly.
 » 4 years ago, # |   +15 I haven't slept all night last night and Just got back from my university to participate in this round :D I hope there will be interesting problems.. I am feeling like being Div1 for a while :p
•  » » 4 years ago, # ^ |   0 such high , much wow all the best
•  » » 4 years ago, # ^ |   +3 For me writing after a sleepless night is premise for falling rating=(. Hope it is not your case, good luck
•  » » » 4 years ago, # ^ |   +1 Well... I'm not in my best shape.. but I need to get used to coding in stressful environments, because I am preparing for ICPC WF this year, which is my final year as a contestant :((any way I only hope the problems are enjoyable that's all :D
•  » » 4 years ago, # ^ |   0 I'm feeling the same as you and dropped from #150 to #800 due to int overflow in the last contest T.T
•  » » 4 years ago, # ^ |   +18 I'm actually glad for the delays :D now I can change my clothes and get into my comfortable pajamas, drink a cup of tea, as well as write this comment :D :D
•  » » 4 years ago, # ^ |   +3 you did it :)
•  » » » 4 years ago, # ^ |   +1 Yes! Thank you ^_^I Also got my best rating so far with 1944 points :D
 » 4 years ago, # |   +12 Why are you delaying the start time? u.u
•  » » 4 years ago, # ^ |   +13 Probably due to Onsite Delays? Just a random guess >(
•  » » » 4 years ago, # ^ |   0 onsite started much earlier, because duration of onsite is 5 hours
 » 4 years ago, # |   0 10min delay?!We can, we do, we practice :(
 » 4 years ago, # |   0 Another 10 minutes? :O :/
 » 4 years ago, # |   -9 Another 10 mins delay. Very organized,
 » 4 years ago, # |   +22 On one hand if I complain about timings, Russians will downvote me, on the other, if I don't and still participate I'll miss my lunch(and get downvotes). Hmmm.....what to do
•  » » 4 years ago, # ^ |   +3 Keep calm and code :p
•  » » 4 years ago, # ^ |   -10 I'll have lunch lol. Virtual contest ftw :D
 » 4 years ago, # |   +1 My first time to participate a CF round sync w/ onsite.It's cool!
 » 4 years ago, # |   +4 Should I compete? Because I am in a Lab class and my teacher gave me an "1 hour break!" for completing the tasks early.
 » 4 years ago, # |   0 Waiting for the next delay :P
•  » » 4 years ago, # ^ |   0 Exactly.
 » 4 years ago, # | ← Rev. 2 →   -10 what's wrong with the hacking? nothing shows up when i try to hack (sorry for my vulgarity on my previous post).
•  » » 4 years ago, # ^ |   -12 Its because you shouldn't be hacking. Solve problems, go go go!
•  » » 4 years ago, # ^ |   +10 I have a similar problem. Pretests passed but cannot lock! Neither is it showing on the dashboard.
•  » » 4 years ago, # ^ |   0 But mine is working fine..
•  » » 4 years ago, # ^ |   -22 It was unuvailable for ~10 minutes. It affected all the participants, so all of you have been in the same conditions. Sorry about it.
•  » » » 4 years ago, # ^ |   +27 Wow.It seems that there are many guys who are unsatisfied with the long time of waiting.
•  » » » 4 years ago, # ^ |   +4 I wonder, who downvoted the boss???
•  » » » » 4 years ago, # ^ |   +9 Some brave and cute guys.
•  » » » » » 4 years ago, # ^ |   +1 cute you are=w=
•  » » » » » » 4 years ago, # ^ |   0 We are all cute.=￣ω￣=
•  » » » » » 4 years ago, # ^ |   0 WOW! How cute you are!
•  » » » » 4 years ago, # ^ |   0 doesn't matter it seams every minute it resets to zero :\
•  » » » » » 4 years ago, # ^ |   0 some mysterious power...
•  » » » » » 4 years ago, # ^ |   +6 maybe mike is giving himself upvotes, lol
•  » » » » » » 4 years ago, # ^ |   0 Be careful with what you said.Maybe there's something happening to yo.
•  » » » » » » » 4 years ago, # ^ |   0 mike is free to do anything here, did you know that?
•  » » » » » » » » 4 years ago, # ^ |   0 We all know that.But I am careful to say it out.
•  » » » » » » » » » 4 years ago, # ^ |   +4 don't be afraid of downvotes, be honest :)
•  » » » » » » » » » 4 years ago, # ^ |   -17 To be honest,I give him a downvote.
 » 4 years ago, # |   +3 First time i solved C in contest . guess what i solved B and C. and 4 WA on A and could not get AC. Awesome problemset :)
•  » » 4 years ago, # ^ | ← Rev. 2 →   +13 I think it is because of unclear statement. Almost sure it is the case if you get WA on pretest #7.
 » 4 years ago, # |   -12 Can somebody explain me This ? Whats wrong with my generator .
•  » » 4 years ago, # ^ |   +4 This link takes everyone to their own hack section, not yours.
•  » » » 4 years ago, # ^ | ← Rev. 4 →   -6 sorry LINK
•  » » » » 4 years ago, # ^ |   +8 Did you even compile it? Line 20 is missing a semicolon.
•  » » » » 4 years ago, # ^ |   0 What does this line do ? o.O printf("0 0\n",ans,ans);
•  » » » » » 4 years ago, # ^ |   0 Just print 0 and 0, nothing to do with 2 "ans"'s
 » 4 years ago, # |   +9 The statment for the second task is pretty clear, but again I spet 30 minutes to understand problem of the task :D
 » 4 years ago, # |   0 we should wait till 12:35 for system testing,right
 » 4 years ago, # |   +10 when will system testing start?
•  » » 4 years ago, # ^ |   +15 In an hour from now as I understand (15:35 MSK).
 » 4 years ago, # | ← Rev. 2 →   +36 We kindly ask you not to discuss problems or solutions since the onsite round is still running. We will notify you when it will be allowed (approximately in 2 hours). Thank you!Мы ещё раз просим участников не обсуждать задачи и решения пока не закончится основной тур олимпиады. Мы сообщим, когда станет можно (приблизительно через 2 часа). Спасибо!UPD Thank you for your understanding! You may now discuss problems and solutions. System testing will be run shortly.UPD Спасибо за понимание! Теперь вы можете обсуждать задачи и решения. Системное тестирование скоро начнётся.
•  » » 4 years ago, # ^ |   +21 Two questions:When will start testing ?Why disscussing is so important, when everybody can see codes from other participants ?
•  » » » 4 years ago, # ^ |   +2 Exactly.. I guess that the onsite contestants cannot have any kind of communication with the outside world..So why bother stop discussions here? I can't see the point in doing so :\
•  » » 4 years ago, # ^ |   +41 I can see the other's solutions.
•  » » 4 years ago, # ^ |   +5 Any updates on system testing now ?
 » 4 years ago, # |   +10 i still do not understand the problem statement for division 2 D, but judging from number of people who solved the problem, perhaps it's just me who is confused about the problem statement.
 » 4 years ago, # |   +112 Seriously? -_-
•  » » 4 years ago, # ^ |   0 So, were there edits in the problem text?
•  » » 4 years ago, # ^ |   +30 Let me clarify this. We actually received a question pointing to the typo in the statement (the word "has" was obviously an extra word there) and we fixed that typo. After 1.5 hours of contest we received the second question about the mistake in this problem and we didn't even think that you are talking about that mistype. After all, it was a small typo that doesn't affect the understanding of the problem, and we fixed it 1.5 hours ago, we almost forgot about it.Of course we didn't have any intention of lying to you or whatever.
•  » » » 4 years ago, # ^ |   +4 Okay, thanks .
 » 4 years ago, # |   +7 What is Compilation error? I lost much time because of that...
•  » » 4 years ago, # ^ |   +24 Are you kidding?
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 I had not gotten Compilation error and today is first in Codeforces. So i don't know Compilation error well.I only know this.struct A ={a,b} => Compilation error A.x = a, A.y = b => Correct
•  » » » » 4 years ago, # ^ |   0 {a,b} this would work with std::pair not with struct
•  » » » » 4 years ago, # ^ |   0 There is no = operator by default for custom structs.
•  » » » » » 4 years ago, # ^ |   0 You are wrong. It can be auto-generated by compiler.
•  » » » » » 4 years ago, # ^ |   0 Yes, there is. In C++11.
•  » » » » » » 4 years ago, # ^ |   0
•  » » » » » » » 4 years ago, # ^ | ← Rev. 3 →   0 You didn't write constructor for two int values. So compiler doesn't know what to do. Click
•  » » » » » » » 4 years ago, # ^ |   0 The problem is that you've written you own (empty) constructor for your struct. If you'd write no constructor, just: struct smth{ int x, y; }; it will work.
•  » » 4 years ago, # ^ |   +33 Candidate master asking about Compilation error >.<
•  » » 4 years ago, # ^ |   +5 Ya.. Me too..!! And can you believe, they are asking us to code a solution.!!! I lost so much time in that.!
•  » » 4 years ago, # ^ |   +5
 » 4 years ago, # |   -8 A bit difficult for me.But I'm sure I can do better.hard work will pay off!
•  » » 4 years ago, # ^ |   0 Also!I'm not in my best condition. I got Wrong answer 2 times in A and C,and 1 in B. Oh my god!I lost 250 point! Even more...the Internet shut down in the contest.
•  » » » 4 years ago, # ^ |   0 victory and defeat are parts of life.As long as we work hard,we will have a good mark in the next contest.We can do it
 » 4 years ago, # |   +2 first time take part in div 1 =w=
•  » » 4 years ago, # ^ |   -15 Ah, Me too ^v^
 » 4 years ago, # |   0 Had someone div2 C WA 3? Can't understand where is the problem.
•  » » 4 years ago, # ^ |   0 Did you check that your code does not count any pair twice?
•  » » » 4 years ago, # ^ |   0 i did
•  » » 4 years ago, # ^ |   0 Int can't afford the limit. so you should use long long to record the answer.So did you check it?
•  » » 4 years ago, # ^ |   0 here is my code http://pastebin.com/hs3H83qJ, I just gonna die waiting sys tests
•  » » » 4 years ago, # ^ |   0 ohhh, now I've got it. I counted all copies with same y, and then decrease the answer as they all been at same poit.
 » 4 years ago, # |   0 Are you going to upload the editorial after the official contest?
 » 4 years ago, # |   +3 I Can't Wait... When will the Final test...
•  » » 4 years ago, # ^ |   0 Beresta said:In an hour from now as I understand (15:35 MSK).
•  » » 4 years ago, # ^ |   0 It's in the announcement: "Note that because of holding the main onsite round system testing and upsolving will be available no earlier than 12:35 UTC."
 » 4 years ago, # |   +72
•  » » 4 years ago, # ^ |   +4 What is reason that we are still wating.
•  » » » 4 years ago, # ^ |   +4 'the reason'.I'm sorry.
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   +12 Protip: you can edit your comments by clicking the button that says "Edit" (surprising isn't it)
•  » » 4 years ago, # ^ |   0 why are you waiting? you didn't participate as I can see.
•  » » » 4 years ago, # ^ |   0 You saw wrong, pal.
•  » » » » 4 years ago, # ^ |   0 I saw your submission history and found no submissions for this contest. strange!
•  » » 4 years ago, # ^ |   0 available NO EARLIER than 12:35 UTC...Only GOD knows how much do we have to wait.
•  » » » 4 years ago, # ^ |   0 It's 12:52 UTC
•  » » » » 4 years ago, # ^ |   0 The haven't promised when the system testing is...
•  » » 4 years ago, # ^ |   0 It's because of the onsite contest Be patient X_O
•  » » 4 years ago, # ^ |   0 Quite funny picture...
 » 4 years ago, # |   +122
 » 4 years ago, # |   -119 Round must be made unrated. We couldn't hack or lock solutions for ~10 minutes.
•  » » 4 years ago, # ^ |   +26 Seriously ??? unrated because of 10 minutes not able to hack???
•  » » 4 years ago, # ^ |   0
•  » » 4 years ago, # ^ | ← Rev. 5 →   0 .
•  » » » 4 years ago, # ^ |   +4 Believe that you'll solve more problems in next contest!
•  » » » » 4 years ago, # ^ |   0 Right. :)
 » 4 years ago, # |   -6 everybody should give a chance to submit the problems that went wrong in pretest as system test is not running. just asking
 » 4 years ago, # |   0 Hope to start system test today..
 » 4 years ago, # |   0 Why do codeforces problems differ so much in nature from ICPC problems? I think ICPC problems are too hard to think :/
•  » » 4 years ago, # ^ |   +1 Not really... You should compare ICPC problems to Div1 contests. and both are pretty darn hard :D I believe Div2 contests are comparable to easy regionalsYou should also consider teamwork in ICPC and much longer contest time (5 hours). This means more problems can be solved.. So can you see why it requires harder problems to make a good ICPC contest?
•  » » » 4 years ago, # ^ | ← Rev. 3 →   0 How effective do you think Codeforces problems are for preparing for the ICPC? Am I better off focusing more on solving on SPOJ, UVa, etc?
 » 4 years ago, # |   0 system testing started ! hold your nerves !
 » 4 years ago, # |   +21 System test is started. Feel free to discuss problems. Sorry for delay.===Системное тестирование запущено, можно обсуждать задачи! Приносим извинения за задержку.
•  » » 4 years ago, # ^ |   0 How long to wait for editorial ?
•  » » » 4 years ago, # ^ |   +23 I'm sorry but this will be a round with delayed editorial. All editorials for problems will be posted no later than March 9th, most probably on March 8th evening.You may find brief ideas for the problems by simply asking in comments for this post.
•  » » 4 years ago, # ^ |   +37 When can I view other people's solution?
 » 4 years ago, # |   0 How to solve C? please someone tell me briefly
•  » » 4 years ago, # ^ |   +1 Briefly — after simple math (square, equal, cut) we get that valid pairs have either equals X or equals Y. Put every value in counting dictionary/set/whatever and get sum.
•  » » » 4 years ago, # ^ |   0 thanks
•  » » » 4 years ago, # ^ |   +1 I did that but still got WA on 28th testcase. :'( I found all possible pairs with same X and added it to number of all possible with equal Y and subtracted pair which has both X and Y same.
•  » » » » 4 years ago, # ^ |   +1 Maybe overflow?
•  » » » » » 4 years ago, # ^ |   +1 No, I did use long long. http://codeforces.com/contest/651/submission/16577339
•  » » » » 4 years ago, # ^ |   +1 I think you are doing multiplication before typecasting here ans += (long long) (k*(k-1))/2; which is why you have overflow.
•  » » » » » 4 years ago, # ^ |   0 Ohh. Didnt realize it would result in overflow. :'( Anyways Thanks.
•  » » » » » 6 months ago, # ^ |   0 Hello sir. I understood your point but now I have changed all my variables to long long and idk why I'm getting wrong answer only at test 13 :(Link to my code
•  » » » » 4 years ago, # ^ |   0 Yes overflow!!!! I added only 4 characters and got AC.
•  » » » » 4 years ago, # ^ |   0 That's overflow. We all know that feel.
•  » » » » » 4 years ago, # ^ |   0 This sucks :( Just when I thought I had not done any silly mistake this time...
•  » » 4 years ago, # ^ |   +1 I couldn't participate, but I have read the problem and I think you can use a hash table (C++ map) for X and another for Y, and count how many individuals have each X and each Y. Then traverse all those keys and for each one, if the count is N, add to a global counter N * (N — 1) / 2, which should be the number of pairs you can make out of N watchmen.Then you should make sure not to count twice or to subtract the individuals which are the same X and Y, which should not be difficult.And as somebody said in another comment, use long long.
•  » » 4 years ago, # ^ |   +1 While it took me about an hour to read, think and code Problem C, someone on earth solved it in 0:01 min.Just saying.
•  » » » 4 years ago, # ^ |   +9 Well tourist is a tourist.
 » 4 years ago, # |   +17 Welcome to Problem D test 35 .
 » 4 years ago, # | ← Rev. 2 →   0 What was the hacking case for A?For B it was int32 overflow.UPD: Damn, I've messed with tasks again. I meant int32 overflow hack case for C.
•  » » 4 years ago, # ^ |   0 For Div 2 C it was int overflow.
•  » » 4 years ago, # ^ |   +3 For A, I hacked two solutions with this test : 1 2
 » 4 years ago, # | ← Rev. 2 →   0 Damn these overflows got me again on C. Need to still wait more to get 4 correct in a Div 2 contest :(I should start to use #define int long long probably
•  » » 4 years ago, # ^ |   +1 You would get Compilation errorThe function main must return int valuei did it once, and costed me two hours of debugging :3
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +8 use signed main() #include using namespace std; #define int LL #define LL long long int signed main() { int a=12345678912345678; cout<
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   +3 #define int long long main(){ return 0; } 
•  » » 4 years ago, # ^ |   0 Me too :( F***ing overflow.
 » 4 years ago, # |   +18 Why can't I see the tests?
•  » » 4 years ago, # ^ |   0 I can see solutions of div2 but not of div1!
 » 4 years ago, # |   0 I need some help regarding Div2 C.I did it following way:I found out the number of distinct horizontal and vertical lines and count of number of points for each horizontal and vertical line. After that simply we can form pairs for each line by using n(n-1)/2 and keep on adding it to the final answer.But I've a problem that this way I can't remove the duplicate points and each duplicate will be added twice in my answer.Any suggestions regarding a faster method to find similar points? (The best I know would be simple brute-force and that will be running in a time which violates time constraints?)
•  » » 4 years ago, # ^ |   +1 Use another map to count number of points in the same position (can use map,int>), then for each position, subtract the result for n * (n - 1) / 2 with n is the number of points in each position.
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 I used a map,int>. You could also sort all the points by (a.x
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 If you code in C++ read about std::map.
•  » » 4 years ago, # ^ | ← Rev. 3 →   0 I didn't use map and got AC with arrays. So, one array of pairs for (x, y), two arrays: one for X and one for Y coordinates. Sort them all, and then you can calculate easily how many of them are with same X or Y coordinate, while tracking how many of them coincide.16585770
 » 4 years ago, # |   +8 Thank you for fast rating updates :D
 » 4 years ago, # | ← Rev. 3 →   +28 Waiting for system test was like riding a roller coaster for me. And I did have GREAT fun when I knew the results!
 » 4 years ago, # |   +208 Memory Limit 256 MB , memory used 255 MB
•  » » 4 years ago, # ^ |   +38 255200/1024 is around 249.2 Mb, so you still have a lot of free space :)Check submission by overtroll — he used 260700 kb :)
•  » » » 4 years ago, # ^ |   0 He also used 262100 kb and got ML, even if 262100/1024 == 255.957 :)
•  » » 4 years ago, # ^ |   0 16582815Pretty close TL, huh
 » 4 years ago, # |   +102 Congratulations to tourist on his best performance ever — today he got +172, beating his previous record of +162 (which was set back in 2010, in CF Round #8).One more round with such inflation and we'll see 4000+ :)
•  » » 4 years ago, # ^ |   +59 Feels wrong that #1 person placed #1 in tournament get so much points.Why TooDifficult got only 84? Its 2 times lower.
•  » » » 4 years ago, # ^ |   +45 He got 2 times lower place :P
•  » » » 4 years ago, # ^ |   +10 I think it's because the round was really stacked because of the time; a lot of great asian coders participated who couldn't otherwise, and only the more dedicated coders from other continents participated (or the ones who don't have school this week hehehe)
 » 4 years ago, # |   +25 bredor where is your scrincast with russian rap?
 » 4 years ago, # | ← Rev. 2 →   0 Today I learnt a lesson, never use scanf with ios::sync_with_stdio(false); cin.tie(0); today it costed me heavily on D.
 » 4 years ago, # |   0 Why were all my solutions skipped ? Also it seems as if I never participated in the round while I solved 2 problems and 1 more in practice.
•  » » 4 years ago, # ^ |   0 I registered.I participated and solved 2 problems B and CSystem shows that I never registered and System skips all my submission.
 » 4 years ago, # |   0 In my previous CF Div2 (#343) round, I managed to solve only 1 problem and had a ranking of 2400. Today I could successfully submit 2 problems and had a ranking of 1700. Which implies an increase of 700. My rating still fell down today. I've no clue as to why is this happening!Improves from previous round and still rating decreases! :SAD: :(
•  » » 4 years ago, # ^ |   0 Well it seems you have participated in too little rounds for your rating to stabilize.Also it is not really depends on the place number, but rather on the amount of participants, their quality (rating) and your relative position among them. E.g. if contest have only 100 participants and you placed #100 — its worse, than if contest have 10000 participants and you placed #8000. But also if in first case other 99 would have rating of 100500 you probably won't lose anything (maybe even get higher), but if everyone of them have rating of 0 you will fell down pretty heavy. Hope you got the idea.
•  » » 4 years ago, # ^ |   0
•  » » 4 years ago, # ^ |   0 What do you love more — Problem Solving or seeing positive rating changes ?
 » 4 years ago, # | ← Rev. 3 →   +85 Problem E turned out to be surprisingly simple. For example, in the example below, the following works: Remove 7-4 -> add 7-6 Remove 9-4 -> add 9-1 Remove 4-6 -> add 4-5 Remove 3-5 -> add 3-1 Remove 5-6 -> add 5-9 Remove 6-1 -> add 6-3 Remove 8-1 -> add 8-5 Remove 10-2 -> add 10-5 Remove 2-1 -> add 2-6 (We need a slight modification when the two trees have common edges, but this is not very hard.)
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 I don't get it. What is the pattern I should see from this example? I am very curious how to solve E because it doesn't seem that hard (you have a lot of freedom when doing operations), but still, I am unable to create an algorithm that works all the time. Can you explain exactly how you solved it? (just the main ideas)
•  » » » 4 years ago, # ^ |   +13 The main idea of one of the authors solutions is working with leaves. Consider a leaf u with its edge (u, v) in the first tree. There are two cases: if the edge (u, v) is present in the second tree, it should stay as is and we can contract this edge forming a new vertex uv in both trees. In the other case we should find any of the edges going out of u in the second tree, let's call it (u, w), and replace (u, v) with (u, w), and after that contract u and w. Note that all v, u, w may be contracted vertices and should be dealt carefully (in particular, the endpoints of removed and newly added edge may be distinct though they belong to the same contracted vertex u). This leads to an O(nα) solution.
 » 4 years ago, # |   +20 It seems that smth is wrong with Java invocations. If the parameters are set correctly, it should be impossible to get ML in this language: it will be either TL because of long GC, or RE because JVM cannot allocate more memory. However, I've got ML for the following solution 16574238. It consumes at most (1M (input) + 2M + 2M (edges) + 1M + 1M (dsu)) = 8M int's, 1M boolean's, 1M ArrayList's of total size up to 2M, 1 ArrayList of size 1M. In total it is up to (8 * 4 + 1 * 4 + 1 * (8 + 4 + 8) * 2 + (8 + 4) * 2)M bytes, which is way below 256Mb. Of course there are plenty of temporary variables, but they should be safely garbage-collected. Unfortunately it doesn't show me the test, so I cannot debug what's going on there.So the question is, how are memory params (-Xmx etc.) set for for Java on server? If they're set consistent to the problem ML, then MLE verdict should be impossible. Am I missing smth?
•  » » 4 years ago, # ^ |   +20 And another data point. Apparently GC behavior on server is very weird. E.g. the following code: public class Main { public static void main(String[] args) { int[] churn = new int[50 * 1000 * 1000]; // Allocate <200MB. } } consumes 194Mb as expected. But the following code public class Main { public static void main(String[] args) { int[] churn = new int[50 * 1000 * 1000]; // Allocate <200MB. System.gc(); } } consumes 472Mb! And another experiment: the following code public class Main { public static void main(String[] args) { int[] churn = new int[50 * 1000 * 1000]; // Allocate <200MB. churn = null; System.gc(); } } consumes 292Mb.This essentially means that if GC triggers, all ML's for Java are divided by 2. I think Java/GC configuration on servers needs some serious adjustments...
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 I remember someone already pointed out in comments that CF uses Xmx 512MB.Also this submission: 16585600 and 16585728 looks like Xmx is indeed 512MB.
•  » » » » 4 years ago, # ^ |   0 So, the memory limit verdict happens when the launched jvm goes OOM?? As such -Xmx corresponds to the max heap memory, apart from this there are other sources of memory consumption for a java process, Different GC policy for sure would reveal different memory usage pattern, like in JAVA8 if you call System.gc() in a loop when G1GC is your garbage collection strategy then you would observe that the given java process keeps on incrementally consuming more and more memory without going OOM (consumed memory might be part of native memory area.)
 » 4 years ago, # |   +10 Can somebody post brief explanation of Div.2 E/Div.1 C ?
 » 4 years ago, # |   +4 How to solve Div2 D ?
•  » » 4 years ago, # ^ |   +3 First precalculate how much time it would take to reach from 1st picture to ith picture while doing right swap each time for each i from 1 to n. Similary calculate time to reach from 1st photo to last picture while doing left swap each time.Then for each position from i to n while going right, you have to find the maximum position you could reach on the other side (left), this could be found using binary search. Again the same for left to right.Complexity: O(nlogn)
•  » » » 4 years ago, # ^ |   +6 I implemented this too, but I think it's possible to do in O(N), because if you try to find the max position you can reach on left, for each i, then it will be at most the position for i - 1, and hence you can use something like a two-pointer technique (or sliding window if you prefer that analogy) to do it in O(N).
•  » » » » 4 years ago, # ^ |   +6 My idea is same as polingy's 16577590
 » 4 years ago, # |   0 anyone can tell me the tecnique of div2 c ? plz...
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 Manhattan and euclidian distance between two points is same when at least one coordinate of both the points is equal. You can prove this by equating both equations. Then you can use map to store count of occurrences of each x and y coordinate. Use another map to store count of pair(x,y). You can find answer by adding gC2 for each x and y ( g is the count of occurrence of each x and y coordinate stored in map). However some points may be repeated in the input and so you will add those pairs in the answer twice once for x coordinate and once for y coordinate. So just use the map used to store pair(x,y) and for each point subtract countC2 from answer ( count= number of times given point appears in input).
•  » » 4 years ago, # ^ |   0 First, let us assume A = |x(i) - x(j)| and B = |y(i) - y(j)|. Then, Manhattan's distance = A + B, and Daniel's distance = sqrt(A ^ 2 + B ^ 2). Solving this, we get 2 * A * B = 0, which means that either A or B is 0. So, all such pairs of points which have either the same x-coordinate, or y-coordinate are to be counted. So, we sort the array according to x-coordinate and then for each unique value of x, if the number of points have that x is N, then we add to the total the value N * (N - 1) / 2 as that is the number of ways of selecting 2 points from all N points(NC2). Then we do the same for y after sorting the array according to y-coordinate. But, here there will be 1 problem that we will have counted those pairs twice which have both the x and the y coordinates same. So, to remove this, for each point having coinciding points, if the number of coinciding points is M, we subtract M * (M - 1) / 2 from the total.
•  » » » 4 years ago, # ^ |   0 wow,,,thanks bro
•  » » » » 4 years ago, # ^ |   0 no problem :)
 » 4 years ago, # |   +31 It's already frustrating...In div1, we can't see sources or tests. Please fix this issue: I really want to find my bug in div1D
 » 4 years ago, # |   -13 Again failed C because of overflow ( lost 1200 points ). What do you do to avoid overflows ? I tried #define int long long but thats throws an error main() must return int
•  » » 4 years ago, # ^ |   0 #define int long long main(){ return 0; } 
•  » » 4 years ago, # ^ |   0 I don't use it but you can try this: #include #define int long long /* * Something */ #undef int int main() { #define int long long /* * Something */ return 0; } 
•  » » 4 years ago, # ^ |   +11 Or you can use int32_t instead of int : #define int long long int32_t main() { } 
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 It is better to define (before the contest) typedef long long ll; and just use ll everywhere instead of int (except main() type, of course). Speed disadvantages are minor, and at the same time you will get overflow very rarely.
•  » » » 4 years ago, # ^ |   0 Hell No !i remember getting lots of ML and TL because of this the best way is to use ll only when it is needed but when u wrote ur code and u suddenly find out about the overflow u can simply define int long long and change int main() to main()
•  » » » » 4 years ago, # ^ |   0 Probably on some hard div1 problems (C-E) you can improve wrong solution from ML/TL just using int where long long is redundant. This problem seems unlikely to me on div2A-D, it can happen only when your code is very suboptimal. I'd like to see counterexamples if I'm wrong.
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →   0 Well since you asked for a counterexample :PML exceeded code(in method solve2) : 16439466Accepted code(just changed type of array board from long to int in method solve) : 16439508PS : the method names are different because I had just removed the unused method solve before submitting again.
•  » » » » » » 4 years ago, # ^ |   0 You have three big arrays: Cross[] allcrosses, long[][] board and long[][] sum, other are not greater that a couple of MB. It is interesting why it is ML, because maximal size for each of them is 4*10^6 elements, long is 8-byte and Cross is 4+4+8=16 bytes. So total used memory should be ~4*10^6*(8+8+16)=128*10^6 bytes. In theory. Maybe I don't know something about Java to configure the cause of this doublesizing in practice.However, as I said, ML here is the result of suboptimal solution. You needn't store all crosses, only positions and values of the two current best crosses.
 » 4 years ago, # |   0 could someone here explain what division 2 D / division 1 B is about? i had a hard time understanding that question and still have hard time parsing the problem. in particular, in the beginning is all the images in vertical direction? so only cost you spend is when we need to rotate image that is in the horizontal direction? i'd imagine you need to go left or right depending on some kind of 'measure.'what's the solution concept? is it some kind of dynamic programming, or is it something completely different?
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 I didn't solve D but I can answer your queries about the problem . You view the images on a phone which is initially in the vertical orientation , so if you encounter an image which is of the opposite orientation than your current phone orientation you need b seconds to change the orientation of your phone .UPD: My bad !
•  » » » 4 years ago, # ^ |   +24 This is wrong, you are not allowed to rotate phone, only pictures. Trying to rotate phone because I read problem before clarifications is why I'm orange now :(
 » 4 years ago, # |   0 Regarding question C Watchman. Codeforces says wrong answer on test case 3 as wrong answer expected '33', found '39' But my computer machine gives the 33 answer and on codeforces the same code giving 39 answer on 3rd test case ..I also cross check on Iedone.com .It also giving me 33 but codeforces give 39 and hence not accepting answer ....please have a look to my submission no 16580949 or visit my submission ..pls help ..
•  » » 4 years ago, # ^ |   0 Yeah, pretty weird. Let me check...
•  » » » 4 years ago, # ^ |   0 Did you find any error ?
•  » » » » 4 years ago, # ^ |   0 It seems right. In my PC give 33 too. I don't know! Make sure you don't have unespected runtime error. I heard sometimes system give WA but is RE instead (also in ACM ICPC Regionals).
•  » » 4 years ago, # ^ |   +1 // while(i < n && v[i]==v[i-1]) // while(i < n && v[i].first==v[i-1].first) // while(i < n && v2[i].first==v2[i-1].first) remember to check the boundary when using while. BTW, I really don't like your coding style
•  » » » 4 years ago, # ^ |   0 Thanx sir .. i got it ... BTW i am just beginner that's why my coding style is so sparse :)
 » 4 years ago, # |   0 I mean it IS obvious, but still... is tourist even human anymore? :/
 » 4 years ago, # | ← Rev. 4 →   0 Could anyone help me find the bugs in my code of Problem C(Div. 1)? It always got TLE on test #14 and I am confused about it....Here's the code, Click
•  » » 4 years ago, # ^ |   +5 You are not allowed to view the requested page
 » 4 years ago, # |   0 Is it possible to solve div2A with the formula? The 2 steps forward, one step backwards thing looks too darn familiar...
•  » » 4 years ago, # ^ |   +1
•  » » » 4 years ago, # ^ |   0 Thank you.By the way, I've found an interesting solution that uses DFS!div2A — DFS
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 How did you come up with that?
•  » » » » 4 years ago, # ^ | ← Rev. 14 →   +10 This is sentews2's code.I don't know whether he'll answer your question, so I'll tell you my version of the story. First, take a look at this rain water barrel: You see, there are 2 paths for water to go out. The throughput of the lower tap is 1 liter per minute and of the upper tap is also 1 liter per minute. Let's imagine that, when we open both the upper and the lower taps, the barrel will lose 2 liters of water every minute. Now, we'll do the following trick. Let's connect the upper tap with the hose and return that water, running from the upper tap, back into the barrel. On one hand, the barrel still loses 2 liters of water every minute, but on the other hand, the barrel now gains 1 liter per minute from the upper tap. This image clears the things out for me, so I can see that the barrel now loses 1 liter per minute in total. The key moment, I think, is to consider the whole system. That is, how much water (or energy, in the case of the div2A problem) does the whole system lose? If we think about the joysticks as a single system containing some amount of energy, we see that the amount of energy contained in that system is a + b and the system loses 1 unit of energy every minute. If we could just drain the energy from 2 joysticks to 0, the amount of time the system would survive by losing 1 energy unit a minute is a + b minutes. Since we cannot drain it to 0, when we are getting close to complete exhaustion, the internal structure of the system of 2 joysticks becomes important, i.e. the distrubution of energy between the two affects the answer. Exactly for this reason, we should also consider all the cases of relative energy distribution in joysticks (when energy is near 0):0 00 11 01 1
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 I think it is simply a DFS on states! The states are acyclic you can prove it on the basis of transitions( They only take you to larger or smaller number) . Hence the states form a DAG. But there might be multiple ways to reach a state I cannot understand how is he taking care of that! I think if we can prove that the first time we reach the state, the value we maintain is optimal then we can prove his solution! Edit: Yeah If I change that max taking condition to work only when we visit the state at first it gives AC then too. So probably anyone who can prove the hypothesis by me can prove the solution :) Any Red People, correct me if I am wrong?
•  » » » » » 4 years ago, # ^ |   0 I was asking how to come up with this one http://codeforces.com/contest/651/submission/16563831
•  » » » » 4 years ago, # ^ | ← Rev. 6 →   0 We can notice that: if the remainder abs(a — b)%3 equals 0, it would keep 0 after each minutes. Otherwise, it can change between 1 and 2.For the first case, the final state is (0, 3) or (3, 0). (why no (0, 0)? because ever time the total energy would lost 1 percent, but we can't get (0, 1) or (1, 0))For the second case, the final state is (0, 2) or (2, 0).So the answer is max(0, a + b — 3) or max(0, a + b — 2). 16601248
•  » » 4 years ago, # ^ |   0 I used a recursive function:16582603.
 » 4 years ago, # |   +32 I wonder if tourist is going to reach 4k this month. Just looking at the slope of that curve.
•  » » 4 years ago, # ^ |   +24 Seems like new rating system is more appropriate for those who often takes top1. tourist did the same good for a few last years, but there is no such jumps on the graph like for last 4 contests.
 » 4 years ago, # |   +3 Is there any editorials?
 » 4 years ago, # |   +3 Bring a new rating category, tourist is close to breaking 4000 limit :D
 » 4 years ago, # |   0 Can anyone please explain the idea of Div1/C or Div2/E ?
•  » » 4 years ago, # ^ |   +20 build a graph G with n * m vertices that each of them correspond to a cell in the table. add an edge from vertex u to vertex v if u and v are in the same row/column and a[u] <= a[v]; now find every SCC of the graph and create a new graph H in which every vertex is a SCC of G. note that vertices of a SCC of G should have the same number in the final table. now find the topological order of vertices of H(I leave it to you to prove that there is a topological order for vertices of H). the vertices that are not endpoint of an edge(note that since the edges are directed, start points and end points are different), can be assigned value 1. erase those vertices from H and assign values to the other vertices recursively. note that this solution uses O((nm)^2) edges to construct graph G. you need to use some ideas to reduce the number of edges(I leave it to you).let me know if you need any more help.
 » 4 years ago, # | ← Rev. 2 →   +36 I'm already sure that you forgot to let us the permission to see the tests or someone's else source (as we don't have the permission during the contest). Please let us. I've been looking for a bug in my source for a couple of hours and it'd be much easier if I could see the test (as we usually can). It's my third comment about this problem ans I hope someone will see it. I don't know where to post it...
•  » » 4 years ago, # ^ |   +31 badass is here for helptry this test 8 10 28 97 4 46 44 31 35 21 6 88 7 71 5 94 1 84 3 91 2 61 1 59 3 43 1 73 2 82 correct output: 3 3 3 3 3 3 3 3 3 3 
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +10 I've just found what's wrong but I don't know exactly how to solve it now. I may have an idea but the code is already very hard to understand and it's very complicated what I want to do. I think I'm going to quit. Still, badass, can you tell me what is your idea?(BTW, I guess you've just found a new nickname :)) ) Actually, I'd like to hear ideas from anybody about div1D. It seemed really nice at the beginning(the answer is either M — 1, M or M + 1 where M is the maximal length of a maximal increasing subsequence). Now I've tried to check whether is M + 1 (this was easy). Now I have to check if it is M — 1 or, if not, to print M. But my idea for checking whether M — 1 or M is a solution is very hard and I'm almost sure that this is not the solution.
•  » » » » 4 years ago, # ^ | ← Rev. 3 →   +68 Let the length of longest increasing sub-sequence(LIS) in original array(before any update) be S.we need to find for each element in the array whether it's included in at least of the LIS or not, and if yes does removing it will decrease length of LIS by 1 or not.let L[i] be length of LIS ending in i and R[i] length of LIS starting in iit's clear that if L[i]+R[i]-1 == S then element i is included in at least on of LIS, now how to know if we remove i then S will decrease or not?it's a bit tricky, removing i will decrease S if and only if there's no j such that element j is included in at least one LIS and L[i]==L[j] (i.e. element i is the only element which have the value L[i] among all element which are included in LIS)after we know for each element if removing it will decrease S or not it's easy to answer the queries now :)
•  » » » » » 4 years ago, # ^ | ← Rev. 3 →   0 I've just got AC. I made the arrays L and R as you said but for being sure wheter its elimiation decreases S by 1, I used some hashes(yep that's right=)) ). I just counted in how many ways optimal L or optimal R can be built and it should be equal to the total number of optimal increasing subsequences. Anyway, thanks :) I understood your observation and it is a better solution(because mine can give a wrong anser in case of collision)LE: I've implemented your idea and got AC: faster and shorter code. Thanks :)
•  » » » » » 4 years ago, # ^ |   0 Nice :)!
•  » » » » » 4 years ago, # ^ |   0 Nice solution! I was struggling to get track of which element is in LIS during contest time, and finally came up with a weird method when the contest was over...
 » 4 years ago, # |   0 Need some help with problem C Round 345.Any editorial soon??
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 At first, solve it mathematically. Set a = xi — xj, b = yi — yj sqrt(a^2 + b^2) = |a| + |b| ; => a^2 + b^2 = (|a| + |b|)^2 ; => a^2 + b^2 = |a|^2 + 2*|a|*|b| + |b|^2, where |a|^2 = a^2 — obvious ; => 2*|a|*|b| = 0, where a = 0 or b = 0 Result solution: We must to calculate count of x-coordinate and y-coordinate repeats, and calcuate unique combinations PROFIT!P.S. Sorry for my english))
 » 4 years ago, # |   0 anyone can explain me ,, div2 D,,,,plz...i make comulative sum,,, from first to last and then last to first ,,and the bainary search but some cases still mistake,,,plz explain me what it says,, i am trying to read from first or reversly,,is it possible to start from center?
•  » » 4 years ago, # ^ |   0 There are many details in this problem which need quite a bit of careful handling. You can find the cases where your program gets WA (either in the system test or created by yourself) and think it over, or take a look at others' code.
 » 4 years ago, # |   0 The announcement has div1 tag only. Can you tag div2?
 » 4 years ago, # |   +19 Guys, please publish the editorial !!!!!!
 » 4 years ago, # | ← Rev. 2 →   0 My code for div2 C get right wrong for "3 1 1 7 5 1 5 "(the first sample) but get WA on codeforces... Could someone explain me that? Here is my code: 16575774
•  » » 4 years ago, # ^ | ← Rev. 2 →   +3 Just as compiler said: no return statement in function LL cal( LL x);
•  » » » 4 years ago,