### MinakoKojima's blog

By MinakoKojima, 6 years ago, ,

Three drops in a line, back to yellow so quickly ...

Anyway, Codeforces Round #183 will be take place on Sunday, May 12th at 17:00 MSK(21:00 CST). Right after the Google Code Jam Round 1C.

Setters are:

• Yuzhou Gu Sevenkplus (For Problem B && E)
• Yuping Luo roosephu (For Problem A && D)
• Jiatai Huang CMHJT (Problem C)

Testers are WJMZBMR, havaliza, Velicue && me.

We gratefully acknowledge Gerald Agapov(Gerald) for his help in giving advise about the problems, Delinur for her help in translating the problems to Russian, and MikeMirzayanov, who has designed such a powerful platform.

We strongly recommend you to take a glance over all five problems, there must be one suitable to your taste.

Oh one more thing, this time, scoring will be dynamic, but problems are sorted by increasing order of their difficulty as usual.

Good Luck!

•
• +128
•

 » 6 years ago, # |   +8 Great!! I think it will be a great contest while the setters and testers are very good. Thanks for your soon post :)
 » 6 years ago, # |   +11 Not in midnight in Japan(and other far east Asia and Australia) Great!!!
 » 6 years ago, # |   +5 Codeforces Round #183?
•  » » 6 years ago, # ^ |   0 Fixed.
 » 6 years ago, # |   0 Are you sure in number of this round? Think, it should be 183.
•  » » 6 years ago, # ^ |   0 Sorry for such a silly mistake ... /w\
 » 6 years ago, # |   0 Very early announcement and score distribution (many peoples has like it), great setters and testers — I think it will be very interested.
 » 6 years ago, # |   +3 Haha noone even mentions Div2 A and Div2 B problems :D
•  » » 6 years ago, # ^ | ← Rev. 2 →   -10 As you can guess, DIV 2 A, B is set by me ... /w\ ......）。。。
 » 6 years ago, # |   +8 I think the problemset is easier but much more interesting this time..
•  » » 6 years ago, # ^ |   -8 Who set the problem for Div.2
 » 6 years ago, # | ← Rev. 2 →   0 Am I right that original statements will be in english?
•  » » 6 years ago, # ^ |   +5 Of course they're English.
•  » » » 6 years ago, # ^ |   +5 Actually they should be in Chinese..:)
•  » » » » 6 years ago, # ^ |   +27 Maybe Chinglish lol~
 » 6 years ago, # |   -8 I think hacking score is too low.
 » 6 years ago, # | ← Rev. 3 →   +6 Why this blog was not on home page ?
 » 6 years ago, # |   0 The first time I can participate in
 » 6 years ago, # |   +3 Hmmm contest time changed? 6AM in California...
 » 6 years ago, # |   -7 Why time is non-standart?
•  » » 6 years ago, # ^ |   +8 There was a risk of yesterday’s TCO Round 2C being cancelled and moved to 16:00 UTC today. Codeforces’ usual 15:30 UTC would conflict with it. It already happened with round 2A on 31st of March.
•  » » » 6 years ago, # ^ |   0 Thank
 » 6 years ago, # |   +17 It would be interesting for me(and I think not only for me:)) to know some additional information about the authors of the contest — your hobbies, photoes, interesting stories etc.
•  » » 6 years ago, # ^ |   +57 xiaodao's photo there >_<
 » 6 years ago, # |   +12 I wondered why comments by xiaodao got so many negative feedback?
 » 6 years ago, # | ← Rev. 2 →   +39 A question : is xiaodao (Feihu Tang) boy or girl?I thought the name is a boy's, but in his(or her) photos shared above it's a girl....
•  » » 6 years ago, # ^ |   +28 You can see that her name is 唐菲蝴(beautiful butterfly Tang),then everything goes right.
•  » » 6 years ago, # ^ |   +17 She's really a girl, believe me.
 » 6 years ago, # |   +39 I recommend you all to participate in this event. You would enjoy solving this set of beautiful (and challenging :D) problems. :)
 » 6 years ago, # |   +8 It is the Chinese round. I am really excited to see the problems! :) We had American problems (with USACO cows' background), we also had Japanese problems (rng_58's and the rest). And now is Chinese round. Love it.
 » 6 years ago, # |   -6 =w= unsuccess to reach 1500 last match...=w= so ..hope my friends and i can reach blue again ..T_T
 » 6 years ago, # |   0 are there any mistakes in sample tests in problem B div 2?
 » 6 years ago, # |   -21 Congrats for making unrated contest.
•  » » 6 years ago, # ^ |   +5 Who told you?
•  » » 6 years ago, # ^ |   +21 I hope you joke
•  » » 6 years ago, # ^ |   +6 Sir, this ain't April the 1st.
 » 6 years ago, # |   +26 The contest was perfectly prepared and tested :D
 » 6 years ago, # |   +9 Why in B in the second sample the answer isn't (29,22,75,78)? In this rectangle distance from the center to the point (x,y) is 0, and in the answer to the sample it's 0.5.
•  » » 6 years ago, # ^ |   +1 Same here. I don't know why this is incorrect...
•  » » » 6 years ago, # ^ |   0 The sad part is that a lot of people solve it and I don't even know how to interpret the statement — should the rectangle be the closest to (x;y) or lexicographically minimum..
•  » » » » 6 years ago, # ^ |   0 I spend a lot of time to guess — but i still don't know why... Sent clar, let's wait
•  » » » » » 6 years ago, # ^ |   +2 I sent one an hour ago. Guess what the answer is? You're right, "no comments" :)
•  » » » » » » 6 years ago, # ^ |   0 For me, they said, that my answer is not optimal..
•  » » » » » » » 6 years ago, # ^ |   0 Did they explain, why?
•  » » » » » » » » 6 years ago, # ^ | ← Rev. 2 →   +3 I sen't another clar 15 minutes ago, still no answer. UPD: Got an answer : We need first maximize the sub-rectangle, then take the lowest distance.
•  » » » » » » » » » 6 years ago, # ^ |   0 Damn, missed the word 'maximum'. Thanks, man.
•  » » 6 years ago, # ^ |   +7 because you should select biggest rectangular possible
•  » » » 6 years ago, # ^ |   0 Thanks for the answer. I feel like a total loser.. Ah, anyway, this will be a good lesson for my future contests.
•  » » 6 years ago, # ^ |   +2 From the problem statement . . .Your task is to find a maximum sub-rectangle on the grid (x1, y1, x2, y2). . . .
 » 6 years ago, # |   +1 Missed the round — no mail?
•  » » 6 years ago, # ^ |   +6 Check spam folder.
 » 6 years ago, # | ← Rev. 2 →   +124
•  » » 6 years ago, # ^ |   +7 Translation please? :o
•  » » » 6 years ago, # ^ |   0 wow wow clars, be easier)
 » 6 years ago, # |   0 How to solve Div2 D?
•  » » 6 years ago, # ^ |   0 first make a and b coprime try to max the length of x such that x%a=0, then check if y falls in range. if not, max y such that y%b=0
 » 6 years ago, # |   +43
 » 6 years ago, # |   0 Lots of hacks on A div2 with test "10000", library solution on B div2 on Delphi, unprepared B div1. Nice.
•  » » 6 years ago, # ^ | ← Rev. 2 →   +7 python lol))) from datetime import date a1 = map(int, raw_input().split(":")) a2 = map(int, raw_input().split(":")) print abs((date(a1[0], a1[1], a1[2]) - date(a2[0], a2[1], a2[2])).days) 
 » 6 years ago, # |   +108 I'll just put it here. http://en.wikipedia.org/wiki/Cyclic_number
 » 6 years ago, # |   +1 I think the limit of n for A div 2 should be 10^3 or 10^5. Most of my room has a O(n^2) solution. Especially a nearly O(n^2*log(n)) succesful in defended 2 attack.
 » 6 years ago, # |   +125 http://en.wikipedia.org/wiki/Cyclic_numberno comments
 » 6 years ago, # |   +24 Because of so many mistakes, I strongly think this round should be unrated.
•  » » 6 years ago, # ^ |   0 if so, this will third continuous unrated contest :)
•  » » 6 years ago, # ^ |   +4 I agree with you.The questions were published so late that we had misunderstanded the problem and wasted much time. BTW, the D is a popular knowledge which you can find it on the Internet.So, I hope this round will be unrated.This is the only way to make it fairly.
 » 6 years ago, # | ← Rev. 5 →   -40 Dynamic scoring usually makes scoring very different from past. Will it influence the rating system?
•  » » 6 years ago, # ^ |   +7 this is called dynamic scoring
•  » » 6 years ago, # ^ |   +3 It's dynamic scoring
 » 6 years ago, # |   +15 What a funny round!
 » 6 years ago, # |   -21 Great round, interesting problems. :-)
 » 6 years ago, # |   0 The problem is nice,but clarifications too disturb.Waiting for next round.
 » 6 years ago, # |   +8 My O(N^2+k^2 a_max log a_max) solution passed system test of problem C with a lot of brunch-cutting... I think it is not intended...
•  » » 6 years ago, # ^ | ← Rev. 2 →   +7 an O(n^2+ans*k^2+a_max ln ans) solution was expected.
•  » » » 6 years ago, # ^ |   0 Sorry, I mistook the analysis of my order... My solution was your order, thank you.I think TL is too short because my solution passed in over 1800ms with a lot of brunch-cuttings...
•  » » » » 6 years ago, # ^ |   +13 Try to use array instead of vector, it speed up performance of my code dramaticaly in this problem.
•  » » » » » 6 years ago, # ^ |   0 Oh, thank you for your advise.
 » 6 years ago, # |   0 Nice problems. A lot of maths, but It's enjoyable. :)
 » 6 years ago, # |   +5 Intereting problems!
 » 6 years ago, # |   +50 The data for div1 D seems weak. When N=1, it's clear that every base works, so the answer is x-1 if x > 2 and -1 if x = 2. However, some solutions that didn't handle these cases still passed system tests. For example, 3709363 gives 1 on the case "1 2".
 » 6 years ago, # |   +5 What is the solution for problem Div 1 — C (Div 2 — E) (Minimum Modular)?
 » 6 years ago, # | ← Rev. 2 →   0 System testing of Div.2 was very bad.it was finished , but final standing was not ready!
 » 6 years ago, # |   +9 Div.2 AMy code is TLE. ~~~~~ ans=sqrt(0.0+SQ(i)+SQ(j)); if( ceil(ans)==ans ) cnt++; ~~~~~ But I change “(int)ans==ans” ,then get AC....TvT
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 Check out mine 3706566. I think problem is in ceil() and floor(). Got AC replacing floor(c) with (int)c — 3712951. I would like to say : Authors, How about increasing time limit to 4s ? but it's too late. I have already got my Wow you have +67.
•  » » 6 years ago, # ^ |   +1 i too used ceil() function and TLE...
•  » » 6 years ago, # ^ | ← Rev. 2 →   +8 It would be better that you check your solution in custom test before submitting....
 » 6 years ago, # |   +1 ORZ failed div.2 A
 » 6 years ago, # |   0 For Div2 C, now I understand why I could not find any formulas for even values of n..
 » 6 years ago, # |   0 Weak pretests :(. B-Wa 11 because of mixing up n and m.
 » 6 years ago, # | ← Rev. 2 →   0 Wow constraints were really strict. My DIV2 A didn't pass because of the c++ floor method which is too slow, compared to a cast. For DIV2 B, why doesn't it work using mktime and difftime from ctime? ...
•  » » 6 years ago, # ^ |   0 http://codeforces.ru/contest/304/submission/3706514Are you still sure that's because of floor()?
•  » » » 6 years ago, # ^ |   0 Well I did some tests:
•  » » » » 6 years ago, # ^ |   0 843 ms with cast1609 ms with floor()But it doesn't mean that solution with floor can't be accepted
•  » » » » » 6 years ago, # ^ |   0 Sure, your solution passed :)I just noticed you were using VC++ compiler, and me gcc. After some research, it seems that VC++ generate a more optimized code than gcc, so the floor method could be optimized as well: http://stackoverflow.com/questions/3752988/gcc-vs-ms-c-compiler
•  » » 6 years ago, # ^ |   0 mktime() : convert local time to seconds since the EpochThe Unix epoch is the time 00:00:00 UTC on 1 January 1970 (or 1970-01-01T00:00:00Z ISO 8601).http://en.wikipedia.org/wiki/Unix_time
 » 6 years ago, # |   0 my final tests are checked but its showing skipped what does it mean????? http://www.codeforces.com/contest/304/submission/3709339 please clarify it...
•  » » 6 years ago, # ^ |   +9 Are you sure your solution is your own, not copied from others?
 » 6 years ago, # |   +18 Screencast: http://youtu.be/XWsPoC4p-EY?hd=1
•  » » 6 years ago, # ^ |   +29 add music))
 » 6 years ago, # |   0 How to get full test cases for: http://codeforces.com/contest/304/problem/E?Thanks!
•  » » 6 years ago, # ^ |   0 Check the submission of Ents : http://www.codeforces.com/contest/304/submission/3710988
•  » » » 6 years ago, # ^ |   0 In the submissions large input data are cut.
•  » » » » 6 years ago, # ^ |   +4 you can't get large test cases
 » 6 years ago, # |   +307 Having spent about 20 submissions trying to find out the reason of my wrong answer on test 8 in Div1-E, I've managed to receive the following outcome from the judge:wrong answer 201st numbers differ — expected: '-0.0132824', found: '0.0124727', error = '0.0257551'This doesn't look like a correct probability, does it?
•  » » 6 years ago, # ^ |   +69 I've got TLE 8 during the contest, but later I optimized my solution a bit and now it's giving the same answer as yours on the 8th test even when I use long doubles.
•  » » 6 years ago, # ^ |   -36 All tester's program have different solution so you know
•  » » 6 years ago, # ^ | ← Rev. 2 →   +1 the model solution of E is wrong...it has precision problem.the setter is trying to fix it... but still rng58'solution seems has precision problem too...actually they all work fine when n=40, but start to differ when it become bigger,when I change the double in model solution to long double,it seems it is the same answer with KADR.
•  » » 6 years ago, # ^ |   +48 I've asked the author to give me his solution, and the author's solution returned even worse answer (smaller than -10000) for the following case:int main(void){ int i; cout << 80 << endl; for(i=0;i<80;i++) cout << i << ' ' << i+80 << endl; return 0; }My solution during the contest (got WA) also contained precision errors for this case. The probabilities were between 0 and 1, but the sum of the probabilities in some row was more than 22 (while it should be 0).Currently I guess it's impossible to solve this problem precisely under the given constraints.
•  » » » 6 years ago, # ^ |   +26 That is really bad.I think this round should be unrated to you QAQ.
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   -13 yes, if his solution is realy correct
•  » » » » » 6 years ago, # ^ |   -11 Yes, they can.
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +11 tourist's solution has no precision problem, but it run in O(n^5),maybe too slow. (it run 1890ms,barely in time:) )I optimize it and work out an O(n^4 logn) solution,I guess now it is ok:3716717
•  » » » » 6 years ago, # ^ |   +8 In attempt to make my Java version go through the time limit (without use of if (l[i] <= L && r[i] >= R) elimination) I gradually optimized it and after succeeding I also found out that Gena's (with or without your great asymptotics improvement) solution can still be noticeably optimized. :) Initial version: http://codeforces.ru/contest/303/submission/3716717 With two code optimizations: http://codeforces.ru/contest/303/submission/3718523
•  » » 6 years ago, # ^ |   +43 Yes, you are right. The author's solution is wrong for that tetscase. But all the pretests were right.So, now we are discussing how to solve this problem with precision and make the results of the round as fair as possible. Thanks for the notification!
•  » » 6 years ago, # ^ | ← Rev. 2 →   +12 I have seen you solution, it is a good idea but it actually run in O(n^5),maybe there's some test can make it TLE （the inner running time is (the number of segment contain givn sub-segment)^4. I have optimize it a bit and now it run in O(n^4 logn). check it 3716717 here. Now I think this problem is solved.
•  » » » 6 years ago, # ^ |   +28 It seems that my solution's running time doesn't depend on the actual test case as long as li ≠ lj, ri ≠ rj and li < rj for all i and j. A gap of 110 ms is not big enough, though :)Your optimization is nice, thanks! Now the problem is really solved.
•  » » » » 6 years ago, # ^ |   0 I checked WJMZBMR's n^4logn code and i believe that it has precision problem too, though it pass all the test datas.Besides, I guess it may require O(n^5) to get the right answer, and so i suggest either enlarge the time limit or reduce the size of n ;)
•  » » 6 years ago, # ^ |   +63 We discuss for a long time with a setter this problem. So we change the solution to a correct one. All the solutions that passed pretests at the contest failes on the system test as expected. So, this problem doesn't affect on the participants, because the pretests were right.My appologize for this situation. And great thanks to tourist for the notice!
•  » » 6 years ago, # ^ |   0 Can you write tutorial for this problem?
 » 6 years ago, # | ← Rev. 3 →   0 It seems I solved 303C - Minimum Modular with brute force 3712393 which, I think, is O(5000*10^6) in the worst case.Is there any testdata which challenges the program or I calculate the complexity wrong?
•  » » 6 years ago, # ^ |   +8 Your solution is not brute, cause you calced values s and use them as optimization. Your solution is very close to right solution.
 » 6 years ago, # |   0 Can anyone provide a proof of Div I Problem A? I just noticed the pattern for n <= 10 and just submitted that hoping it would work.
•  » » 6 years ago, # ^ | ← Rev. 4 →   +8 EDIT : The proof I have post is wrong. See the comment below.
•  » » » 6 years ago, # ^ |   +3 Please correct me if I am wrong, but I am not getting the proof.When you say even-odd pairs, does that mean all the evens come from A and all the odds from B. But, we can still get n/2 odd by mixture of ( E,O) And (O,E). Precisely n/4 (E,O) and n/4 (O,E). And same applies for getting n/2 evens. In essence this points that we can still gets the even-odd configuration.
•  » » » » 6 years ago, # ^ |   +8 You are right. Sorry for having post a wrong proof.
•  » » » » » 6 years ago, # ^ |   0 No problem at all. Actually, this is way I was trying to prove that any configuration possible not for even n. I just got proved that if n is even and if it is not divisible by 4 then there is no configuration with the above reasoning. If you get the proof using the above logic please let me know.
•  » » 6 years ago, # ^ | ← Rev. 3 →   +46 If , then or just , where S = 0 + 1 + ... + n - 1 = n(n - 1) / 2. So, there must be . But when n is even, .
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +9 Where S=0+1+2+3+...n-1=n(n-1)/2
•  » » » » 6 years ago, # ^ |   +1 Thank you, fixed.
•  » » » 6 years ago, # ^ |   0 this is fine, i got the logic, but how to get the sequence as all sequences are not valid. your formula just tell if a valid sequence is possible or not.
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   0 for N is even output -1 for N is odd the two permutations like this: 0 1 2 3 4 ... n-1
 » 6 years ago, # |   +3 For this very fast solution to problem A in div2, could someone explain the math behind it? Thanks.
•  » » 6 years ago, # ^ |   +1
 » 6 years ago, # |   +6 How to solve div2 E-Minimum Modular? Thanks in advance.
•  » » 6 years ago, # ^ | ← Rev. 2 →   +44 means "ai - aj is not divisible by m. So calculate the differences of all pair of integers.We check that "if we choose m to modulo, we can do the array satisfies conditions?" for all integer m until we find m from (n-k).Answer ≤ 106 + 1 because if we choose 10^6+1 for m, obviously it satisfies condition.When we search about m, all we have to do are research about multiple of m and get the array of "Which pair of integers are same modulo m". If the size of array exceed 10(), give up search.In this solution, the order is O(N^2+a_max log a_max+k^2 a_max) because O(1/1+1/2+1/3+...1/a_max)=O(a_max log a_max).
•  » » » 6 years ago, # ^ |   0 Similar solution of mine in Java (3754545) gets TLE. I think time limit is very tight for java solutions. Any thought?
•  » » » » 6 years ago, # ^ |   +5 Replacing ArrayLists to Arrays makes it much faster. I got AC. Lesson learned.Thanks.
 » 6 years ago, # |   0 When will the editorial be published? I really want to know how to solve Div1E...
•  » » 6 years ago, # ^ |   +5 The editorial has been published, but It is doesn't have solutions for Div1 D and E http://codeforces.com/blog/entry/7641
•  » » » 6 years ago, # ^ |   +3 Thank you so much! I'm going to continue to think about Div1E.
 » 5 years ago, # | ← Rev. 3 →   0 I think intended solution of Div I E is incorrect(or problem description is incorrect):I have test some AC code for this case: 3 1 10 1 10 1 10I think the correct answer is 0.25 0.5 0.25 0.25 0.5 0.25 0.25 0.5 0.25 but seems AC code's answer is 0.3333333 0.33333333 0.333333333 0.3333333 0.33333333 0.333333333 0.3333333 0.33333333 0.333333333obviously for each person rank 2's probability is higher than 1 or 3,be cause there are two kind cases for p2: p1p3