### fchirica's blog

By fchirica, 9 years ago,

Hello everyone!

We invite you to participate at Codeforces Round #198, scheduled Friday, 30 August at 7:30 PM MSK. The authors of the problems are me and Linh (ll931110). We are also the authors of the Codeforces Round #191 (Div. 2). Last time, we received positive feedback for the round. We hope this round will be at least as good as the previous one.

Linh brought to you D2-C/D1-A and D2-E/D1-C. I wrote the rest of the tasks. We hope you'll spend more time writing on the paper and thinking than typing on the PC. In addition, all tasks don't require too complicated algorithms. Instead, all require some creativity, hard working and patience. BTWs, the main character of the round will be Iahub, as in the previous one.

I'd like to thank to DamianS, Gerald and Aksenov239 for testing the round. Without them, my job would have been certainly harder. Also, thanks to Delinur for translating the tasks and to MikeMirzayanov for the amazing Codeforces platform and Polygon system.

We wish everyone high rating and to have fun!

UPD1 The score distribution will be dynamic in both divisions. For more information please look here. The problems are sorted in our expected order of difficulty.

UPD2 Thanks for everyone who participated. I hope you fount problems interesting. Also, I think my prevision that you'll think more than write was correct :)

Congratulations to the winners.

Division 1

Special congratulations to Igor_Kudryashov, the only person who solved D1-E!

Division 2

UPD3 The editorial has been finished. I'm waiting for your feedback / questions.

• +207

| Write comment?
 » 9 years ago, # |   +7 can't wait to find out who's the main character in the problem statements :D
 » 9 years ago, # |   -22 You call positive feedbacks yelling at you about that u couldn't manage to avoid naive solutions' passing E.Seems legit.
 » 9 years ago, # |   +8 Err... Spend more time on paper... Does that mean this round we should draw sth, like round 195? by the way,thanks for ur hard work!
 » 9 years ago, # |   0 Our teacher said that this test is made by XHXJ,really?
 » 9 years ago, # |   -18 Is this an individual contest? How to know if a contest is team or individual?
•  » » 9 years ago, # ^ |   +24 All Codeforces Rounds are individual
 » 9 years ago, # |   +6 I was dreaming for months a contest like this: no complicated algorithms, spend more time writing on paper than typing on PC.
 » 9 years ago, # |   +9 Good luck every one:)
 » 9 years ago, # |   0 GooD Luck :D
•  » » 9 years ago, # ^ |   -26 YoooOOoOOoo leEeeeeTeR
 » 9 years ago, # |   +4 GL && HF!!!
 » 9 years ago, # |   +19 Tasks will be sorted by difficulty in increasing order, will they?
•  » » 9 years ago, # ^ |   +25 By difficulty in author's opinion
 » 9 years ago, # | ← Rev. 2 →   -6 How to solve B div2?
•  » » 9 years ago, # ^ | ← Rev. 2 →   +9 For each 2 points I find maximum "left" and maximum "right" triangles(using that points) and sum them.
•  » » » 9 years ago, # ^ |   0 i calculate all possible triangle, then try one by one lets call this one 'left', and check for other possible triangle which is share one of the same edge, and check if that the other triangle is inside the first triangle or not, and call this triangle 'right', then out = max(out,left+right)but i got wa :( in pretest 2, anyone care enough to correct my code :) http://codeforces.com/contest/340/submission/4381739
•  » » » 9 years ago, # ^ |   0 Excuse me, How's the time complexity of your algorithm? I use an O(n^3) algo., but I got TLE. :( http://codeforces.com/contest/340/submission/4378019
•  » » » » 9 years ago, # ^ |   0 I use an O(n^4) algo and got AC, but before that I use a convex hull for a decrease count of points.
 » 9 years ago, # |   +3 Problems are little bit hard for div2 contesters, but I have to say, very interesting problems.
 » 9 years ago, # | ← Rev. 2 →   +3 Couldn't completely write NlogN of LAS for problem-D in time, because realized it in last 5 minutes. So sad =( And fchirica was correct, implementation was easy.
•  » » 9 years ago, # ^ | ← Rev. 2 →   +5 You can use Patience_sorting. Here is my code which passed the system testset st; set::iterator it; for(int i=0; i
•  » » » 9 years ago, # ^ |   0 So you are not satisfied by =(, ok TOT.
 » 9 years ago, # |   +14 div 2 problems difficulty A D D D E !!
•  » » 9 years ago, # ^ |   +8 A E D D E!
•  » » » 9 years ago, # ^ |   +4 yes , problem B more than 70% failed final test
 » 9 years ago, # |   0 why doesn't the system testing start ? :-/
 » 9 years ago, # |   +2 I hacked more than 10 'A' solutions with this test case:1 1 1 2000000000
•  » » 9 years ago, # ^ |   +1 Weak pretests , in previous contests TLE solutions did not get pretest pass
•  » » 9 years ago, # ^ |   0 me too hacked 12 with same
 » 9 years ago, # |   -27 The comment removed because of Codeforces rules violation
 » 9 years ago, # |   +15 Special Thanks for your great contest! I'm willing to take all the downvotes only to thank you personally! :)
 » 9 years ago, # |   +6 I think there is some problem on div 1 problem D'time limit! 2 dimension segmeng tree and the 2 dimension tree array have a same time complexity O(m*logn*logn),but you make first TLE and last one AC..it is different from usual cf's problem.
•  » » 9 years ago, # ^ |   +21 i think you probably make some mistake about the time.the time complexity of quad tree is O(n) is indeed.
•  » » » 9 years ago, # ^ |   0 !!!what?...i treat it as O(logn*logn) until now.=.=~..thank you~
•  » » » » 9 years ago, # ^ |   +9 Can "xianduanshu tao pinghengshu" get accepted?I do want to do so,but when I see the time limit I changed my mind.(sorry I don't know how to translate it into english)
•  » » » » » 9 years ago, # ^ |   0 I don't see the time limit at first....555...and after TLE by segment tree, i'm too native to believe that cf would not "卡常数"..so i didn't to write tree array at once.
•  » » » 9 years ago, # ^ |   0 Are you sure about it? every step at updata or query on my quad tree(just like kd tree) , the area became area / 2. So i think the number of total steps is log(n^2), time complexity is O(logn*logn). Why you say it's O(n).
•  » » » » 9 years ago, # ^ |   +8 I think it's O(N) for query(1,1,1,n)
•  » » » » » 9 years ago, # ^ |   +8 Agree.Your code is not log(N) for each query and update.Unless I've misunstood your code.
•  » » » » » 9 years ago, # ^ |   0 Thanks every one. i know my wrong now!
•  » » » » 9 years ago, # ^ | ← Rev. 2 →   0 O(log(n2)) = O(2log(n)) = O(log(n)), so there must be something wrong. btw. binary indexed tree or fenwich tree instead of tree array :)
 » 9 years ago, # | ← Rev. 2 →   +15 Nice problems, really liked them. Damn E, declared the array of 1000 instead of 2000, else I would've gotten AC. Very nice contest. Congratz to the organizers!
 » 9 years ago, # |   0 Problem B in Div2 was awesome.
 » 9 years ago, # |   +7 Very nice problem set,and a very enjoyable contest overall.
 » 9 years ago, # |   +1 great contest! great problem! thank you all!
 » 9 years ago, # | ← Rev. 2 →   +25 Very cool problemset. I really liked D: At first glance I thought it was another Range tree problem. I almost implemented that, but luckily I remembered the author's comment that "all tasks don't require too complicated algorithms" :DEdit: First time in congratulation list, yay ^_^
 » 9 years ago, # |   +110 I will always add X while subtracting two integers modulo X!!! I will always add X while subtracting two integers modulo X!!! I will always add X while subtracting two integers modulo X!!!
 » 9 years ago, # | ← Rev. 2 →   +5 DIV1-C can be solved in O(N), why constraints are so weak?solution
•  » » 9 years ago, # ^ |   0 So that O(N*N) solutions can pass too.
•  » » » 9 years ago, # ^ |   -27 I suppose problem would be more interesting with larger constraints, so well-known derangement problem with n^2 solution shouldn't pass:-)
•  » » » » 9 years ago, # ^ |   +11 The O(n) solution is well-known, so smaller constraints wouldn't make it more interesting. Just make the imbalance between people who've seen it and those who didn't worse.
 » 9 years ago, # |   +16 Awesome contest ! I loved the problems , they were GREAT . Thank you for this very well made contest :) !!!
 » 9 years ago, # | ← Rev. 3 →   +26 Thank you authors for the contest!I'm wondering what was the intended solution in Div 1 C, because one can use inclusion-exclusion principle to get to the answer, which is: ,where K is the number of places i where a[i] = i still can happen and F is the number of free places. Judging from post-contest reaction, most people used DP approach. Thanks to gen for knowing Latex.Also, does anyone has any tips on Div 1 D without using any king of 2D structures? I believe one could somehow split it in 2 independent parts: rows and columns, but couldn't think of how.
•  » » 9 years ago, # ^ | ← Rev. 2 →   0 For D div 1:First you need to observe that the problem can be solved by using only operations of 2 types: Query(1,1,x,y) and Update(1,1,x,y)By observing 4 relative positions of (u,v) to (x,y), you can solve it by using 2D Fenwick tree (which I hope is simple enough) :)
•  » » » 9 years ago, # ^ |   0 Yeah, maybe it was intended. But I just got a feeling from the pre-round author comments that there is some cool solution with no 2D structures at all. And that the long long as the values was designed to stop the majority of 2D structures from passing.
•  » » 9 years ago, # ^ |   +18 There is another simple solution. Let n be the number of free cells and k the number of those free cells in which we cannot put values equal to their position, but it can still happen. Let calculate such DP[n][k] = (n — 1) * DP[n — 1][k — 1] + (k — 1) * DP[n — 2][k — 2], if k > 1. DP[n][1] = (n — 1) * (n — 1)!, DP[n][0] = n!. One can see that we should calculate only values with constant difference between n and k, so there are only O(n) states.
•  » » » 9 years ago, # ^ |   +5 Could you explain the formula? Because I've been trying to find some combinatorial interpretation of it, without success.
•  » » » » 9 years ago, # ^ |   0 http://en.wikipedia.org/wiki/Derangement if somebody's interested.
 » 9 years ago, # |   0 How it was necessary to solve the problem of B div 2?
•  » » 9 years ago, # ^ | ← Rev. 4 →   0 You have to fix one diagonal with O(N^2) and then with O(N) find the best points ( the ones that make the biggest area ) to the left and right of the diagonal . Overall complexity is O(N^3).
•  » » » 9 years ago, # ^ |   0 Thanks!
 » 9 years ago, # |   0 Is there no time limit scaling for slow languages (e.g Python)? Was something like that maybe discussed before on Codeforces? I just timed-out on div1-B using python (finding LIS in nlog(n)), but passed in 0.124 after retyping the code in C++ :(
 » 9 years ago, # |   +9 http://codeforces.com/contest/341/submission/4375062No reversely sorted test case! 3 3 2 1  Output: 0 Answer: 1 
•  » » 9 years ago, # ^ |   0 The set [1] is an independent set alongside [2] and [3].
 » 9 years ago, # | ← Rev. 2 →   +88 Some whining about the problems follows.Problem B: it was 100500 times already, it's a shame to reuse this problem again.Problem C: it is obvious for the ones who remember how to calculate the number of permutations without fixed points (or for the ones who do not hesitate to use Google/Wikipedia during the contest). Again, this problem appeared on a different contests 1050 times. And for the ones who do not remember the solution it is way harder, since they have to reinvent this dynamic programming.Problem D: it is super-evil, since 2-d segment tree (with time complexity is terribly slow (especially in Java), and 2-d Fenwick tree (with the same time complexity) seems to be the intended solution (at least, everyone got AC with it). Did the authors intend to make a problem with key idea in non-asymptotic optimizations?Update: another complaint: seems that most of the Java solutions for problem A are easily hackable (with anti-java-sort test). Did not you bother to add such a test? It is very unfair, since one can be hacked with this test, and in the other room the same solution may pass. Anyway, as I understand, general guideline for tests is to kill as much killable solutions as possible, and it seems to be violated.
•  » » 9 years ago, # ^ |   0 If somebody had been successfully hacked by such a test then it would have been added to final system tests.
•  » » » 9 years ago, # ^ |   -12 As I know, there is no automatic adding of successful hacks to system tests on codeforces (unlike topcoder). And adding the tests selectively is even worse (e.g. see this).
•  » » » » 9 years ago, # ^ | ← Rev. 4 →   0 Exactly in that contest I was the victim of a successful hack added to the system tests. The successful hack made by Arti1990 was added as a test 52 to the final tests of problem C.
•  » » » » » 9 years ago, # ^ |   0 Ouch, this probably means that tests are still manually added during contest despite the discussion initiated by Petr. Too bad :(Anyway, IMO problem authors should not depend on this and at least try to prepair strong tests before the contest.
•  » » » » » » 9 years ago, # ^ |   0 Sorry, maybe my previous post wasn't clear enough. Exactly in that contest which you pointed in your previous post (Round 172) the successful hack was added to the system tests.
•  » » » » » » » 9 years ago, # ^ |   0 Ah, I see, thanks for the clarification. IMO is would be better just to automatically add all successful hacks to systest, but it can explode testing time as a drawback.
 » 9 years ago, # |   +3 It is strange that there is no warning like this in task D:"Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier."And I forget to use long long but passed pretest. :(
•  » » 9 years ago, # ^ |   +28 %lld works now in all C++ compilers used on CF
•  » » » 9 years ago, # ^ | ← Rev. 2 →   +14 Hmm..then why not to remove this annoying time-consuming message that appears after submitting llds? Time, especially at the beginning of contest, is really significant for wasting it on reading unnecessary warnings.
 » 9 years ago, # |   0 I submitted the following code for A: http://codeforces.com/contest/341/submission/4374002 and got WA on pretest 1, with checker saying it received 0 instead of 22. Could anyone explain me why did my code print 0? On my laptop it prints 22, both with "%lld" and "%I64d". The logical part of the code is OK, as I got AC after simply deleting some macros and unnecessary #include's (code http://codeforces.com/contest/341/submission/4376745).
•  » » 9 years ago, # ^ |   0 Check this submission: http://codeforces.com/contest/337/submission/4383657 x=5, output=55834574853 You are using %I64d to print int.
•  » » » 9 years ago, # ^ | ← Rev. 2 →   0 There is a #define int long long before main() ;). So that's not the problem.
•  » » » » 9 years ago, # ^ |   0 http://codeforces.com/contest/341/submission/4383888Now it's working, check #define int ...
•  » » 9 years ago, # ^ |   0 Try to compile your solution with -O3 option
•  » » » 9 years ago, # ^ |   0 is -O3 being used on CF?
•  » » » » 9 years ago, # ^ | ← Rev. 3 →   +3 Codeforces use -O2 (Link)We have the same problems. Probably, it is a bug in gcc, fixed in version 4.8. Codeforces use version 4.7.
 » 9 years ago, # |   0 Can somebody tell me why this code ( http://codeforces.com/contest/340/submission/4383684) is outputting 10 3 ,it is giving 22 3 on my laptop.
•  » » 9 years ago, # ^ |   0 Try to compile your solution with -O3 option
•  » » » 9 years ago, # ^ |   0 no change in output , but what is wrong in the code ?
•  » » » » 9 years ago, # ^ |   0 What is your version of gcc?
•  » » » 9 years ago, # ^ |   0 Ideone also giving correct output : http://ideone.com/py5h0L
•  » » » » 9 years ago, # ^ |   +1 Try reading and writing with streams (ifstream, ofstream, etc..). If you want where you got that 10 you can also try to print ar as the answer and see what codeforces tells you
•  » » 9 years ago, # ^ | ← Rev. 2 →   +1 I've replaced #define LL long long with this: typedef long long X; #define LL X And now it gives 22 3http://codeforces.com/contest/340/submission/4383966
•  » » » 9 years ago, # ^ |   0 yeah that worked! How can this create any difference :-o ?
•  » » » » 9 years ago, # ^ | ← Rev. 2 →   +8 I used g++ -O2 main.cpp -S -fverbose-asm to get the assembly codes and it turns out that the var ans is not in it while it is in if using g++ main.cpp -S -fverbose-asm.I found that this code when compiled with -O3 will output 10 (g++4.6.2). So it must be a bug in the compiler. #include long long ar[3]={2,3,5}; long long ss,ans,num; int i; int main(){ for(i=0;i<3;i++){ ans += ((ar[i]*i) - ss); ss += ar[i]; } num = ss + 2*ans; printf("%I64d\n",num); return 0; } After reading the assembly codes, I found it ran like this: ar={2,3,5} ss=ans=num=i=0 ss'=ss ss+=ar[0] ss+=ar[1] ss+=ar[2] ans-=ss' ss'*=2 ans-=ss' i=3 tmp=ans*2 tmp+=ss num=tmp print num 
 » 9 years ago, # |   +1 Looks that was a great contest!! unfortunately I missed it...
 » 9 years ago, # |   +2 I find that i cannot view any problem. when i click the problem title, the web give the alert telling me "can't find or parse problem descriptor". I know nothing about the exception, and anyone can give me the answer or one solution?? Thanks!!
•  » » 9 years ago, # ^ |   0 tha same with you,sad!
•  » » 9 years ago, # ^ |   0 same with you.
•  » » 9 years ago, # ^ |   0 same with you..
 » 9 years ago, # |   +3 What's the meaning when I got a "Hacked"? Ps:I am a beginner!!
•  » » 9 years ago, # ^ |   +3 Your submit has some defect, someone use a case make your code got a wrong answer.
•  » » » 9 years ago, # ^ |   0 Thank you! now I know it!
 » 9 years ago, # |   0 Very interesting round and thanks for challenging problems !
•  » » 9 years ago, # ^ |   0 Yes! that was interesting ! thanks for problems :)