### laoriu's blog

By laoriu, 5 years ago, ,

Hello everyone!

Today, there will be another CodeForces Round at 18:00 (Moscow time). It is a Div. 2 contest, but Div. 1 participants can take part out of competition also.

My name is Vuong and this is my very first CodeForces round. Hope that this is not the last one. I would like to thanks Maxim Akhmedov(Zlobober) for help me preparing the round, Maria Belova(Delinur) for translating problems into English, and Mike Mirzayanov(MikeMirzayanov) for such a great Polygon and CodeForces.

Be sure to read all problem statements before contest ended. Hope you enjoy the contest.

Good luck and have fun!

UPD The contest is over! Thanks all of you for participating!

Here is top 5 participants:

The editorial can be found here.

• +177

 » 5 years ago, # |   +2 Would Score distribution be dynamic?
•  » » 5 years ago, # ^ |   +1 Hopefully not, last contest was dynamic and it was not rated (even if those two are not related)...
•  » » 5 years ago, # ^ |   0 yes , all the problems will be about dynamic programming . ok
 » 5 years ago, # |   0 Thanks for the problemset. Good luck to all! :)
 » 5 years ago, # |   0 I can go to bed before the system test over!!!! Because my university will cut off the electricity at 11:30, and my computer can last for only 3 hours without outer-power! What nice news!
•  » » 5 years ago, # ^ |   -6 mathlover is a super star in my heart,can I admire you?
•  » » 5 years ago, # ^ |   0 In our university, The building #15 has electricity supply all the night so I can wait for the system test.
•  » » » 5 years ago, # ^ |   +27 Can I go to your dorm and code with you?
•  » » » » 5 years ago, # ^ |   0 My dorm is very mess now... Maybe next time.
•  » » » » » 5 years ago, # ^ |   +4 Never mind~
•  » » 5 years ago, # ^ |   -15 How hard to study in China :D Economy))
•  » » » 5 years ago, # ^ |   +6 This is just some of the rules of the school,because the contest time is at midnight in china,but there are still many hard-working students like mathlover got a red name.
•  » » » 5 years ago, # ^ |   0 hi！ ShaDiao! In China,We are in order to save electricity. We never short of money!
•  » » » 5 years ago, # ^ |   +14 it is because of some fool schoolmasters and teachers but not economy...
•  » » » 5 years ago, # ^ |   0 Китайцы, успокойтесь!
•  » » » » 5 years ago, # ^ |   0 please translate it to English~THX
 » 5 years ago, # |   +19 If I'm not wrong, this is the first round set by a Vietnamese! Good job! :)
•  » » 5 years ago, # ^ |   +5 I don't think so... http://codeforces.com/blog/entry/8248
•  » » 5 years ago, # ^ |   0 ll round =)) you're wrong :p
•  » » 5 years ago, # ^ |   0 i also think so! i will participate the contest tonight!
 » 5 years ago, # | ← Rev. 2 →   +41 I have been wndering....how many languages does Delinur know?? :D
•  » » 5 years ago, # ^ |   0 Usually, problem statements will be written in English, if the author wants it to be put in an international site.
•  » » 5 years ago, # ^ | ← Rev. 4 →   +4 I know don't the exact answer. But one day during a conversation, she said this "But I can translate your message into 4 other languages if you want :P". It means that she knows may be 5 or 6 languages or more.
 » 5 years ago, # |   +5 22:00 is good time for me to participate. Thank you for your contest.
•  » » 5 years ago, # ^ |   +5 You didn't even register for the contest
•  » » » 5 years ago, # ^ |   +8 I went to register page at least 3 times but failed to register because of some network problems. After coding problem B, I realized that I didn't register for this contest.
 » 5 years ago, # |   0 I hope codeforces won't be down today :S
 » 5 years ago, # |   0 Countdown time and Announced time are Different. I am confused.
•  » » 5 years ago, # ^ |   +1 Both of them are correct. Which announced time have you seen?
 » 5 years ago, # | ← Rev. 2 →   0 I wonder will the time be at 18:00(MSK) in the future or 19:30(MSK) for mostly?
•  » » 5 years ago, # ^ |   0 I hope most rounds are on 18:00 MSK in the future. That 1-hour switch has really some impact on us(Chinese).
•  » » » 5 years ago, # ^ |   0 ...but 17:30 CET is too early for me, and you can guess what is my opinion about 16:00 CET...
•  » » » 5 years ago, # ^ |   0 I hope for 19-30(MSK)
 » 5 years ago, # |   +5 I think :codeforces Round 277(Div. 2)== Happy Birthday contest !!(for MikeMirzayanov's daughter)!!:)
•  » » 5 years ago, # ^ |   -35 bhut fikar hai tumhe mike mirzayanov ki beti ki .-- written in HINDI now translate it Delinur
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +5 please write in English!!I can't read this comment.
•  » » » » 5 years ago, # ^ |   +2 He said "Why are you so concerned about Mike Mirzayanov's daughter ?"
•  » » » » » 5 years ago, # ^ |   +6 I like mike Mizayanov and him daughter. she is funny and smart and cute and ... daughter!!
•  » » » » » » 5 years ago, # ^ |   +9 I just translated it clashofclans, reply to terminated .
•  » » » » » » » 5 years ago, # ^ | ← Rev. 2 →   0 See previous Edit
 » 5 years ago, # |   0 i wish we won't have hack or other problems in this round
 » 5 years ago, # |   0 I bet that there will be one more blog post by DmitriyH after this round.
 » 5 years ago, # | ← Rev. 4 →   +6 Punish him/her please! (S)he wants solution
 » 5 years ago, # |   0 How to solve C ????
•  » » 5 years ago, # ^ |   +12 You always need to fix only a half of a string you are staying at.
•  » » » 5 years ago, # ^ |   +1 I did exactly that. Got WA on pretest 2. I am sure its a silly mistake on my part. :(
•  » » » » 5 years ago, # ^ |   0 Was a silly mistake... :(
•  » » » 5 years ago, # ^ |   0 But How to do it by minimum operation ?
•  » » » » 5 years ago, # ^ | ← Rev. 4 →   0 Assume we are in the first half of a string. You are to find the segment which you must fix (leftmost and rightmost positions in the first half). Now you can choose the best way to visit all the segment, there are only two of them: right - pos + right - left and pos - left + right - leftOf course, you also have to do min(abs(s[i] - s[n - i - 1]), 26 - abs(s[i] - s[n - i - 1])) operations for every i=1..n/2
•  » » » » » 5 years ago, # ^ |   0 What if both left and right are on the same side of pos?
•  » » » » » » 5 years ago, # ^ |   +3 You can take the absolute values, givingmin(abs(right-pos)+right-left,abs(pos-left)+right-left)
•  » » » » » » » 5 years ago, # ^ |   0 Well, my implementation ( 8656932 ) was a bit different. So I had to give that extra check, where both left and right were on the same side of pos. Lelby also gave that check ( 8659477 ), but he commented differently. That's where I got confused.
•  » » » » 5 years ago, # ^ |   0 You have to move from first char which needs to be fixed to the last one (or opposite way if shorter).For example if number or fixes for characters in string aaaaacdefg is 0, 3, 4, 5, 6. Then if you are on position 2, you move to position 5, if in position 3, move to 2 and then to 5 and if on 3, then move to 5 first and then to 2...
•  » » » » 5 years ago, # ^ |   0 We need to operate only with one half of string. Consider we choose left one. If p > n/2 just reflect it. Them found two indicies — 'l' first letter which need to change and 'r' — last letter which need to change. Minimum action for movement will be min(r-p,p-l) * 2 + max(r-p,p-l) if p inside [l;r]. If p is outside first we need to go in this range. Now we know how much ticks we will spent only on movement, during this movement we'll be on each letter. So just calculate cost of each change in range [l;r]. Result will be movement cost + change cost.O(n)I hope my approach is right :)
 » 5 years ago, # |   +20 How to solve D ?
•  » » 5 years ago, # ^ | ← Rev. 2 →   +10 Define root of a set as the node with minimum (av, v). Now we can consider all the sets with that root (each of them will be counted once). It can be done via simple dymanic programming. http://codeforces.com/contest/486/submission/8659287
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 Take a fixed minumum number low then maximum value is low + d.Find number of sub trees which has at least one node with minimum value and does not has any node that bigger then low + d or less then low. It can be done with dynamic programming in O(N). Overall complexty is O(ND)
•  » » 5 years ago, # ^ |   0 Thank you both very much! I've got it.
 » 5 years ago, # |   +5 Why some people didn't get overflow in first problem when they calculated sum of first n div 2 even numbers and calculated sum of first (n+1) div 2 odd numbers?
•  » » 5 years ago, # ^ |   +3 I don't know. I made an unsuccessful hack because of this!
•  » » » 5 years ago, # ^ |   +3 Same here :(
•  » » 5 years ago, # ^ | ← Rev. 2 →   +15 It overflows, but both overflow the same, so when they subtract the overflow is gone. If you can find a case such that one overflows but the other doesn't (very unlikely and might not exist because 1018»1015), I think their solution will fail. I spent the last 15 minutes on W|A (Wolfram Alpha) trying to do just that, but haven't succeeded. A program would probably do it faster though.EDIT: Actually I think now that even if one overflows and the other doesn't, subtracting them will again mean the overflow didn't matter. 281474976645119 makes one overflow and the other not, but it still works as the overflow is ignored.
•  » » » 5 years ago, # ^ |   0 Yeah I noticed this after my first unsuccessful hack :D
•  » » 5 years ago, # ^ |   +1 let's hope for system testing!
•  » » 5 years ago, # ^ |   0 Apparently some solutions failed for the input "3037000499"
•  » » » 5 years ago, # ^ |   0 This doesn't seem to break one solution I'm looking at. Can you show me a submission that fails it?
•  » » » » 5 years ago, # ^ |   0 This one fails (i failed to find this test in time). 8652729
•  » » » » » 5 years ago, # ^ |   0 Ok thanks. It's different because they find the sum of all numbers and subtract twice the sum of the odds, and since they divide by 2 after overflowing, subtracting no longer always removes the effect of the overflow.
 » 5 years ago, # |   0 How to solve problem D(problem D is very hard!!)?
•  » » 5 years ago, # ^ |   0 My sol is to DFS each note as that node is the max node, then use DP.
•  » » 5 years ago, # ^ | ← Rev. 2 →   +3 Every valid set can be uniquely determined by the smallest node in it.(If there are more than 1 node has the smallest value, we choose the one who has the smallest id). So let's choose an node to be our special node, and starts to dfs under the limit that our special node has the smallest val and smallest id and the gap is no more than d. We get a sub-tree of the original one. And considered sub-tree, You can use dp to count how many way you can choose a set which contains the root (our special node)from the sub-tree. It's a classical dp problem on trees. dp[node] means the ways to choose a set which contains the root and the others node come from the sub-tree of it. And you want to calculate dp[x] for the the node x, you just go through his son, and we can either not choose the part from this son's sub-tree or just take it, which has dp[son] ways. So in total (1 + dp[son]) ways. Multiply the sons choices up. And we get the ways to choose a set from the sub-tree of x which contains the node x.As we can let every node in the tree to be our root(special node), we can get the answer for the question.Check my code hope that helps.
 » 5 years ago, # |   +1 A was easy, B was interesting, C was time-eater and interesting too.
 » 5 years ago, # |   +157 +100 to persistency
•  » » 5 years ago, # ^ |   0 nice
•  » » 5 years ago, # ^ |   +28 Wrong answer on test 156... :D
•  » » » 5 years ago, # ^ |   0 You scared me great ... Luckily there are only 40 tests!
•  » » 5 years ago, # ^ |   +1 :D did you get any point from this question?
•  » » 5 years ago, # ^ |   0 I did the same thing recently. But I was submitting my OK solution to A LITTLE DIFFERENT PROBLEM and got AC after 30-40 changes.
•  » » 5 years ago, # ^ |   0 you passed only pretest not finally full test for accuracy purpose they show only 5 -10 cases and show pretest passed.
 » 5 years ago, # |   +15 Ban Samsung please.Translation: he asked me to send him solutions of A, B and C
•  » » 5 years ago, # ^ |   0 wow the request is so interesting
•  » » 5 years ago, # ^ |   +8 this site has no report system?
•  » » » 5 years ago, # ^ |   0 Nope.
•  » » 5 years ago, # ^ |   -8 Did you sended him smth? No? There is no reason for ban then. Yes? Then both should be banned.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 I don't think temak would've asked to ban him if he has sent something o_o
•  » » » » 5 years ago, # ^ |   0 It's very same situation as — "You got SMS message: 'Mom! Please, send me 300\$ to X-XXX-XXX-XX-XX I'm in big trouble!!!'. You can ignore it, and then there is no criminal. But it's possible to find the owner of this number, send the money and then arrest him, because his attempt was succesful". So there is no chance that Samsung will be banned, because solution wasn't sent! But still, temak posted this image and waiting for something.
•  » » 5 years ago, # ^ |   -6 that's why Iphone better than samsung:D
 » 5 years ago, # |   +5 how to print negative number (A problem) from squee_sp00n's A if(n&1){ cout<<"-"<
 » 5 years ago, # | ← Rev. 2 →   +1 It seems that nobody solved E using large prime modulos like me. What was the intended solution?
•  » » 5 years ago, # ^ |   +1 I solved it in that way :)
•  » » 5 years ago, # ^ | ← Rev. 2 →   +3 I think it is to count the number of indexes belong LIS of length i :) If there is only one index of length i then it must be type 3, otherwise type 2.
•  » » 5 years ago, # ^ |   +3 Could you explain what do you mean by "large prime modulos" ?I solved it simply using segment tree for some calculations.
•  » » 5 years ago, # ^ |   -8 Quite surprised there's an antihash testcase for 2^64 modulos :|
•  » » » 5 years ago, # ^ |   0 While constructing testcase for string hashing is not so easy — hacking similar solution for this problem is very easy (and it is well-known olympiad problem). Just take a look at sequence 2 1 4 3 6 5 8 7 10 9... How many LIS it have? :)
•  » » » » 5 years ago, # ^ |   -8 Yes, i realize it's not hard to make such testcase, my bad for assuming anything modulo something is hard to hack :)
 » 5 years ago, # |   -8 Will the contest also be unrated as the past contest???
•  » » 5 years ago, # ^ |   0 No :)
•  » » 5 years ago, # ^ |   0 Don't think so. Last one was unrated because of problems with servers etc. Rankings are just always updated few hours after the contest.
 » 5 years ago, # |   +22 SighTop4 are once again unrated, two of them registered in the past 24 hours. I'm not saying they are cheaters, but that happens way too often lately :\Awesome problems by the way, solved all 5! Thanks, author :)
 » 5 years ago, # | ← Rev. 2 →   0 why getting wa in test case 16 in 486A - Подсчёт функции .. my soln 8655625 it gives correct output in my compiler
•  » » 5 years ago, # ^ |   0 Overflow problem. N can be 10^15 so N*(N/2) will be something like 10^29. You can read this comment, to understand why it may work on you compiler http://codeforces.ru/blog/entry/14672#comment-196477
 » 5 years ago, # |   -34 I HAVE A COMPLAIN IN CONTEST IT SHOWS PRETEST NOT SHOW WRONG OFTER CONTEST ITS SHOWS WRONG ANSWER WHY YOU WOULD NOT SHOW AT THAT TIME?
•  » » 5 years ago, # ^ |   +23 Welcome to CodeForces :D
•  » » 5 years ago, # ^ |   0 PRETESTS =/= TESTS, obviously.This is the format of the competition. Your solution is tested on some part tests that usually do not cover all corner cases and maximal constraints. After the competition your solution is graded on the official tests.
•  » » 5 years ago, # ^ |   0 pretests are a very small fraction of the entire test
•  » » 5 years ago, # ^ | ← Rev. 3 →   0 I don't know the exact reasons, but if I need to guess, there are probably three reasons for that:1) Because of pretest/test separation, there's less need of computation while we're in contest; that's why we can get faster feedbacks.2) It's much more exciting and fun to wait for system testing to see your actual results.3) Hacking mechanism is based on this feature; this is also related to second reason since hacking is fun.
•  » » » 5 years ago, # ^ |   -31 what a joking u its not fun always you show wrong answer at contest but today you cheat me it;s not fare.I wana my full points its your mistake not mine otherwise i'll never participate in your contest
•  » » » » 5 years ago, # ^ |   +81
•  » » » » 5 years ago, # ^ |   +3 What's going on in your head?
•  » » 5 years ago, # ^ |   0 This is not your first contest, right? There are few tests when you submit, but all tests are tested during system tests...
 » 5 years ago, # |   -24 this contest is unrated ?
•  » » 5 years ago, # ^ |   +1 Why are you asking?
•  » » » 5 years ago, # ^ |   -7 for Funny :D
 » 5 years ago, # |   +36 that My_First_Lady seems to have used different templates on C and E. and submitted C after E in two minutes.just saying.
•  » » 5 years ago, # ^ |   0 Yes, that's very suspicious indeed. Sadly I've never seen anyone banned for such reasons which is why we have tons of unrated accounts and/or teams ruining top5 of Div2.
»
5 years ago, # |
-53

see this two code for 1'st question whats differnt.

# include<math.h>

int main() { unsigned long long int n,i,j,k; scanf("%lld",&n); if(n%2==0) { i=n/2; k= i*(i+1); j=-(i*i); printf("%lld",(k+j));

} else { i=n/2; k= i*(i+1); j=pow((i+1),2); printf("%lld",k-j);

}

} 2.

# include<math.h>

int main() { unsigned long long int n,i,j,k; scanf("%lld",&n); if(n%2==0) { i=n/2; k= i*(i+1); j=-(i*i); printf("%lld",(k+j));

} else { i=n/2; k= i*(i+1); j=(i+1)*(i+1); printf("%lld",k-j);

}

} but first shows wrong answer and second shows correct answer what the difference between them

•  » » 5 years ago, # ^ |   +18 ...
•  » » 5 years ago, # ^ |   0 In case the guy really doesn't understand smth and not trolling: The first programs uses pow function (http://www.cplusplus.com/reference/cmath/pow/) The declaration of this function: double pow (double base, double exponent); — that means result for even integer numbers could be 255.99999999999 instead of 256 since for float(double) numbers those values are pretty same. But here j=pow((i+1),2) you're doing cast to integer. So result could be 255 instead of 256 and no one can guarantee which one exactly.
 » 5 years ago, # |   +6 Most of the solution failed test case 31 and 39 for problem B. They didn't know when to say NO :P
•  » » 5 years ago, # ^ |   +10 We're lucky that we don't need to output "START" / "STOP". Most of us don't know when to say "STOP" :D
 » 5 years ago, # |   0 Heh, had solution for C, but just assuming that there's only one turn, not that the cursor always remains in the first half. Much more complicated to write that way : S
 » 5 years ago, # |   0 codeforces should try to improve their website performance during contest..
 » 5 years ago, # | ← Rev. 3 →   0 8652439 Why can this solution for problem A can pass all the data? It is an O(n) solution!
•  » » 5 years ago, # ^ |   +11 The loop for (int i=1; i<=n; i=i+2) s=s+i-i+1; is so simple, that compiler (with optimizations on) turns it into s = s + n / 2 because loop is really just incrementing s by 1 on each iteration, and we know precisely the number of iterations. Thus it becomes O(1) solution.
•  » » » 5 years ago, # ^ |   0 oh...One of my friend attempted to hack this solution with a big number... two unsuccessful hacks... Sadness
 » 5 years ago, # |   0 Hello everyone! I am a new comer here and I don't know its a right place or not to ask about this but I didn't found better than this place to ask this question! I solved 1 question on first attempt on #Div 276 but my rating didn't effected and last night I solved one question on #div 277 on first attempt but now my rating is went down! I don't know what I did wrong and why my ratings are going down!
•  » » 5 years ago, # ^ |   0 This blog maybe useful.
 » 5 years ago, # |   0 Why my solution to A 8652258 passed all tests? It almost wrong. Can someone answer me
 » 5 years ago, # |   +5 Country wise rankings table has been updated
 » 5 years ago, # |   0 Mind if I ask why 4 out of 5 top are unrated?? I wonder if multi account is OK!
 » 5 years ago, # |   0 Why the next round will be called "Codeforces Round #277.5 (Div. 2)", not "Codeforces Round #278"?
•  » » 5 years ago, # ^ |   0 Because next contest that will be after 7 day called "Codeforces Round #278", "Codeforces Round #277.5 (Div. 2)" was created after this contest, and will start earlier