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
- Azat_Yusupov
- angel_of_monkey
- molamola.
- iseriohn
- Mato_No1
- silver__bullet
- TheDude
- Nero
- khuebeo
- uc-nuts
UPD3 The editorial has been finished. I'm waiting for your feedback / questions.
can't wait to find out who's the main character in the problem statements :D
You call positive feedbacks yelling at you about that u couldn't manage to avoid naive solutions' passing E.
Seems legit.
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!
Our teacher said that this test is made by XHXJ,really?
Is this an individual contest? How to know if a contest is team or individual?
All Codeforces Rounds are individual
I was dreaming for months a contest like this: no complicated algorithms, spend more time writing on paper than typing on PC.
Good luck every one:)
GooD Luck :D
YoooOOoOOoo leEeeeeTeR
GL && HF!!!
Tasks will be sorted by difficulty in increasing order, will they?
By difficulty in author's opinion
How to solve B div2?
For each 2 points I find maximum "left" and maximum "right" triangles(using that points) and sum them.
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.net/contest/340/submission/4381739
Excuse me, How's the time complexity of your algorithm? I use an O(n^3) algo., but I got TLE. :( http://codeforces.net/contest/340/submission/4378019
I use an O(n^4) algo and got AC, but before that I use a convex hull for a decrease count of points.
Problems are little bit hard for div2 contesters, but I have to say, very interesting problems.
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.
You can use Patience_sorting.
Here is my code which passed the system test
set st;
set::iterator it;
for(int i=0; i<n; i++) {
st.insert(a[i]);
it=st.find(a[i]);
it++;
if(it!=st.end()) st.erase(it);
}
cout<<st.size()<<endl;
So you are not satisfied by =(, ok TOT.
div 2 problems difficulty A D D D E !!
A E D D E!
yes , problem B more than 70% failed final test
why doesn't the system testing start ? :-/
I hacked more than 10 'A' solutions with this test case:
1 1 1 2000000000
Weak pretests , in previous contests TLE solutions did not get pretest pass
me too hacked 12 with same
Special Thanks for your great contest! I'm willing to take all the downvotes only to thank you personally! :)
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.
i think you probably make some mistake about the time.
the time complexity of quad tree is O(n) is indeed.
!!!what?...i treat it as O(logn*logn) until now.=.=~..thank you~
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)
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.
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).
I think it's O(N) for query(1,1,1,n)
Agree.Your code is not log(N) for each query and update.Unless I've misunstood your code.
Thanks every one. i know my wrong now!
O(log(n2)) = O(2log(n)) = O(log(n)), so there must be something wrong.
btw.
binary indexed tree
orfenwich tree
instead oftree array
:)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!
Problem B in Div2 was awesome.
Very nice problem set,and a very enjoyable contest overall.
great contest! great problem! thank you all!
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" :D
Edit: First time in congratulation list, yay ^_^
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!!!
DIV1-C can be solved in O(N), why constraints are so weak?
solution
So that O(N*N) solutions can pass too.
I suppose problem would be more interesting with larger constraints, so well-known derangement problem with n^2 solution shouldn't pass:-)
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.
Awesome contest ! I loved the problems , they were GREAT . Thank you for this very well made contest :) !!!
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.
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) :)
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.
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.
Could you explain the formula? Because I've been trying to find some combinatorial interpretation of it, without success.
http://en.wikipedia.org/wiki/Derangement if somebody's interested.
How it was necessary to solve the problem of B div 2?
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).
Thanks!
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++ :(
http://codeforces.net/contest/341/submission/4375062
No reversely sorted test case!
The set [1] is an independent set alongside [2] and [3].
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.
If somebody had been successfully hacked by such a test then it would have been added to final system tests.
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).
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.
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.
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.
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.
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. :(
%lld works now in all C++ compilers used on CF
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.
I submitted the following code for A: http://codeforces.net/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.net/contest/341/submission/4376745).
Check this submission: http://codeforces.net/contest/337/submission/4383657 x=5, output=55834574853 You are using %I64d to print int.
There is a #define int long long before main() ;). So that's not the problem.
http://codeforces.net/contest/341/submission/4383888
Now it's working, check #define int ...
Try to compile your solution with -O3 option
is -O3 being used on CF?
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.
Can somebody tell me why this code ( http://codeforces.net/contest/340/submission/4383684) is outputting 10 3 ,it is giving 22 3 on my laptop.
Try to compile your solution with -O3 option
no change in output , but what is wrong in the code ?
What is your version of gcc?
Ideone also giving correct output : http://ideone.com/py5h0L
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
I've replaced #define LL long long with this:
And now it gives 22 3
http://codeforces.net/contest/340/submission/4383966
yeah that worked! How can this create any difference :-o ?
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 usingg++ 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.
After reading the assembly codes, I found it ran like this:
Looks that was a great contest!! unfortunately I missed it...
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!!
tha same with you,sad!
same with you.
same with you..
What's the meaning when I got a "Hacked"? Ps:I am a beginner!!
Your submit has some defect, someone use a case make your code got a wrong answer.
Thank you! now I know it!
Very interesting round and thanks for challenging problems !
Yes! that was interesting ! thanks for problems :)