Hi all! This round was prepared by me and KAN. I hope, you will enjoy our problems.
I want to thank PavelKunyavskiy, who tested our problems, readed statements and so on. Moreover, alger95, Skird, fdoer, sand-martin tested round too, I thank them for it.
And of course, I thank Gerald for organising our work, MikeMirzayanov for the great system and Delinur for translation of the statements.
I hope, result will be better than results of our previous round. Good luck!
Pay attention, round will be held at unusual time.
Scoring:
div1: 500-1500-1500-2000-2500
div2 : 500-1500-1500-2500-2500
My congrutulations for leaders.
div1:
div2:
Full english editorial: here
although the starting time of the contest is not as usual , I hope it will be a great contest and GL & HF to all participants :)
I hope the host could change the start time once again like a last year's contest.
I expect a very technical and hard round. I liked your last round! :-{)
After Round #175, it must be hard :)
Great, I like the time of the contest! What are the scores? 500 — 1000 — 1500 — 2000 — 2500? or something else?
I like this starting time of the contest ^_^
good for Chinese users.
yy
I'm not sure if i'm going to stay up all night or take some sleep before this round.
Starts 450 minutes earlier than the usual time . Hope , there'll be some surprise in the problem statements too as well as the starttime :)
@ Mike Mirzayanov
sir, why dont we have variable time for 'codeforces contests' like topcoder? is it because the usual time attracts lot of participants or it's just to distinguish Codeforces from topcoder?
I totally agree.I'm excited because this round is at 12.00MSK.We Chinese coders don't have to stay up at 23.30(Chinse Time) to participate.At first I thought this round is by a Chinese or Janpanese coder,but it seems I'm wrong.Thank you tunyash for this round at such great time!
I think,if Codeforces can have variable contest times like Topcoder,more coders will participate and Codeforces will become better.It is necessary to do so if Codeforces is to overtake Topcoder and become the first largest online programming competition site.
totally agree ^_^
I quite agree with this view.
agree too
:(((( at this day, tomorrow i have maths olympics :((( it begins at 10 o'clock and end at 2 o'clock :((((
I like this starting time of the contest! Hope the starting time will be variant,(not limited to 7:30pm in Russia) so that more US or Chinese coders will attend the contest.
Will points distribution be standard or dynamic?
last contest was great.I hope it will be great too
I hope for a more organized editorial this time ... Guys take 1 day but give us good editorials .
As you can see many people couldn't participate this contest ... It might be good for some countries but it's not for most ...
I mean variable contest times.I'm not suggesting we always have contest at 12.00MSK,there's no doubt we need 19.30MSK contest time.For example,I suggest 30% contest set at morning of MSK Time.
perhaps that's much better idea ...
As lsmll said, it should be good to everyone, so it's fair enough to variable the time so anyone will have a chance to participate. It's 5 A.M here in Brazil but i'm still gonna participate even though this time I really should be sleeping.
Test photo.
good for Chinese users.
By the way, past tense of "read" is "read", not "readed".
Nice comment ;)
My first contest in travel! Good luck!
Time limit for Div2 B is too long :( even brute force from k to 1 can pass :(
Got an Unsuccessful Hacking Attempt when trying to hacking one of those brute force solution :(
can you give me the link of this solution i think brute force will get TLE
Here is one .. Actually it's kinda weird O.o , I implemented this solution in the practice and got TLE , but when I tried mikhail's code got AC .. I think it depend on the optimizer somehow!
same to me got TLE :D with same solution
The reason for TLE in your case is, if I'm not mistaken, the use of long long in the line
for (ll i = k - 1; i >= 2; i--) {whereas the AC solution uses int for i. As a long long takes up more space in the memory in comparison with integer, it also takes longer to perform calculations with it (here: 'i--'). In this case it makes the difference between TLE and AC.Yes you are right about this .. But I think in general the intended solution is binary search , and the brute force should't pass.
You know, there is an O(1) algorithm (as opposed to the
algorithm of binary search), if you want to do some math. My submission, for example, is the implementation of the result: 3390910
Is sqrt really O(1)? I guess you could argue it's really fast, but actually it uses binary search (which is O(log k), not O(sqrt(k))).
Square root is O(log k)? I have always assumed that it's (along with the four arithmetic operations) constant. My bad. Thanks for clearing it up!
Also, yeah, I meant O(log k) for binary search. I must have been in a hurry to type O(sqrt k) instead.
I think the
sqrtfunction calculates the square root with fixed relative error, so it's O(1).Here is a c++ implementation:3396062.
http://mirror.codeforces.com/contest/287/submission/3388316
Even this Solution passes. Time:2000 ms :SS
Those who like permutations should be quite successful this time :)
wow! All System Testing was only 4 minutes!!! Thanks for this great testing!!
probably because there were fewer participants than usual....i myself didn't participate as it was at a different time and i forgot about it...
I agree with you, The time of the contest was good but I forgot it too!
Systest complete within just 2 refreshes :D
Fast system test... Great!!!!
To those who solved div1 A quickly e.g. within 20 minutes, how did you observe the trick(when n%4>1 return -1)? Thanks.
I think writing backtracking may be useful here.
Use next_permutation to do brute-force first.
With this method, did you manage to quickly find the pattern?
Of course, we can use this method to find all solutions (n <= 13) within a minute. And the pattern is very clear. Try it.
Well I didn't solve it within 20 minutes (and I'm div 2 anyway), but I suppose it's pretty simple:
Suppose f(i) = pi. We have f(f(i)) = n + 1 - i, so f(f(f(f(i)))) = i. So the permutation is effectively cycles of 4, 2, 1. However, there can be no cycle of 2 (otherwise f(f(i)) = i ≠ n + 1 - i if
, and if 
, then it's a cycle of 1), and the only cycle of 1 can only be done if 
, so there is at most one cycle of 1. Hence everything is in cycles of 4 except for possibly one element. This means 
or 
.
When in the contest, I visualized it by an n × n board where you put a piece on row i and column j if pi = j, and noticing that everything are the vertices of squares except for probably the middle element.
This is a brilliant idea. However, I still have two questions.
What's the meaning of the cycle? Seems like some kind of abstract algebraic construct like group?
I don't understand your last sentence above(i.e. and noticing...), can you clarify it?
First question:
Let's see a permutation 2, 3, 1, 4, 5. Note that p1 = 2, p2 = 3, p3 = 1. So from 1, we can get to 2, then to 3, then to 1 again, and it repeats forever. So (1, 2, 3) is a cycle, of period (or you can say "size") 3. p4 = 4, so (4) forms a cycle of period 1. Also note that we can multiply the period of any cycle by simply extending it: (1, 2, 3, 1, 2, 3) forms a "cycle" of period 2 × 3 = 6. I'll refer to a cycle with the smallest period (it cannot be broken into cycles) to be a "proper cycle".
If f(f(f(f(i)))) = i, then i must belong in a cycle of period 4, or in other words, a proper cycle whose period is a divisor of 4, hence why I can deduce that there can only be (proper) cycles of period 4,2,1. If the problem has been made such that f(6)(i) = i (6 iterations of f), I'd look for proper cycles of period 6,3,2,1.
Second question:
See the given permutation 2, 4, 1, 3 in the test case and what I made in my scratch paper:
As you can see, I put a piece (O) in row 1, column 2, indicating that p1 = 2. Another one in row 2, column 4: p2 = 4.
After making this, I noticed that everything is vertices of squares except for probably the middle piece (if there is any).
Elegant explanation, thanks.
I also have an observation, the correct lucky permutation is some sort of self-descriptive, taking n = 4 for instance, the answer is 2 4 1 3, the 2nd(value) element is the 1st(index) largest, the 4th element is the 2nd largest, the 1st element is the 3rd largest, the 3rd element is the 4th largest.
But I still don't know the meaning of "everything is vertices of squares", which squares?
Well, you can see that the four pieces in the above grid are vertices of a square, tilted a bit clockwise. Another example for n = 9:
Observe that A's make a square, and so are B's.
I finally understand. It's just a visual way describing the cycle of size 4 phenomenon. However, it's more precise to use the term "parallelogram" instead of square, isn't it:)
Actually you'll find that all the parallelograms will be squares (try to prove it :) ), but you can use "parallelogram" too if you prefer. Yes, it's my visual way of describing a cycle of period 4.
"I also have an observation, the correct lucky permutation is some sort of self-descriptive, taking n = 4 for instance, the answer is 2 4 1 3, the 2nd(value) element is the 1st(index) largest, the 4th element is the 2nd largest, the 1st element is the 3rd largest, the 3rd element is the 4th largest."
Of course. The pi-th element is ppi, which by condition is equal to n + 1 - i. It is obviously the i-th largest element.
Number of inversions in a square of a permutation is even, and number of inversions in permutation (N, N — 1, ... , 1) is N(N — 1)/2. It is clearly odd for N = 4k + 2 or 4k + 3.
That's correct. But could you explain the reason using no. of inversions to judge? I don't figure out the connection.
I don't quite figure what is the question about. If a permutation has an odd number of inversions, it can't be a square of any permutation. Therefore for N = 4k + 2, 3 answer doesn't exist.
Actually I don't understand what "square of a permutation" means.
A permutation applied twice consequently, like ppi in the problem statement.
Thanks, I got it.
The square of a permutation p is the permutation pp; that is, if originally the permutation p has pi = j, pj = k, then the square of p (which I denote q) has qi = ppi = pj = k.
For example, if p = (2, 4, 1, 3), its square q is:
q1 = pp1 = p2 = 4
q2 = pp2 = p4 = 3
q3 = pp3 = p1 = 2
q4 = pp4 = p3 = 1
I assume that you already know "inversion". The square of any permutation has the property that the number of inversions in it is even. Meanwhile, by the condition of the problem, the square of the sought permutation is equal to the reverse identity permutation (n, n - 1, ..., 2, 1), which has an odd number of inversions for
or 
, so they certainly can't be equal. So there doesn't exist any permutation whose square is the reverse identity permutation if 
or 
.
(EDIT: I keep making long comments and getting "ninja-ed" by people -_- But who cares.)
It's clear. All understood except "the square of the sought permutation is equal to the reverse identity permutation (n, n - 1, ..., 2, 1)", the reason?
Because the problem says that ppi = n + 1 - i.
If we expand this for all i, we get that (pp1, pp2, pp3, ..., ppn) = (n, n - 1, n - 2, ..., 1); in other words, the square of p is the reverse identity permutation.
About the parity of square of permutation, is there any proof? Given a permutation, how to decide whether it can be a square of some permutation?
That's the thing. I only recall that it is an established theorem, but I forgot the proof. Searching in Wikipedia also yields no result (although I think I saw the theorem in Wikipedia).
...Ah ya, here it is. I rephrase the (trivialized in Wikipedia) proof:
A permutation can be described by a number of adjacent-element transpositions. For example, (2, 4, 1, 3) can be described by (3, 4), (1, 2), (2, 3):
From (1, 2, 3, 4), we transpose elements on indices 3 and 4: (1, 2, 4, 3).
We then transpose elements on indices 1 and 2: (2, 1, 4, 3).
We finally transpose elements on indices 2 and 3: (2, 4, 1, 3).
To prove that we can always do so, it's simple: Just build the permutation we're going to make from the end (or from the front). The above sequence uses this algorithm: It constructs the permutation by first moving 3 to the end (as it's the last element), then 1 to the second-to-last index, and so on. (It's just lucky that after we move the 1, the permutation has been built already.)
Now, we note that the number of inversions changes by 1 for every adjacent-element transposition we made, so the parity of the number of inversions is equal to the parity of the number of adjacent-element transpositions we made. So, the parity of a permutation is equal to the parity of the number of adjacent-element transpositions. (This number may vary by simply adding something like (1, 2), (1, 2) as many times as you like, but the parity of the permutation always remain the same.)
Now, the composition of two permutations is just the product of their transpositions; in other words, the parity of the composition is equal to the sum of the parities of the two permutations used to build the composition.
Now, recall that the sum of two equal parities (even+even or odd+odd) is always even, and the square of a permutation is the composition of a permutation with itself. It's obvious that the parity of a permutation is equal to the parity of the permutation itself, so its square, which is the composition of the permutation and itself, must be even (as it's the sum of two equal parities).
I'm not sure how to determine whether a permutation is a square of another permutation or not though. I originally suspected that all even permutations are squares of some permutations, but (2, 1, 4, 3) doesn't satisfy it, so I don't know.
Oops, I got it now. Because P(P(i)) = n-i+1, so applying P(P(*)) on 1 through n, the result is the reversing sequence (n,n-1,...1). Thank you for the reply.
Each of the elements, for which i != n -i + 1, needs to be in the cycle of size exactly 4. So we need to partition all elements (or all but one) into such cycles.
Yes. My concern is how to prove that conclusion. chaotic_iak's approach seems nice.
I just didn't prove anything and submitted it on 10th minute :) My prove was like «can it be that there won't be any 2 (mod 4) or 3 (mod 4) tests in pretests? :)»
(Disclaimer: I use this only on contests)
Quite brave action:P
eg. 5
Case1:
1 -> ? -> 5 -> ? -> 12 -> ? -> 4 -> ? -> 2merge above
1 -> 2 -> 5 -> 4 -> 1Case2:
3 -> 3 -> 3It seems that m = n in all pretests of D. That may explain for some WA on test 7 I think.
I fell into this trap ._./
Nicely done problem setters, that was an absolutely amazing contest. It was worth staying up all night.
Congratulations to al13n! 2 victories in a row seems impossible if you're not Petr or tourist but he did it!
Thanks! I have no idea how it is possible O_O.
New IGM ? ..
Congratulations!
You are really amazing :)
Div 1 B can be solved by the naive algorithm...
I think it's not so naive, you need to think how to do the cycle, without moving too much numbers.
Yes, but I was waiting something much harder. Same for the third problem.
But this Solution passes :S
That's B div 2 :S
This contest was great! nice problems !
Div1 B can be solved by Brute-Force?
YES
Question could have been little more clear.. at last i figured.. !!
ACRush was in my room today and he became WARush today!!!
what does that mean ?
His 4 solutions failed system tests.
not really. two of his solutions are TLE :)
DIV 1 problem C TLE for using cin...
You should use cin with ios_base::sync_with_stdio(false);
why " ios_base::sync_with_stdio(false) " is makes cin fast ?
This link explains that if this flag is true, it maintains the stream state in both cstdio and iostream so you can mix scanf/cin calls (or printf/cout). Turning it off means cin won't advance stdin, so it does less work to read the input.
I failed the same problem as olimpo because of being slow with input, but it's nice to discover something new like this...thanks, shervinkh!
In default case, cin and cout don't use buffering. This behaviour enables programmer to use scanf, printf and cin, cout in a program simultaneously. Using ios_base::sync_with_stdio(false) tells cin, cout that you don't want to use scanf, printf with cin, cout. So cin, cout use smart buffering with lots of speed up (more efficient than scanf, printf). I think the latter case should be default. but its the decision of C++'s creators.(may be because of ability to use cin, cout in old c programs that use scanf, printf). for large inputs and outputs (1e5 or 1e6 or more words) that is usual in algorithmic contest program buffered input and unbuffered input differ a lot in the speed. so in every algorthmic contest program it is recommended to use that call in the beginning of the program.
EDIT: It seems that while i was writing this, Quelloquialism has written the answer.
Div2 C says "any integer i" meets the condition, not "every" or "all". I thing it's not even ambiguous, I did the wrong algorithm because of that :s
Nice Contest! For 286A - Lucky Permutation, I'm quite interesting on how to prove that there's no solution when n % 4 equals 2 or 3.
If you draw Permutation Graph You'll see that every cycle should be of length 1 or 4. so we couldn't have 4k + 2 or 4k + 3 nodes.
Nice! I got it! Thank you so much.
!!!!!!!!!!!!!!!!!!!!!!!! The problem D has n, m to read, but read m variables next and read n variables next. The pretest do not contain the situation when n is not equal to m... TAT TAT TAT
I'm sorry, I didn't noticed that. My fail.
The input format for 286D - Tourists's is a bit strange -
{#queries, #events, events, queries}instead of the more usual{#events, #queries, events, queries}.Typical: The one time I'm good enough at algorithms to write a correct Div1-D solution, I'm also not literate enough to read a Div1-D statement properly.
Upd1. Looks like Martin also had this problem, and I don't type as fast as him.
Upd2. There are 12 contestants affected: Contest Status (look for WA#7)
Could someone help me? my submission 3392032 got TL on test 41 in system testing but my next submission after the contest 3392661 got Accepted I just changed the size of my arrays from 1000005 to 2000005, but I think 1000005 was enough! wasn't it?
replace "cin" by "scanf" first, then submit again
Thanks, got Accepted! but why did this submission (3392661) get accepted? I just increased the size of array!
Maybe server was too busy first time? (see 41 test "Time: 1921 ms, memory: 23488 KB")
Your first submission is also accepted.
Enjoyed doing this contest.. Nice questions !! :)
drop 3 times in a row
lose IGM title so quickly
Looks like your ability has been transferred to wjmsbmr
Actually she is my girl friend :)
But she is better than me >_<
Is today's contest unrated?
Why! ... no reason for what you say
Up to now, the rating wasn't changed.
Usually it will be updated an hour (or even later) after contest...
It's already more than two hours (almost 2.5 hours) and the rating haven't been updated yet..
good problems! thanks :D
How did this person become a candidate master even with a rating of 1555 ?
Can anyone please explain this to me :-
For every unsuccesful submission , theres -50 so why does a user gets same score as me when he has 4 unsuccesful submission and i have none and the only question we both have solved is done at same time!
More specifically here , user 'abhinav92003' and i have got same score/rank. Hows this possible ?
You don't get -50 when you eventually don't succeed to solve the problem. Here, you both solved one problem in the same time so you have the same score. He tried to solve B unsuccessfully, you didn't try, I don't think you really deserve a better score than him...
@Nicolas16 , okay i get what you have said. And is there -50 for 'Failed System Tests' ?
What do you mean by Failed System Tests? Actually, when you solve a problem, your points for this problem is equal to the score corresponding to the time you took to solve it, minus 50 points by previous failed submission (unless it is on the first pretest). And there is a minimum so that someone who solve a 500 point problem with 10 wrong submissions don't get 0 but 150.
vote ups
No , i think you got it wrong . By 'Failed System Tests' , i think @IITian meant that one gets AC during the contest and after contest , at final testing , compiler judges it wrong! For that i think he was asking wether or wether not is -50?
I believe that it doesn't give any penalty, much like unsuccessful problems (submissions that don't pass pretests and the problem is eventually not solved) don't give penalty.
Points are deducted for unsuccessful submission only when you have solved the problem. He has not solved the problem.
Can someone explain me how to approach problem D of division 2?
it passed almost 2:30 hours after the contest and still the rates are like before!!! why ?
ratings were updated
I enjoyed this contest very much! Thanks :)
Hi everyone! I realized during the contest that problem B Div. 1 could work using a brute-force approach, however I was unable to maintain the cycles without moving too many elements at once. Could anyone who solved the problem correctly give me a hint on how I could achieve this?
If you look at some of the accepted solutions you will notice that you can think of each move which is performed as follows: Let's say that the elements which are the first in their blocks are on positions P(1), P(2), ..., P(Q) (obviously, P(1)=1). Then, instead of thinking about cyclic shifts, imagine that all the elements stay in place, except:
the element from position P(Q) goes to position N+1
the element from position P(Q-1) goes to position P(Q)
...
the element from position P(1) goes to position P(2)
This way, you only get to move the elements on the positions P(1), ..., P(Q), and your sequence can now be found on the positions 2, ..., N+1 (instead of 1,...,N, as in the beginning). At your next move you will simply have to consider the fact that your sequence does not start at position 1.
Very cool. Thanks!
I got hacked in Div 2 A . this is my solution , can anyone tell me the test case or my mistake
int main() { char a[6][6],c=0;
for(int i=1;i<=4;++i) {for(int j=1;j<=4;++j) cin>>a[i][j];} for(int i=1;i<=4;++i) for(int j=1;j<=4;++j) { int c=0; if(a[i][j]==a[i+1][j]) c++; if(a[i][j]==a[i][j+1]) c++; if(a[i][j]==a[i+1][j+1]) c++; if(c==3 || c==2) {cout<<"YES";return 0;} } cout<<"NO";}
In this case, first 2x2 square is a possible answer. You should also check if 'c' is 0.
my bad :( just didnt paid attention .
Here the answer is YES but your program prints NO:
just amended this line
if(c==3 || c==2) to this line if(c==3 || c==2 || (c==0&&(i!=4 &&j!=4))) and got accepted
Most of the times i see the code of a problem not solved by me , i notice that around 90% of the code of 90% coders is same . e.g in Div B 2nd problem .
I m a newbie coder , plz tell me something that i m missing .
please tell me anyone...>>>>>> at first i submit the problem,then accept. but it hacked. after i submit the problem then accept. when the code check,then all correct. but when given the rating ,show solve is 0; when i see my submission then see that skipped. what's the of the side.not only today,but also before a day can happen. i am very very dishearted.....>>>>>
Maybe rating is not that important, right? The things that you learned is what matters.
When will the editorial be published?
I think, it will appear tomorrow. We have editoral in russian, but we haven't translated it yet.
Can somebody tell me some more problems like Lucky Permutation to practice.
please see comments of user: SROPRO ! I think He's Activity isn't good for this site!
can't connect the editorial ...would you publish the editorial at codeforces blogs
Me too , please publish it at CF blogs.
In 287E - Main Sequence can {-1,-1} be correct bracket sequence?
No.
There is a problem in the explanation of the C problem in the editorial. You must insert {2,n+4} at the beginning and {1,n+3} at the end as the second step to form a (n+4)-lucky permutation from n-lucky permutation.