### boleyn.su's blog

By boleyn.su, 7 years ago,

Hi, Codeforces Round #221 will take place on December 24th at 18:00 MSK for both divisions.

Problem setters are whd, oGhost and boleyn.su. This is our first Codeforces Round, and we hope it will be a good one.

We'd like to thank Gerald and alpc104 for helping us prepare this round, and MikeMirzayanov for bringing all of us a place to compete and communicate with others.

The score distribution will be announced before the contest starts.

UPD1: The score distribution is 500-1000-1500-2000-2500 for both divisions.

UPD2:

Congratulations to winnners and Merry Christmas to ones who celebrate it today!

Div 1:

2.al13n

3.rng_58

5.uwi

Div 2:

1.bohuss

2.Tyg3R

3.xhsong

5.Kira96

• +237

 » 7 years ago, # |   +2 Good luck
•  » » 7 years ago, # ^ |   +19 And Merry Christmas (note the date)
 » 7 years ago, # | ← Rev. 3 →   -38 Hope the contest won't be like the last contest( Hard && Unrated ). Good luck to eveyone!!!
 » 7 years ago, # |   0 Good luck ... :)
 » 7 years ago, # |   +16 Maybe people can already assume that every round announcement has some kind of grateful acknowledge to MikeMirzayanov, since it's becoming a bit boring to read that part every single time.
•  » » 7 years ago, # ^ |   +27 then don't read that part! :D
•  » » 7 years ago, # ^ | ← Rev. 2 →   -51 +1!It is more like fetishism. We really have to eradicate this practice.UPD: no disrespect was meant to Mike at all.
 » 7 years ago, # |   -37 If this is the last round this year...HAPPY NEW YEAR TO ALL :D
•  » » 7 years ago, # ^ |   +17 The last round 's Good Bye 2013. It will take place on the last day of this year :-)
 » 7 years ago, # |   +9 Why this blog isn't on the home page !?
 » 7 years ago, # |   +44 Contest in Christmas Eve? And on top of that — at 18:00? Weird idea. I'm not familiar with Russian traditions, but in Poland at that time we usually gather with family around table and celebrate Christmas Eve :P. Other days will be better or at least earlier hours. Even though I will try to compete :P. In Poland it's not that bad hour, because it will be 15 :P.
•  » » 7 years ago, # ^ | ← Rev. 3 →   +3 Pay attention to where the three round makers come from.They come from Renmin University of ChinaThe round will take place at 18:00 MSK means 22:00 CST.BTW, as a freshman,it's always hard for me to make a decision whether I should take part in a round start at 19:30 MSK or not , because if I do, I have to coding from 23:30 CST to 01:30 CST while my roommates are sleeping, which may bothers them.(In my school, a student should never stay outside domitory after 23:00)
•  » » » 7 years ago, # ^ |   +3 Wouldn't the round writers have it better if the round was earlier?
•  » » » 7 years ago, # ^ |   +8 Are you sure that your roomates are sleeping at 23:30 CST? hehe
•  » » 7 years ago, # ^ |   +24 Christmas is not celebrated on 25th of December in Russia, see this wikipedia link. And even on 7th of January Christmas is not celebrated that widely comparing to how they celebrate it in Europe for example. In Russia people mostly celebrate New Year.
•  » » » 7 years ago, # ^ |   +8 Your snow bear looks so cute! cute cute cute!!!
•  » » 7 years ago, # ^ |   +3 The Orthodox calendar isn't affected by the Gregorian correction (not everywhere, though), so Christmas in Russia should be shifted to 13 days later. Still, 24th this late is not the best choice.
•  » » 7 years ago, # ^ |   +19 You really are in no position to comment about "no-lifes" on my youtube videos if you plan on participating in a contest on 3pm-5pm Christmas Eve. ;)
•  » » » 7 years ago, # ^ |   +19 OK, you convinced me. Tomorrow at 3pm I'm going to watch your whole screencast :P.
•  » » » 7 years ago, # ^ |   +5 Yay, I participated and took in my opinion really good place — 38th :D!
 » 7 years ago, # |   +8 Wow, three problem setters Chinese from RU! Look forward to it!
•  » » 7 years ago, # ^ |   +9 In fact, RUC is short for Renmin University of China, while RU is not.By the way, I was born in Chongqing. It is good to see students from my hometown attending our contest. Good luck and have fun!
•  » » » 7 years ago, # ^ |   +8 That's so sweet. Thanks!
 » 7 years ago, # |   +8 king base!time is good for chinese,thx for setter
 » 7 years ago, # |   +8 Good time for chinese..
 » 7 years ago, # |   -27 Люблю задачи от новых авторов)
•  » » 7 years ago, # ^ |   -37 Но решать их ты, видимо, не любишь.
•  » » » 7 years ago, # ^ |   -30 :)
 » 7 years ago, # |   +1 Looking forward to it ! When the contest ends, it will be Christmas in China and we will have to go to school as usual ...
 » 7 years ago, # |   -17 I love this contest!
 » 7 years ago, # |   -47 Hope a better Contest than the previous one... That was not a Contest...
 » 7 years ago, # |   +6 hope every contestant can have fun with the problem set :D
 » 7 years ago, # |   0 Have you changed the contest time or i need some sleep :) ?
 » 7 years ago, # |   -129 Up-vote this comment if you can :P
•  » » 7 years ago, # ^ |   +28 It is very hard. We can't. Sorry.
•  » » 7 years ago, # ^ |   +9 Let me guess. After seeing some people in the last two contests, asking for downvote and getting them, you thought this would work!? If only it was that easy :p
•  » » » 7 years ago, # ^ |   -21 I did this only for other guys like you to get up-voteed.
 » 7 years ago, # |   -18 Good time for Chinese contestant! Thanks!pingshi maozi tai qifu ren le, banyesangengde naozi dou bu zhuan le.
 » 7 years ago, # |   0 I hope this contest be creative.
 » 7 years ago, # |   0 Good Rate on Codeforces and Happy New Year))))
 » 7 years ago, # |   0 10 minutes before the contest and no score distribution published!
•  » » 7 years ago, # ^ |   +34 Surely we should unregister and not participate in the contest if we don't know the score distribution.
•  » » 7 years ago, # ^ |   +5 just solve problems and have fun :)
 » 7 years ago, # |   +3 Just for Remember you said The score distribution will be announced before the contest starts.
•  » » 7 years ago, # ^ |   +9 Chill. 2 more minutes left. That's like 120 seconds. Plenty of time to update the score distribution.
•  » » » 7 years ago, # ^ |   0 Now it's 30 second only do you still think that ?
•  » » » » 7 years ago, # ^ |   +80 I posted it 16sec before contest started.
 » 7 years ago, # |   0 Power belt, I have late for contest and registration. WHY registration starts at late evening? Should it be possible to open registration 1,5 day before contest?
 » 7 years ago, # |   +30 Merry Christmas and Happy Halloween (Note : OCT 31 = DEC 25 :D )
 » 7 years ago, # |   0 Maybe I have a chance to go to div1...thx...
 » 7 years ago, # |   +5 nice contest!,but what is the algorithm to solve problem C DIV 2 or problem A DIV 1?
•  » » 7 years ago, # ^ |   +5 C is pretty simple actually if you think of the reason why the setter used the digits 1,6,8,9. You can get all remainders when divided by 7 for some permutation of the digits 1,6,8,9. That is for every number x in {0,1,..6}, there exist a permutation of 1,6,8,9 such that when that permutation is divided by 7, it leaves a remainder of x. I think with this hint you might be able to complete the solution.
 » 7 years ago, # |   0 Will there be a tutorial published?
 » 7 years ago, # |   +11 Yeah.. Div1 is too hard to me.. I'd better back to div2...
 » 7 years ago, # |   0 Saw few people use sort in problem B div 1. O(n*nlogn) should get TLE right? I went out of my way to use bucket sort to keep it O(n^2).
•  » » 7 years ago, # ^ |   +6 Sorting? I'm kinda scared now. I didn't use sorting. At all.
•  » » 7 years ago, # ^ |   0 I didn't use sorting too, I think n^2*logn should TLE.
•  » » 7 years ago, # ^ |   0 5506448Sorting, no TLE =)
•  » » » 7 years ago, # ^ |   0 Okay this is weird. I generally assume, 10^8 calculations take 1 second. So O(n*nlogn) is (5000*5000*12)/10^8 = 3 seconds. Time limit is 2 seconds. Since it didnt get TLE, I guess CF is a lot faster than I assumed. So how fast is it? I did the bucket sort for nothing :(
•  » » » » 7 years ago, # ^ |   0 It seems like the compile-time optimizations by GNU C++ are able to make up for it somehow.. Even though that some solutions that used sorting were either hacked or didn't pass the systest, so it's kind of tricky to guess whether a solution will pass or not just by looking at the source code.
•  » » 7 years ago, # ^ |   0 mine was O(n*nlogn) and it passed... :)
 » 7 years ago, # |   +19 Is cin very fast on codeforces? I was surprised that cin solutions worked in B.
•  » » 7 years ago, # ^ |   +6 At least it is fast enough with this:  ios :: sync_with_stdio(false); I always use cin in CF and until now I haven't get a TLE by it.
•  » » 7 years ago, # ^ |   0 according to my testing, on GNU c++ 4.4 and above cin/cout work very fast and compareable to scanf/printf :p
•  » » 7 years ago, # ^ |   +5 I think the reason is codeforces judges is really fast.At beginning, we do not want n^2logn solution pass, but failed to generate a testcase. I am really surprised by the speed of judge computers.
•  » » » 7 years ago, # ^ |   +1 my n*m got TLE.
•  » » » 7 years ago, # ^ |   +13 My O(N.M.logN) get TLE ! be happy :)
•  » » » 7 years ago, # ^ |   0 Yes, I saw a solution that uses cin without sync_with_stdio, sortings of n elements n times, and push_backs n2 times — still worked under 2s :)
•  » » » 7 years ago, # ^ |   +1 My solution with cin get TLE. 5505467
•  » » » » 7 years ago, # ^ |   0 It seems it was quite close to the boundary.
•  » » » 7 years ago, # ^ | ← Rev. 3 →   0 my solution 5506320 O(N^2) using scanf("%c",&x); got TLE, change it to x = getchar() got AC 5511177 under 0.5 s, i wonder why is scanf("%c") so slow ?
•  » » » » 7 years ago, # ^ |   +8 Cause it parses format string "%c" on each query, at least.
•  » » » » 7 years ago, # ^ |   0 My O(n^2log(n)) solution 5515627 and O(n^2) solution 5515601 actually got the same running time. But during the contest I use scanf("%1d", &a[i][j]) to read the digit one by one, and it turns out the this is the bottleneck in my TLE code 5510016 ..
 » 7 years ago, # |   0 how to solve problem c?
 » 7 years ago, # |   +12 Problem Maximum Submatrix 2 is essentially exactly the same problem as http://www.ceoi2009.ro/tasks/logs.pdf :(
•  » » 7 years ago, # ^ |   +3 And problem B in DIV 2 is almost the same as http://www.spoj.com/problems/ANARC08G/
•  » » » 7 years ago, # ^ |   +24 Div1 A is almost the same as http://acm.timus.ru/problem.aspx?space=1&num=1095
•  » » 7 years ago, # ^ |   0 We got the idea of this problem from one of our algorithm class homework.
 » 7 years ago, # |   0 Need hints for problems C div 2 :(
 » 7 years ago, # |   0 Need hints for problems C div 2 :( soon :D
•  » » 7 years ago, # ^ |   +13 That problem looks very artificial to me, these numbers must have some magic.So I submit a crazy solution 5502926: until find a solution, do some random swaps, and if time out then output 0. And it passed system test.Seems it can't be no solution, but I don't know why. :)
•  » » » 7 years ago, # ^ | ← Rev. 4 →   +11 For every 0 ≤ r < 7 there is a permutation of {1,6,8,9} that (being read as a 4-digit number) yields remainder r when divided by 7. Choose the right one and append all the other digits to it.
•  » » » » 7 years ago, # ^ |   -16 Even more than that, for every integer a, there exists a permutation of {1, 6, 8, 9} that is appended to a and makes the result number divisible by 7. :)
•  » » » 7 years ago, # ^ |   0 You can rearrange 1,6,8,9 to form all mods from 0 to 6 -- so just order the rest of the numbers in any order, then output the correct permutation: http://codeforces.com/contest/375/submission/5507138
•  » » » 7 years ago, # ^ | ← Rev. 2 →   0 For each 0<=r<7, there exists a permutation of {1,6,8,9} as (r*10 000 + permutation) % 7 = 0 So, you choose a random order for the initial number (just conserve one 1, one 6, one 8, one 9 and count number of zeros), then you calculate the rest of this number, and you choose the valid permutation of {1,6,8,9}. You can then add as many 0 as you want lastly.sample: 123456789 -> (23457 * 10 000 + permutation) % 7 == 0 -> permutation = 1869 (and with zeros:) 1230000456789 -> (23457 * 10 000 + permutation) % 7 == 0 -> permutation = 1869 -> result = 2345718690000
•  » » » » 7 years ago, # ^ |   0 Please explain why this approach can be true ? I don't understand :(
 » 7 years ago, # |   0 Very interesting problems, and no complex algorithm. LIKE it:) [Although i have solved a little tests] Hope u can papare more contests in the future!!
 » 7 years ago, # |   0 Need hints for problems C div 2 :( soon :D Sooooooooooooooon
 » 7 years ago, # |   0 Are u kidding? N log^2 N solutions in D that use dat slow c++ map pass with a great handicap. Well, maybe I'm unfair cause I spent alot of time doing N log N solution, but I bet on weak tests.
•  » » 7 years ago, # ^ |   0 100000 * 18 * 18 < 100*10^6
•  » » » 7 years ago, # ^ |   +5 That's too rude, u don't assume that map is a redblack tree and we keep pairs in it.
•  » » » » 7 years ago, # ^ |   0 One of logs, which going from merge is very small. Also maps are not very big mostly. Probably this two compensate.
•  » » » » » 7 years ago, # ^ |   0 There are even O(n * sqrt n * lg n) AC solutions, I really believe that the nature of the queries, at most n different ranges, (without partial overlaps) really improves O(n sqrt n) bound.
•  » » » » 7 years ago, # ^ |   0 I used a hash map (unordered_map) instead of a normal map, and the fenwick tree is tremendously fast, so the additional log n factor is quite reasonable, I was skeptic during the contest (and even tried to find an O(n lg n)), it also seems that Codeforces got some speedy machines.
•  » » 7 years ago, # ^ |   0 I think you did something wrong, O(N log N) solution isn't very hard. See 5512577.
•  » » » 7 years ago, # ^ |   0 Well done, but that wasn't actually a topic of my message =)
•  » » » 7 years ago, # ^ |   0 Indeed, but it was tricky to realize that is actually O(n lg n) during the contest, those who saw that all the updates are O(n) amortized mostly implemented an O(n sqrt n), the rest just used a Fenwick tree. BTW it would be interesting to find the worst case input for the O(n sqrt n) approach, here the tree structure makes the query ranges quite singular (no partial overlapping), maybe in this case is even better, O(n lg n) or even O(n)?
 » 7 years ago, # |   +14 And for second time in a row a purple coder takes down the Div 1. Congratulations, Touma_Kazusa :).
•  » » 7 years ago, # ^ |   +12 In fact, she is red for a very long time.
•  » » » 7 years ago, # ^ |   0 In fact, she is one of the top rated users.
•  » » » » 7 years ago, # ^ |   +27 Can you tell us who is that?
•  » » » » » 7 years ago, # ^ |   +11
•  » » » » » » 7 years ago, # ^ |   +41 :(Are you sure?The rules: "Don't create more than one account, if you have forgotten the password, use the password reminding system."
•  » » » » » » » 7 years ago, # ^ |   +16 Even if the rules should be applied more or less to everybody, I don't think it was an attempt to cheat, or because the password was forgotten, but an other reason (which one, I don't really know). The only thing that seems unfair it's that will affect rating changes of all others contestants. I mean, I suppose that being beaten by a purple when you are red/orange make your final rating lower than if you're beaten by a top 10 user...
 » 7 years ago, # |   0 in problem D,why my O(n*m) solution get tle? 5509804
•  » » 7 years ago, # ^ |   0 Try to use getch() or smth other, not cin.
•  » » » 7 years ago, # ^ |   +24 Getch()? Pff. ios::sync_with_stdio(0); is enough to use cin and get AC =)
•  » » » » 7 years ago, # ^ |   0 5511181Just as I said.
•  » » » » » 7 years ago, # ^ |   0 can you explain me why it is so improtant? and what this doing?ios::sync_with_stdio(0);
•  » » » » » » 7 years ago, # ^ |   +3 It is turns off synchronization with stdio (scanf/printf), so cin/cout can work faster. More information here.
•  » » 7 years ago, # ^ |   0 Well, I guess because of this lineans=max(ans,(j-i+1)*num[j][i]);This line causes many memory hits, you need to access the array in row major orderswap j, i in the loops or in the array dimensions (make it num[i][j])
•  » » 7 years ago, # ^ |   0 i think problem is with your input.
•  » » 7 years ago, # ^ |   0
•  » » » 7 years ago, # ^ |   0 'getch' was not declared in this scope,what can i do?
•  » » » » 7 years ago, # ^ | ← Rev. 2 →   0 "#include "
 » 7 years ago, # |   +1 thanks pretest #11, for problem A (div-2).
 » 7 years ago, # |   +1 Could someone explain the solution of Problem D? Thanks in advance
•  » » 7 years ago, # ^ |   0 you mean in Div2?
•  » » » 7 years ago, # ^ |   0 Yes
 » 7 years ago, # |   +5 How to solve E div 2 / C div 1?
 » 7 years ago, # |   +16 The "Custom test" feature here limits testcase input to 256KB, but the maximal testcase for "Maximum Submatrix 2" (Div 1 B, Div 2 D) has a 5000x5000 matrix (25M elements), so it seems impossible to properly test the maximal case for TLE against Codeforces servers (even if you hardcode the testcase in the source, you're circumventing the time taken reading input). Is there any good strategy for handling this, or any way around this restriction?
•  » » 7 years ago, # ^ |   0 Use a genarator code.
•  » » » 7 years ago, # ^ |   +13 That works for hacking, but not for testing your own solution in custom test.
•  » » » » 7 years ago, # ^ |   +5 Oh yeah. My bad. I misread. Maybe the custom Test is not meant for stress testing.
 » 7 years ago, # |   0 F@uk...Pro D,,my time is n*m*logn.....TLE.= =
 » 7 years ago, # |   +1 What does I.O.U (name of problem B of Div 2) stands for?
•  » » 7 years ago, # ^ |   +3 I owe you
 » 7 years ago, # |   0 I don't understand why in B/D n<=5000. Many people submitted correct solution, but because of using (in my case cin) got TLE. I think n<=1000 would be enough for solutions with bad asymptotics to not pass.
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 I got n*m solution but because using "cin" got TLE.if n <=1000 than it can be solved also n*m log m and it did not want to author,I think author is strict in this issue.
 » 7 years ago, # |   +10 Am I missing an easy solution to Div1 D or so many people have managed to code solution that resembles mine? I've done it by an algorithm which resembles heavy-light decomposition. I've done DFS, computed some data for every subtree and in one vertex I copied the data from smaller subtrees to the biggest one, which results in O(n log n) solution. I was really satisfied to get this problem accepted :).
•  » » 7 years ago, # ^ |   +5 Can you explain more detailed your solution? In Russian comments here we discussed accepted solutions in O(Nlog2N) with the same "copy data from smaller subtree to the greater one" idea, but the data was stored in log-time containers, such as Cartesian trees and Fenwick trees, so asymptotic was O(NlogN·logN) = O(Nlog2N).
•  » » » 7 years ago, # ^ |   +6 There is also a solution with complexity O(N * log^2(N) + (Q + N) * sqrt(N)) without advanced data structures, by splitting the set of colors into heavy and light sets such that light set contains colors that have < sqrt(N) elements and heavy set contains colors that have >= sqrt(N), then the light sets could be processed with simple dp on tree, and heavy sets could be computed using the "copy data from smaller subtree to the greater one" idea because there is at most sqrt(N) heavy colors.
•  » » » 7 years ago, # ^ |   +14 Here is my code that got accepted: http://codeforces.com/contest/375/submission/5508056For every vertex v I call DFS(v, log) where log is some number between 1 and log n. If vertex v has children v1, ..., vk and vertex v1 has the biggest subtree, I call DFS(v1, log) and DFS(v2, log + 1), ..., DFS(vk, log + 1). If I call DFS for vertex v with corresponding argument log, after calling DFSes for its children I want to have some data in col_num[log], at_least[log] and ver[log]. For fixed color c, col_num[log][c] means how many there are vertices in this subtree with color c, for a number k, col_num[log][k] means how many there are colors c such that col_num[log][c]>=k and ver[log] is simpy vector of all colors of vertices in this subtree. Those data allow us to simply answer all queries in each vertex and update corresponding data in our parent in time O(size of our subtree) (if we aren't the biggest subtree's of our parent's children's subtrees) which results in O(n log n) complexity of whole algorithm. If our subtree is the biggest subtree of our parent's children's subtrees, our parent just treats our complete data like its initial data and update it by other children subtrees.
 » 7 years ago, # | ← Rev. 12 →   0 Power of MS C++!!! I think if lots of TLE codes submit their codes with MS C++ compiler, they will get accepted! Accepted Solution: 5511246 and 5511362 and 5511553 TLE Solution : 5511075 and 5507435 and 5505552 I submitted these TLE solutions with compiler MS C++ and got AC! What is the real reason?
•  » » 7 years ago, # ^ |   -10 problem B sux
•  » » 7 years ago, # ^ |   +2 you can't strongly say that MS C++ is better than GNU C++. The difference is that cin and cout have been defined differently in these two compilers. The time of cin in MS without ios_base::sync_with_stdio(false) and with it is really close, however there is a massive difference in GNU with ios_base::sync_with_stdio(false) and without it. But GNU is faster with syncing than MS with it. I can show u a lot of codes which got acceptance with GNU with syncing that same code in MS didn't.
 » 7 years ago, # | ← Rev. 2 →   +4 Div.2 Problem D I add ios::sync_with_stdio(false); and pass.........Can anyone help to explain?!What a pity...
•  » » 7 years ago, # ^ |   0 cin works faster with ios::sync_with_stdio(false);
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 Explanation here.Also some statistics here.
•  » » 7 years ago, # ^ |   0 I think it is almost always better to use scanf instead of cin.
•  » » » 7 years ago, # ^ | ← Rev. 2 →   +1 You're wrong. If you use cin with ios::sync_with_stdio(0); on GNU-C++ your solution may be even faster than with scanf as you can see here.
 » 7 years ago, # |   -8 Feel quite disappointed about the problems setter (or the translator) of problem D div 2. You can rearrange the row but each col MUST BE ORIGINAL
•  » » 7 years ago, # ^ |   +12 I am sorry for that.
 » 7 years ago, # |   +1 Div.2 Problem D: priority_queue got TLE (AC in MS C++), push in vector and sort got AC :(
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 I guess that why we usually prefer quicksort to heapsort :)
 » 7 years ago, # |   0 I don't know about you guys but I used a physics formula for Div 2 A. Is there any other solution?
 » 7 years ago, # |   +44 Thanks for nice contest! It requires an ability to write fast without bugs not-completely-simple code in each task.
 » 7 years ago, # | ← Rev. 2 →   0 Can someone please tell me where my solution for div2-C is failing? I made use of the mathematical trick of finding %7 for large numbers.http://codeforces.com/contest/376/submission/5506741UPD: Found my mistake. Thanks to Zlobober ! :)
•  » » 7 years ago, # ^ |   0 Your idea is quite right but you should add your mp[remmod] to the end of the answer, because it will give the right remainder, but not 10^(len — 4) * right remainder. http://codeforces.com/contest/375/submission/5504410 -- my solution.
•  » » » 7 years ago, # ^ |   0 Adding mp[remmod] to the end is wrong because that can cause leading zeroes.In any case, I found my mistake a while back and corrected it. :) Thanks!
•  » » » » 7 years ago, # ^ |   0 Well, you can add all zeroes to the end, as in the author's solution.
•  » » » » » 7 years ago, # ^ |   0 Not quite. I'll give you an example.No zeroes in this case, so according to you I should add mp[remmod] to the end. But it is wrong.Test Case : 11689 Output : 18961 ( = 5 mod 7 )
 » 7 years ago, # |   0 It is realy unfair..... algorithm and and implement is correct only because of ios::sync_with_stdio(false); I get TLE....
•  » » 7 years ago, # ^ |   +5 You should try to study more about the ur programming language sometimes :)
 » 7 years ago, # |   +7 It was really best Christmas present, thank you very much and see you in DIV 1 :)
•  » » 7 years ago, # ^ |   +5 Congratulations!!!
 » 7 years ago, # |   +1 +100 :D
•  » » 7 years ago, # ^ |   +6 +174 ;)
•  » » » 7 years ago, # ^ |   +1 -15 :P
 » 7 years ago, # |   +8 It is recommended to test the maximal case locally. I think that it takes less than two minutes to write a code to generate maximal case.
 » 7 years ago, # |   -8 +198 :)
 » 7 years ago, # |   0 First of all, thank you for preparing the problems for us. It was a nice Christmas Eve. However, I would like to point out the problems is not very good (at least for me). For Problem B, it is EXACTLY THE SAME with CEOI 2010 Day 2 Problem 1 Logs (the only difference may be the problem from CEOI asks rearranging the columns). And for problem C/D, I cannot recall clearly the source of these problems but I have solved tons of problems based on the old idea.I hope that Codeforces can have more problems with new idea instead of the old one. New idea may be easy, simple, interesting, ... but it is good. Anyway, problem A/E is really nice (maybe adapted from Chengdu Onsite 2013?). I don't come up the solutions till now. Thank you again!
•  » » 7 years ago, # ^ |   +3 Well, if D has a nicer solution, than "move-info-from-smaller-subtree-to-larger" one with using some complicated data structures like maps, hashmaps, cartesian trees, fenwick trees etc (that are discussed above in Russian version of the site) then it would be great to know about them. Maybe when problemsetters publish editorial we will find more interesting solutions to it.And C seems very nice and interesting for me. Can you give a sample of the problem with the same idea? Moreover, if authors didn't have to explain, what does "inside the closed curve" mean, it would have been really cool problem (but with such explanation in task the idea to store a mask of oddity for each object becomes much clearer and obvious).
•  » » » 7 years ago, # ^ |   0 The Grove -- USACO 2006 January SilverAs far as I knew, this may be the first time this idea appears. The problem can't become cooler by replacing the definition into something like "reach from the infinite point" since it must allow multiple pass of one cell. It is not that natural.
•  » » » 7 years ago, # ^ |   +1 If someone has read this and not my explanation few posts above — yes, instead of maps, trees and other stuff, you can use arrays :D -> http://codeforces.com/blog/entry/10034#comment-155315But one one drawback is that this results in also O(n log n) memory, there are other approaches with those more complicated structures which requires O(n) memory only. But if it fits into limits, there's nothing wrong with it :).
•  » » » 7 years ago, # ^ |   0 "if authors didn't have to explain, what does "inside the closed curve" mean, it would have been really cool problem" — imagine a closed curve with many selfintersections (those are allowed in this problem!). Could you clearly state what's its interior and what's its outerior? These 2 words are losing their meaning and the only thing that can tell them apart is this parity definition.
•  » » » » 7 years ago, # ^ |   0 Yes, that's exactly what I meant by phrase "authors have to explain what does that mean". MainDullMoeHand in his comment above showed much nicer task, that deals with that problem another way. For that task there is no need to define what interior exactly is, because it uses only the "walk around the connected figure" conception, which is much simpler to imagine and doesn't require additional clarifications.
•  » » 7 years ago, # ^ |   +13 Problem A is not new at all — see there http://acm.timus.ru/problem.aspx?space=1&num=1095 There's about 2000 sucessful submissions on it on the most famous Russian online judge.
 » 7 years ago, # |   +13 I did not write this round well,but I liked problems very much,thanks authors for contest.
 » 7 years ago, # |   0 How did people use sorting to solve Div2 D / Div1 B? O.o
 » 7 years ago, # | ← Rev. 2 →   +17
•  » » 7 years ago, # ^ |   0 Awesome work, like previous stats. How do you make such requests on this website to get data? wget parser?
•  » » » 7 years ago, # ^ |   +3 Thanks! :)If I get your question right, requests are made using XMLHttpRequest from javascript. After the received html data is processed, graphs are built using Google Charts.
•  » » » » 7 years ago, # ^ |   0 Thanks for this fast answer!
 » 7 years ago, # |   0 Alternative problem for Div 1 A/ Div 2 C: Is there a simple solution at this problem: Find a permutation of a number n composed only by 1,6,8,9 digits (666,1689 etc...) divisible by 7 I tried to solve this problem during the thirty first minutes before finding my misunderstanding...
•  » » 7 years ago, # ^ | ← Rev. 2 →   +3 As long as there's at least one occurence of each of numbers 1,6,8,9 in that number, it's the same as Div1 A :DFor arbitrary numbers: if the input is small, you could do DP on (remainder,how many digits of each type you have left); if it's large, there are either few ways to solve it or a permutation should always exist, like numbers "16666666","61666666",...,"66666616" which give different remainders mod 7 — so it's enough to consider a random permutation of other numbers before it and choose the ending few digits that are good.
•  » » » 7 years ago, # ^ |   0 Ok, so for larges numbers, we can't have perfect polynomial solutions (I mean, without using random) ? Anyway, thanks for this answer.
•  » » » » 7 years ago, # ^ |   +3 I think we could get constant time solutions. Well, constant if we had just the occurences of 10 digits (if we don't limit ourselves to 4). Actually, digits with 7 possible remainders.As long as the number is diverse enough, there should be a small subset of digits such that there's a permutation of them with remainder x for all 0 ≤ x < 7; if there's such a subset, the length of the number is, in fact, irrelevant — no matter what permutation of the remaining digits we use at the start of the number, we can always pad it with the suitable permutation of our subset.The problem we got just specifies the subset for us: remainders "1,1,2,6". This is quite small, and I don't think any required subset (that doesn't contain any smaller required subset) will be much larger. Notice for example that the subset "many 6-s and 1" that I presented can be replaced by "many x-s and y", and it still holds for x, y giving different remainders mod 7 and even any prime modulus (not just 7) with 10 as the primitive root!That leaves us with the task of bruteforcing all suitable subsets, hardwiring them into the code and just choosing the right one for any number :D
•  » » » » » 7 years ago, # ^ |   0 Thanks, very nice idea :)
 » 7 years ago, # |   +1 Thanks for the round! The problems were very clever, even though I didn't solve them during the contest!
 » 7 years ago, # |   +3 Timus 1095 is exactly the same with today's A div 1. The only difference is digits used but I suppose that there're many different sets of 4 digits that work in this case — it doesn't mean though that problems will be different as well.
 » 7 years ago, # |   0 :(((
 » 7 years ago, # |   0 Anyone get TLE at DIV1-B, try scanf("%s") instead of cin. what a sad story, my O(N^2) solution with very small constant coefficient TLE.
•  » » 7 years ago, # ^ |   0 I had the same issue. I think the time constraints for B are too harsh.
•  » » » 7 years ago, # ^ |   0 Never mind, just remember to use scanf in future. I have been away from ACM for a couple of years and forget this rule :(
•  » » » » 7 years ago, # ^ |   0 I did scanf but I scan character by character.
•  » » » » » 7 years ago, # ^ |   +1 NEVER use cin without invoking sync_with_stdio first.
 » 7 years ago, # | ← Rev. 2 →   0 Can anyone explain test 4 of Pro.B div 1 (or Pro.D div 2) for me ? In the first row we have 10 ones so we can put ones adjacent so that we have a rectangle with size 1 x 10, or I misunderstood the problem ? http://codeforces.com/contest/375/submission/5515862
•  » » 7 years ago, # ^ |   0 You can swap ROWS not COLUMNS :)
 » 7 years ago, # |   0 What is the official solution for DIV1-D? When I read other's AC codes, to my surprise the moving-interval solution could pass-_-!!
•  » » 7 years ago, # ^ |   +1 Its time is N\sqrt(N),so it can pass it.In CN, we call it 'MO DUI'
 » 7 years ago, # |   0 questions were interesting and little bit tricy...Hats off to problem setters!!!
 » 7 years ago, # |   0 thanks to authors for this round, problems were interesting,short and simple to understand — I like this round
 » 7 years ago, # |   0 Who can describe solution for 376C - Divisible by Seven, 376D - Maximum Submatrix 2, 376E - Circling Round Treasures?
 » 7 years ago, # |   -21 Can you post the editorial please.
•  » » 7 years ago, # ^ |   +3
•  » » » 7 years ago, # ^ |   -8 Thanks
•  » » 7 years ago, # ^ |   -8 why so many down vote. is it wrong to ask for a help?
•  » » » 7 years ago, # ^ |   +29 Probably because the editorial was there on the "recent actions" list, and you didn't bother to check it before asking about it.