### ZhNV's blog

By ZhNV, history, 6 years ago, translation,

Hello, Codeforces!

I'd like to invite you to Codeforces Round #324 (Div. 2). It'll be held on Tuesday, October 6 at 19:30 MSK and as usual Div. 1 participants can join out of competition.

Great thanks to Zlobober (Maxim Akhmedov) for helping me preparing the contest, to Delinur (Maria Belova) for translating the statements into English, to MikeMirzayanov (Mike Mirzayanov) for the Codeforces and Polygon. This is my first round, and, I hope, it won't be the last one.

You will be given five problems and two hours to solve them. The scoring distribution will be announced later.

Characters from problems have their prototypes — my friends, familiars, native, and this round is dedicated to them.

UPD : 500-1000-1500-2000-2500

Good luck and high rating!

UPD2 Round has finished, thanks for participation!

Congratulations to the winners!

1). Siunaus

2). aasddf

3). M_H_M

4). lal

5). femsub

Editorial will be published later

UPD3 Editorial

• +364

 » 6 years ago, # | ← Rev. 4 →   -103 Hope it will be a great Round :-) Happy coding :-)
 » 6 years ago, # |   -70 Hope it's another interesting round. Good luck to all :)
 » 6 years ago, # |   -59 I think clear problems with no story are better because there are many coders at codeforces that their main language is not english or Russian
•  » » 6 years ago, # ^ |   -38 Totally agree. For me it is quite difficult to read and understand the storylines in English. Sometimes I even look up a dictionary for words that I don't know.
•  » » » 6 years ago, # ^ |   -84 It's a part of problem! You must have good English skills to understand storyline clearly. I think English tasks for Russian users will be more fair.
•  » » » » 6 years ago, # ^ |   +20 and Russian tasks for American and UK users? =). It is nonsense.
•  » » » » » 6 years ago, # ^ |   -40 English is the main language of interaction between countries. You can't code in Russian; you code in English. So it makes sense that tasks should be in English.
•  » » » » » » 6 years ago, # ^ | ← Rev. 3 →   -9 1C is progaramming language (guess on what) on Russian. Now you know more.
•  » » » » » » » 6 years ago, # ^ |   +4 1C, not C1.
•  » » 6 years ago, # ^ | ← Rev. 4 →   -58 :D
 » 6 years ago, # | ← Rev. 2 →   -64 Best wishes to ACM ICPC — 2015 regional/sub-regional participants for their upcoming regional/sub-regional contest and congrats to those who already manage to qualify for ACM-ICPC World Finals 2016 — Phuket :)
 » 6 years ago, # |   -53 "The scoring distribution will be announced later."So mainstream ;)
 » 6 years ago, # |   -83 hello
 » 6 years ago, # |   -65 So much grey。。
 » 6 years ago, # | ← Rev. 2 →   -70 hope to see a lot of math problems :D
 » 6 years ago, # | ← Rev. 2 →   -40 Lots of down votes here :D :v
 » 6 years ago, # |   +82
•  » » 6 years ago, # ^ |   0 This parrot seems angry :P
•  » » » 6 years ago, # ^ |   +21 I had green parrot, but when cf change color, I changed color of that parrot too
•  » » » » 6 years ago, # ^ |   +5 You are very brave to comment here today. Look at all the downvotes.
•  » » » » » 6 years ago, # ^ |   +2 "Downvote squad" hard at work :p
•  » » » » » » 6 years ago, # ^ |   0 Same
•  » » » » 6 years ago, # ^ |   -11 Yeah! The color matches with your CF color. Hopefully you'll get a blue parrot soon :)
•  » » 6 years ago, # ^ |   0 inbox me more such pics ( ͡° ͜ʖ ͡°)
 » 6 years ago, # |   -26 Gayle Laakmann live session or this contest :D
•  » » 6 years ago, # ^ |   +21 Isn't she over-rated?
•  » » 6 years ago, # ^ |   +6 check this quora link quora. With all due respect ma'am, try to accept that there are people in this world a lot more smarter than u and being a bit** will not change that. :)
•  » » » 6 years ago, # ^ |   0 Isn't she stupid for saying that? Gennady won't even care, let alone give her a comeback.
•  » » » » 6 years ago, # ^ |   0 yes i know.. in comments section she clearly states she knows him and compares herself and him as apples and oranges . LMAO XD
•  » » » » » 6 years ago, # ^ |   0 WHAAAAAAAAAAAAAAAAAAA????? brb,, dying on the floor laughing :D
•  » » 6 years ago, # ^ |   +27 Obligatory: Who?
 » 6 years ago, # |   +3 The scoring distribution will be announced later later later late lat la l..........
 » 6 years ago, # |   +3 where is scoring distribution ??
 » 6 years ago, # |   0 Auto comment: topic has been updated by ZhNV (previous revision, new revision, compare).
•  » » 6 years ago, # ^ | ← Rev. 2 →   -31 z
 » 6 years ago, # | ← Rev. 3 →   -13 at problem d i output 32 2 23 i have wrong answer on pretest 1 , which has n=27 why? LE : my bad, sorry
•  » » 6 years ago, # ^ |   0 What was the problem?
•  » » » 6 years ago, # ^ |   0 I forgot a return 1;The windows returns it automatically,but on linux is a big problem. Sorry guys for the misunderstanding
 » 6 years ago, # | ← Rev. 2 →   -30 z
•  » » 6 years ago, # ^ |   +1 why did you copy? this is bad
•  » » 6 years ago, # ^ | ← Rev. 2 →   +3 cp 'solution of kieuquocdat123' 'copy of solution of kieuquocdat123' mv 'copy of solution of kieuquocdat123' 'user gg.vdn1999' 
 » 6 years ago, # | ← Rev. 2 →   +1 B — What's wrong with the solution 3^(3n) - 7^n ?
•  » » 6 years ago, # ^ |   +4 Nothing.
•  » » » 6 years ago, # ^ |   0 So it is actually right? I kept getting WA. Maybe I've got some mistakes in modular arithmetic ?
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   0 Yep, with modulo formula is like this ((3^n) % MOD — (7^n) % MOD + MOD) % MOD. Because we can get negative number)P.S. sorry, didn't read posts below
•  » » 6 years ago, # ^ |   +15 if(ans < 0) ans += MOD;?
•  » » » 6 years ago, # ^ |   0  int n; cin>>n; i64 s = 1, g = 1; for (int i = 1; i<=n; i++) { s = (s*7)%mod; } for (int i = 1; i<=3*n; i++) { g = (g*3)%mod; } cout << (g-s)%mod; 
•  » » » » 6 years ago, # ^ |   +7 cout << (g-s+mod)%mod;
•  » » » » » 6 years ago, # ^ |   0 I feel so embarrassed :\And still. How could it possibly be negative?
•  » » » » » » 6 years ago, # ^ |   0 because 1000000007 mod 1000000007 is less than 100 mod 1000000007
•  » » » » » » » 6 years ago, # ^ |   0 Got it now. Thank you.
•  » » » » » » 6 years ago, # ^ |   0 -3/2=-1 -3%2=-1 I don't like this either. It causes so many troubles...
•  » » » » 6 years ago, # ^ |   +1 (g-s)%mod could be negative
•  » » » 6 years ago, # ^ |   +1 when u will get ans < 0 as 27^n — 7^n can never be zero
•  » » 6 years ago, # ^ |   0 Good question. Got WA with this formula, couldn't figure why :(
•  » » 6 years ago, # ^ |   0 I think that's the solution almost all in my room used. Check your modulo maybe?
•  » » 6 years ago, # ^ |   0 That is what i did and it passed pretests
•  » » 6 years ago, # ^ |   0 check overflows.
•  » » 6 years ago, # ^ |   0 I thought too much that this required for looping and finding nCr. -_-
•  » » 6 years ago, # ^ |   0 Logic behind formula? I failed very hard today ;_;
•  » » » 6 years ago, # ^ |   0 There are total 27 possible way to distribute coins to 3 gnomes out of which 7 will have have sum equal to 6. And in our required answer we need to exclude that case. Since there are n such combinations we will have 27 ^ n — 7 ^ n.
•  » » » » 6 years ago, # ^ |   0 Thanks
•  » » » » 6 years ago, # ^ |   0 I don't know why i was getting WA in 7th test case. :-(
•  » » » 6 years ago, # ^ | ← Rev. 3 →   0 For n=1 one triangle. For n=2 two triangle. and so on. We have three positions and three number. So total combination = 3*3*3 =27 Invalid combinations of three numbers when sum=6 is (2,2,2) =1, (1,2,3) this will be 3! = 6 . Invalid combination=7 Valid Combination=27-7=20 There will be no solution when all triangles have in invalid combination. Answer is Total ways to fill n Triangle — When all triangle uses Invalid combination Answer is 27^n — 7^n**
•  » » 6 years ago, # ^ |   0 It's very cool to understand some dependence or notice combinatoric, but I simly considered second test and suggested, that it could be true. In a result, I was lucky :)
 » 6 years ago, # |   0 Problem 2: Just 3^(3*n)-7^n ;))
•  » » 6 years ago, # ^ |   0 27^n — 7^n : Still got wrong answer ...dont know why ...maybe becauze of MOD operation
•  » » » 6 years ago, # ^ |   +12 maybe when (7^n)%mod > (27^n)%mod, then you should write: ((27^n)%mod-(7^n)%mod+mod)%mod
•  » » » » 6 years ago, # ^ |   0 ok thanks
•  » » » 6 years ago, # ^ |   0 you forgot to add MOD if the answer becomes -ve. You should write like this: (27^n — 7^n + MOD)%MOD
•  » » 6 years ago, # ^ |   0 code by JAVA (3^(3*n)-7^n) % mod
 » 6 years ago, # |   +20 dafuq is C pretest 9?
•  » » 6 years ago, # ^ |   +4 seriously it's killing me to know
•  » » 6 years ago, # ^ |   0 I couldnt pass Pretest 4 only :/
•  » » 6 years ago, # ^ | ← Rev. 2 →   +2 I'm guessing something like this:INPUT5 1baseteasej OUTPUTbasej
•  » » » 6 years ago, # ^ |   +1 Tested with my program (which failed at pretest 9), and I got the correct output for that input.
•  » » » 6 years ago, # ^ |   +1 Yup Mine Passed that too :/
•  » » 6 years ago, # ^ |   +1 may be some thing like it!4 2 abcd ebfg
 » 6 years ago, # |   +7 How to solve problem E ?
•  » » 6 years ago, # ^ | ← Rev. 2 →   -8 Greedily. Problem: sort the permutation with minimum cost. Let's assume that we already sorted first i elements(0-based). Let's p[j] = i. Then we need to find maximum ind such that i ≤ ind < j and j ≤ p[ind], it can be easily done by segment tree. Then swap elements at index ind and j. For each index i you will make O(n) swaps. Complexity O(n2logn)
•  » » » 6 years ago, # ^ |   0 Are you certain this works? I submitted this and got stuck on pretest 14, and looking at your profile you didn't pass the pretests either (getting stuck much earlier than me).
•  » » » » 6 years ago, # ^ |   0 I wanted to write the same but was sure that it doesn't work;)
•  » » » » 6 years ago, # ^ |   0 Yes, that works. I didn't passed because I had wrong idea. I looked for maximum ind such that i ≤ ind < j and p[ind] > ind. This idea doesn't work for test: 4 4 3 2 1 1 2 3 4
•  » » 6 years ago, # ^ |   0 The minimum cost is achieved using any strategy that never moves any element further from its final location, since |i - j| is just the distance by which each element is moved (·0.5).One way to solve this would be putting all elements that need to be moved to the right in one set, those which need to be moved to the left in another set and always swapping the first element of the latter set with the last smaller element of the former.
•  » » » 6 years ago, # ^ |   0 Can't believe E can be so simple, thanks for the explanation :D
 » 6 years ago, # |   +1 How to solve D?
•  » » 6 years ago, # ^ |   +5 If n is prime we print 1 nIf n — 2 is prime we print 2 2 n — 2If n — 4 is prime we print 3 2 2 n — 4Else n = p1 + p2 + p3. We find closest prime number to n (p1). And we've got n — k = p2 + p3.n — k ~ log(N) (Don't remember why, shame on me). And just by brute force find p2 and p3.
•  » » » 6 years ago, # ^ |   +1 What's the complexity of finding the closest prime number?
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   0 1700 * sqrt(n) maximum distance between 2 primes if they are both not greater than 10^9 is 1700
•  » » » » » 6 years ago, # ^ |   +4 Maximum prime gap less than 10^9 is 282.
•  » » » » 6 years ago, # ^ |   +1 As I said n — k ~ log(N). Checking whether number is prime O(sqrt(N)). So finding closest prime number is log(N)sqrt(N).If I'm wrong correct me please.
•  » » » » » 6 years ago, # ^ |   +1 It seems that its O(log^2(N)). https://en.wikipedia.org/wiki/Prime_gap#Conjectures_about_gaps_between_primes
•  » » 6 years ago, # ^ |   +30
•  » » » 6 years ago, # ^ |   +1 Seriously, without knowing this conjecture, can anybody solve problem D? This kind of problem just piss me off!!!
•  » » » » 6 years ago, # ^ |   +8 I solved D without this knowledge:D
•  » » » » » 6 years ago, # ^ |   +1 Then you (maybe without realizing) assumed that there is always valid p2 and p3 whose sum equals to n — p1. Problem guarantees there is a solution. It doesn't guarantee there is a valid (p2, p3) pair; that's why, you need to know Goldbach's conjecture.
•  » » » » » » 6 years ago, # ^ |   0 Yeah, you're right... This was just guess.
•  » » » » » » 6 years ago, # ^ | ← Rev. 7 →   +1 You don't need to know it since the problem is simple enough to brute force. First check if n is prime, if so print. Else find largest prime smaller than n, now check if you can find one or two primes adding up to this (goes very fast since prime density is quite high), if so print. Else iterate.You know from the problem description that there is a solution, and you know that finding multiple fitting large primes is too slow so the only way left is to just find large primes and then see if you can find one or two smaller primes adding up to the result.This way you can solve for odd n as well since it is so easy to find a solution.
•  » » » » 6 years ago, # ^ |   0
•  » » 6 years ago, # ^ | ← Rev. 2 →   +9 I used Levy's Conjecture and Fermat's Little Theorem to solve D.
•  » » 6 years ago, # ^ |   0 I can't solve it during the contest due to a small mistake. But i did it right after the ending of the contest :/If n = 3, output 1 3 if n = 5 output 2 2 3 elsesince n is odd, n — 3 is even, and then we can use strong goldbach conjecture to solve the problem. Every number N even, greater than 2, can be written as sum of two primes. Since n — 3 is even, we can find this two primes that added form n — 3 and then add it to 3, which is prime. output3 3 prime[i] (N — 3 — prime[i])I used Sieve of Eratosthenes to find primes between 2 and 10^7, and if some number K didn't fit in this interval, I test it's primality by brute force. And used binary search to try to find N — 3 — prime[i] in vector of primes;http://codeforces.com/contest/584/submission/13459478
 » 6 years ago, # |   +7 Problem A and Problem B is a joke in Python
•  » » 6 years ago, # ^ | ← Rev. 2 →   +1 yeh! partiality with c programmer ;)Bahut Na insafi hai
•  » » 6 years ago, # ^ |   +1 how so?
•  » » » 6 years ago, # ^ |   0 Literally 4 lines of code for either.(Seeing as in python you can do things like print(str(A)*N) for value of A repeated N times and in the second you dont need to add the mod operation till the end because python dgaf about ints long longs and such.)
•  » » 6 years ago, # ^ |   0 D also=)
 » 6 years ago, # |   +5 What is The Solution Of div2 E? I tried to find symmetric group, but it seems hard to calculate the minimum step to sort the permutation
 » 6 years ago, # |   0 How to slove D? Damn I spend all contest to it
•  » » 6 years ago, # ^ |   0
•  » » » 6 years ago, # ^ |   +3 Still not sure how to do it.It is basically coding Goldbach's weak conjecture, right?3, and express n-3 as sum of two primes. Do you just brute force it? What about the time complexity?
•  » » » » 6 years ago, # ^ |   0 No.4 cannot be expressed by your logic
•  » » » » » 6 years ago, # ^ |   0 The question says input is an odd number.
•  » » » » 6 years ago, # ^ |   0 Then we are assuming that '3' is definitely in the answer. Can you prove it?
•  » » » » » 6 years ago, # ^ | ← Rev. 2 →   0 That is Goldbach's weak conjecture and it has been verified for numbers larger than the input in the question.
•  » » » » » » 6 years ago, # ^ |   +3 In fact, Goldbach's weak conjecture has been mathematically proven to be valid in general.
•  » » » » 6 years ago, # ^ | ← Rev. 4 →   +6 So handle small numbers manually for simplicity. (Since n is odd, n-3 is even, and you can brute for 2 remaining 2 primes numbers(other than 3) summing upto n). Handle cases of n=3, etc manually.For larger n, always try and express it as sum of exactly 3 primes. Find a prime number g below n and close to it.This is one of your 3 primes. Since prime numbers are not too far apart, n-g is now a small even number(my bound was 50000) and you can brute for how to express it as 2 primes.
•  » » » » » 6 years ago, # ^ |   +10 Thanks. Your gap was 50,000? According to wiki, a gap of 300 would suffice.https://en.wikipedia.org/wiki/Prime_gap
•  » » » » » » 6 years ago, # ^ |   0 I did not know that. Just wanted to be safe :P
•  » » » » » 6 years ago, # ^ |   0 There's no need of different method for larger numbers. You can always brute force to express n-3 as sum of two primes. My solution passed with this method. I think the reason for this is that even when n is around 10^9, there is a very high probability of finding a small prime p(upto which you can iterate in time) such that n-3-p is also prime.
•  » » » » » » 6 years ago, # ^ |   0 Yes, I realized my solution during the contest failed only because my brain missed the "at most 3" condition. I ended up missing primes below 7 (3 and 5) — I thought they wouldn't be in the input since solution was guaranteed... Unfortunate error.
 » 6 years ago, # | ← Rev. 2 →   +8 BTW, check this problem: http://acm.timus.ru/problem.aspx?space=1&num=1356. It's almost the same as the problem D, just a bit harder (but the solution for 1356 works here in problem D).
•  » » 6 years ago, # ^ |   +5 This problem was on National Olympiad of Kazakhstan 2013-2014, as I remember.
 » 6 years ago, # |   +1 C pretest 9 ahhhr.C looks straightforward but did not work out.My thought. Count the number of distinct chars in s1 and s2 and tag appropriately. We can sort based on frequency. Pick first n1-t and n2-t Try to find t chars in Universal set but not in union of s1 and s2.
•  » » 6 years ago, # ^ |   0 My Algo was(not worked): 1) Find common chars in a & b -> x and set them in output array z[i] = a[i] 2) m = m — x 3) Place m chars of a in z(if z[i] not already set) z[i] = a[i] if z[i] == 0 4)similary set m chars of b in z(after step 3) z[i] = a[i] if z[i] == 0 5) For remaining unset chars in z[i] = char no in (a[i], b[i])
 » 6 years ago, # |   0 is Editorial out ?
 » 6 years ago, # |   -15 System rating finished
 » 6 years ago, # |   0 Hello! I have a question at the second problem, Div 2. During the contest I printed(put(3,3*n)-put(7,n))%m; and i have got wrong answer on test 7. Now I am printing (put(3,3*n)-put(7,n)+m)%m; and I have got accepted. Why the second method works? Thanks!
•  » » 6 years ago, # ^ |   +1 put(3,3*n)-put(7,n) may be negative number. So first method would be incorrect (returns m minus right answer).
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 but why should i add m? m is 10^9 + 7. i don't understant..
•  » » » » 6 years ago, # ^ |   0 put(3,3*n)-put(7,n) = Km + ansmay be less than zero. 0<=put(3, 3*n)
•  » » » » » 6 years ago, # ^ |   0 I didn't know ! Thanks a lot!
•  » » 6 years ago, # ^ |   -13 You are a specialist man!!!Well consider x < 0 and abs(x) < m. If we don't know how language will eval x%m, we simply do (x+m)%m, that way we are sure that we are moding a positive value.
•  » » » 6 years ago, # ^ |   0 Haters everywhere. F**k you too
 » 6 years ago, # |   0 For D, I just generated primes upto 10^6 and tried to find the answer with simple check. And it passes. Why does it pass?
•  » » 6 years ago, # ^ |   +4 Because primes are distributed pretty randomly with log(n) distance between them in average. So, there is no such number N that for all small prime numbers M up to 10^6, N — M is not prime.
•  » » » 6 years ago, # ^ |   0 Well, didn't know that. Thanks.
 » 6 years ago, # |   0 I don't understand.Why 2000 points for problem D??? :o :o :o It was far far easier than B and C.
 » 6 years ago, # |   +1 swap(C, D); 
•  » » 6 years ago, # ^ |   0 Task C is more difficult than D . . . It's injustice!
 » 6 years ago, # |   0 why this submission get WA?
•  » » 6 years ago, # ^ |   +3 1 should not be considered prime
•  » » 6 years ago, # ^ |   +3 1 isn't prime number!
 » 6 years ago, # |   0 how to solve C ?
•  » » 6 years ago, # ^ |   0 greedy . . .
•  » » » 6 years ago, # ^ |   0 Can you explain?
•  » » » 6 years ago, # ^ |   +25 Codeforces should have a problem tag called "case handling"
•  » » 6 years ago, # ^ |   0 http://codeforces.com/submissions/sameer85#its easy to read...its simple greedy approach
•  » » » 6 years ago, # ^ |   0 thanks :)
 » 6 years ago, # |   0 just added the condition of a+b+c=n and D passed :( :( :( :(
 » 6 years ago, # |   0 Auto comment: topic has been updated by ZhNV (previous revision, new revision, compare).
 » 6 years ago, # |   +4 i forget to say :thanks for no delay
 » 6 years ago, # | ← Rev. 2 →   0 Some help on E? I can find the minimum cost but I cannot restore the swaps. I thought about going from left to right and if we see an element which is not on its place (it must go to the right) then let's say his position is i and it must go to position j. Let's first handle all elements that are greater than Ai in the interval [i+1,j] and then somehow solve for the current element. Can you please give me a hint?
•  » » 6 years ago, # ^ |   +3 can E be solved using greedy method ?
•  » » » 6 years ago, # ^ |   0 Well, the first part (minimum cost) can be called greedy, I guess. The idea is to find for each number its position in B. Then if we want A to become B, that means that some elements will go to the left and some to the right. We can make the observation that we need to consider only those elements which go to the right. Let's assume that after considering them, there is an element that must go to the left (if there is more than one, consider the leftmost). Moving it to the left means moving one element to the right. A contradiction! So if pos[k] is the position of the element with value k in B, we add to the answer max(pos[Ai]-i,0) for each i.
•  » » » 6 years ago, # ^ |   0 My solution is actually greedy. What I do is in each step I have a vector that keeps all the numbers that have to go to the right (I iterate the numbers from left to right) and whenever I find a number that has to go to the left I just swap them and move the index of my iteration back so I can start from the number I moved.Before that I change the permutations so the second permutation is 1 2 3 ... N and the first one changes so it's the same problem but having to move a permutation to the sorted permutation.Let's see an example:4 4 3 1 2 1 2 4 3The problem is the same as solving4 3 4 1 2 1 2 3 4Now I start with 3, it has to go to the right so my vector is (3), then 4 has to go to the right so my vector is (3,4), then 1 has to go to the left so I swap 1 and 4 now it's 3 1 4 2And my iterator moves back to where the 1 is, now 1 still has to go to the right so I swap 1 with 3 that is the top of my vector (or stack if you want to see it like a stack). Now it's1 3 4 2Then I continue iterating, 1 has to stay where it is and the vector is empty, then 3 has to go to the right, 4 has to go to the right too, and 2 has to go to the left, and when I analyze 2 my vector is (3,4) so I move 2 to the left and it's1 3 2 4And in the last step I change 3 with 2 so it's 1 2 3 4 And it finishes the process. This is a greedy approach and it's similar to selection sort I think.I start with 4 (it
•  » » 6 years ago, # ^ |   0 You can maintain an ordered set (balanced binary search tree) of all elements that need to go to the left (call this set L), and all that need to go to the right of the permutation (call this set R).In each iteration you perform one swap, that involves swapping the leftmost element in L with its closest element in R to the left (it clearly has to exist). If you store both the elements and their positions, you can efficiently maintain this structure as you go along in logarithmic complexity.You may refer to my code: http://codeforces.com/contest/584/submission/13456405
•  » » » 6 years ago, # ^ |   0 You don't need such complicated structures as O(N^2) is ok for this problem.
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   0 The complexity of my solution is actually something along the lines of O(N^2 log N) in the worst case (something like 5 6 7 8 1 2 3 4) anyway. I try to follow the approach which is easiest for me to comprehend on a high level. If it requires complicated structures, so be it (especially if they're already part of the STL). :)
•  » » 6 years ago, # ^ |   +1 Consider the element that needs to go to the rightmost location. Lets say that element is in the ith position and needs to go to the nth position. Then, surely there must be an element from positions i+1 to n which needs to go to a position j where j <= i. If no such element exists, then there are (n-i) elements which final location is from (i+1) to (n-1), a contradiction! Find the leftmost element which matches this criteria using a pointer sweep and then swap it with position i then keep repeating until it is moved to its correct location. This is an O(n^2) algorithm.
 » 6 years ago, # |   -6 Problem E : For the first time on codeforces, a solution didn't pass for me with cin,cout. My solution failed system tests after passing the pretests. And when I changed it to printf,scanf it passed. I think the problem setters should be careful the next time, as when crtical points and rating gets affected due to such reasons, it feels sad.
•  » » 6 years ago, # ^ |   +28 Why are you blaming the problem setters for this? It was your fault!
•  » » » 6 years ago, # ^ |   -10 What should be tested is our knowledge, not whether we use fast i/o. And in fact such things have never happened on Codeforces before. Also when you get a problem wrong because of such reasons, it doesnt feel good. I'm not blaming them, but I feel if someone loses out on points for a hard problem, because they didnt use fast i/o, that is just not fair.
•  » » » » 6 years ago, # ^ |   +16 If problemsetter increase time limit in order cin/cout submition past, it can cause that slow solutions will past with scanf/printf! Cin/cout speed is well-known fact, be careful, when you use it
•  » » 6 years ago, # ^ |   +8 Do you useios_base::sync_with_stdio(false);?That line can save you from time limits if you use cin/cout
•  » » » 6 years ago, # ^ |   +8 Yes I did use it, still didn't pass :(
•  » » 6 years ago, # ^ |   +1 You can add these lines to speed up cin/cout. ios_base::sync_with_stdio(0); cin.tie(0); 
 » 6 years ago, # |   +8 It is time to midnight,but still waiting for Rating.
•  » » 6 years ago, # ^ |   +8 It is almost sunrise, still waiting for Rating :P
•  » » 6 years ago, # ^ |   +6 it's night and i have n't done my homeworks! but still waiting for ratings!
•  » » » 6 years ago, # ^ |   +6 Me too , it's weird how sometimes human being is not able to wait and do assignments both at once!
•  » » 6 years ago, # ^ |   0 we have the same time midnight. already tired
 » 6 years ago, # |   +3 MikeMirzayanov. When you declare a rating?
 » 6 years ago, # |   0 Happy New Year CF!!! wait(wow), rating still not updated?
 » 6 years ago, # |   +3 Wow, my rating is changed to +0 :)
 » 6 years ago, # |   +6 What is this?
•  » » 6 years ago, # ^ |   +3 Oops, it will be fixed tomorrow.
 » 6 years ago, # |   0 Auto comment: topic has been updated by ZhNV (previous revision, new revision, compare).