By PikMike, history, 22 months ago, translation, ,

Hello Codeforces!

On December 28, 17:05 MSK Educational Codeforces Round 35 will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for Div. 2. It will be held on extented ACM ICPC rules. After the end of the contest you will have one day to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 7 problems and 2 hours to solve them.

The problems were prepared by Ivan BledDest Androsov, Vladimir 0n25 Petrov, Alexey Perforator Ripinen and me.

Thanks Mike MikeMirzayanov Mirzayanov for great system Polygon!

Good luck to all participants!

We also have a message from our partners, Harbour.Space University:

Hello everyone!

Registration is open for our upcoming 1st Hello India x Russia Programming Bootcamp, with 20 teams signed up and counting, and we are looking forward to seeing you and your teammates in India this March!

Register here

UPD: There will be 7 problems!

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 bmerry 7 212
2 uwi 7 216
3 halyavin 7 287
4 HS432 7 314
5 voidmax 7 337

Congratulations to the best hackers:

Rank Competitor Hack Count
1 halyavin 328:-26
3 Aemon 91:-33
4 algmyr 57:-4
5 Yazdan_ra 29:-9

1761 successful hacks and 1237 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A Delsin 0:01
B Benq 0:03
C DTSBT 0:06
D PrashantM 0:08
E perchema 0:15
F pekempey 0:38
G chemthan 0:21

UPD2: Editorial is out

• +223

 » 22 months ago, # |   +41 We are having too many rated contest at the end of 2017. We hope that we'll have such opportunities in coming year! Thanks for organizers and competitors. Good Luck to all.
•  » » 22 months ago, # ^ |   +4 Good Luck to you!!!
 » 22 months ago, # | ← Rev. 2 →   +20 I really like rated Educational Rounds! Thank you guys! Good luck everyone!!
 » 22 months ago, # |   +9
•  » » 22 months ago, # ^ |   -23 Will Good Bye 2017 be rated????
•  » » » 22 months ago, # ^ |   0 Yes
 » 22 months ago, # |   +73 Did you think about Codeforces div 1.5 round — something liek CS academy? For me it looks as good experiment and chances to make some interesting contest for guys with rating around 2000 ( we can not be at the top of div 1 and can not participe in div 2).
•  » » 22 months ago, # ^ | ← Rev. 2 →   +33 The idea is really nice! I think here on CF problem sets and groups for which rating is calculated are bound too tight. We could have several groups(Div 1.2, Div 1.4, Div 1.6 etc) competing on same problemset. Currently getting to div.1 you most likely will be back in div.2 after one of next contests. Only Div1+Div2 is ok for 1900-2000 people :)
•  » » » 22 months ago, # ^ |   0 I think if we have too level in the contests . It is too pressure for writers , and it will be too complex. But I think , If people which rating are in 1900 ~ 2000 can choose to join Div1 or Div2 by itself , It will be great ?
•  » » » » 22 months ago, # ^ |   0 I thought that we can make some only div 2 rounds to be div 1.5. I didn't think about adding one more division on each contest.
•  » » » » » 22 months ago, # ^ |   0 If we make some div.2 be div1.5 , Those rating are too low to join it will what to be ?
 » 22 months ago, # |   +6 Again no one thank MikeMirzayanov .
•  » » 22 months ago, # ^ |   0 They have already thanked him.
•  » » 22 months ago, # ^ |   +11 At least he greeted codeforces.
 » 22 months ago, # |   +3 35 = 7 x 5 and No of Hours = 2So, Problems = (7 + 5) / 2 = 6I wonder why authors mention number of problems! :/
•  » » 22 months ago, # ^ |   +33
•  » » 22 months ago, # ^ |   +3 LoL...they are changed to 7.
 » 22 months ago, # | ← Rev. 2 →   +4 Why is nobody thanking MikeMirzayanovUPD: fixed
 » 22 months ago, # |   +2 Thanks MikeMirzayanov
 » 22 months ago, # |   0 someone please send link to register for this contest
•  » » 22 months ago, # ^ |   0 http://codeforces.com/contests/911You can find it in the "Pay attention" bar at the top-right corner
 » 22 months ago, # | ← Rev. 2 →   0 I think the best contest in those three rated contests will Good Bye 2017 but this educational contest is interesting too. I got excited when i remembered this contest.
 » 22 months ago, # |   +4 Does hacking fetches you points in Educational rounds as well?
•  » » 22 months ago, # ^ |   +3 From the past contests, no.
•  » » 22 months ago, # ^ |   +24 Nope.But you still can rank up by hacking people higher than you. :D
•  » » » 22 months ago, # ^ |   0 So, is it that the majority of the system tests are from hacks only in Educational rounds?
•  » » » » 22 months ago, # ^ |   +11 Yeah, for easier problems it's usually the case
 » 22 months ago, # |   0 Guys i will be giving Educational rated round for the first time so i just wanted to ask whether difficulty level of educational rated round is less than Div2, equal to Div2 or greater than it.
•  » » 22 months ago, # ^ |   0 Difficulty is the same as Div2 problems
 » 22 months ago, # | ← Rev. 3 →   0 Another rated Educational Round? I love them. Good luck, guys.
•  » » 22 months ago, # ^ | ← Rev. 2 →   0 ...
•  » » » 22 months ago, # ^ |   +19 So smart....
 » 22 months ago, # |   0 Is there a negative score for a failed hacking attempt in Educational Rounds?.
•  » » 22 months ago, # ^ |   0 Hacking doesn't affect your score in any way.
•  » » » 22 months ago, # ^ |   0 Does it affect our rank?
•  » » » » 22 months ago, # ^ | ← Rev. 2 →   +9 If only you or somebody above you is getting hacked. Like, rank is still determined by number of solved problems and your penalty.
 » 22 months ago, # |   +38 Just curious, but with a tight schedule like this, how could system-rejudging process of this round work?I mean, without any changes, the rejudge (after the hacking phase) will start in 23:05 (UTC+7), right in the middle of the Good Bye 2017.Two issues may occur due to this:1 — Rating changes for Div.2 members will be available very late, perhaps even after system tests of GB2017 (wow this is unexpected xD )2 — As the judging machines have to work with a huge load of submissions from the previous contest, entirely; long waiting queues may be expected...(I'm quite new here, and I haven't seen any tight schedule like this before. If it had happened, then I guess I've worried too much ;) )
•  » » 22 months ago, # ^ | ← Rev. 2 →   +42 Testing of Educational round (after the end of Goodbye) Testing of Goodbye round Rating for Educational (probably somewhere during the testing) Rating for Goodbye
 » 22 months ago, # |   0 It will be better, if it had scoring distribution.P.S. Sorry for my English.
•  » » 22 months ago, # ^ |   0 It is ACM style contest, so problem A worth same as F.
•  » » » 22 months ago, # ^ |   0 If style has changed, It will be better.
•  » » » » 22 months ago, # ^ |   0 I understand you, but every Codeforces round #X has style like you said and we have enough of them.
•  » » » 22 months ago, # ^ |   +32 When I solve F ... -without knowing that it's ACM style-
 » 22 months ago, # |   -31 I like the rated Educational rounds (for Div.2), but this means that for Div.2 coders, there is rarely an unrated round (of suitable difficulty) for us to have a relaxing contest without a lot of stress. Perhaps this could be changed so that only some of the Educationals are rated?
•  » » 22 months ago, # ^ |   +24 Isn't that what virtual is for?
 » 22 months ago, # |   -18 you better make me blue again or i will send my gang to your abandoned shack of HQs you scums
 » 22 months ago, # |   -6 Is it going to be the editorial for this contest?
 » 22 months ago, # | ← Rev. 5 →   -8 Before every educational round I feel like :
 » 22 months ago, # |   +5 Contest ID — 911. Coincidence? I think not.
 » 22 months ago, # |   +32 I've made temporal fix of the CF-Predictor for educational round (calculates rating changes only for div2 participants), so I suppose actual rating change should be close to predicted:)
•  » » 22 months ago, # ^ |   0 where can i use the predictor
•  » » » 22 months ago, # ^ |   +3 You could read more about this tool in the my blog or just install extension for your browser:
•  » » » » 22 months ago, # ^ |   0 Thank you
 » 22 months ago, # |   +3 Sorry but Mishka sounds like a Girl's Name ..
•  » » 22 months ago, # ^ |   0 :(
•  » » » 22 months ago, # ^ |   +1 Atleast Here in India
•  » » » » 22 months ago, # ^ | ← Rev. 2 →   +6 Yeah, I know. I even saw this name as female one in some round here, I believe. In Russia it's some form of name Mikhail (Mike).
 » 22 months ago, # |   -13 I officially announce that this contest was shit.
•  » » 22 months ago, # ^ |   +3 Why is that? :( I think it is educational
»
22 months ago, # |
Rev. 2   0

# problem_C

What do you mean by "LIT Garlands "

•  » » 22 months ago, # ^ |   0 Lights ON
•  » » 22 months ago, # ^ |   0 Brightness
•  » » 22 months ago, # ^ |   0 We have "question to jury" option btw. Right below the problem list in the main page of the contest.
•  » » 22 months ago, # ^ |   0
 » 22 months ago, # |   +22
 » 22 months ago, # |   0 I didn't participated in the round. If I hack someone's solution successfully or unsuccessfully, would it affect my rating?
•  » » 22 months ago, # ^ |   0 Hacks don't affect anyone's rating, whether they've participated or not.
 » 22 months ago, # |   +3 how to solve D
•  » » 22 months ago, # ^ |   +1 Inversion number parity always changes whenever you swap two arbitrary elements in a permutation.
•  » » » 22 months ago, # ^ |   0 thanks.
•  » » » 22 months ago, # ^ |   -6 Proof?
•  » » » » 22 months ago, # ^ |   0 let x be the total number of inversions before reversing the segment and y be the number of inversions between the range l &r. Then the total no of inversions after reversing the segment wiil be ( x-y+(d*(d-1))/2-y) =(x+(d*(d-1))/2-2*y) where d is the length of segment. Hence parity of inversions does not depend on number of inversions in between the range
 » 22 months ago, # | ← Rev. 2 →   +3 Contest is now. How to solve D?Edit: Meant "now over"
•  » » 22 months ago, # ^ |   +10 swapping any two numbers changes the parity of number of inversions.. so just calc the initial number of inversions and how many pairs are being swapped in every query
•  » » 22 months ago, # ^ |   +1 The parity of the number of inversions of a composition of two permutations is the sum of the parities of the permutations, mod 2. A permutation that reverses a segment of length d has inversions, hence it suffices to add this after each query and consider the amount mod 2.
•  » » » 22 months ago, # ^ |   +16 I believe the correct formula is d(d-1)/2
•  » » » 22 months ago, # ^ |   0 proof?
 » 22 months ago, # |   0 anyone else getting run time error in test 30 of E ?
 » 22 months ago, # |   0 "The round is over"refreshes"System Testing: 99% Done*So fast!
 » 22 months ago, # |   +3 What is pretest 9 of E?
•  » » 22 months ago, # ^ |   0 try sth like 3 21 2
•  » » » 22 months ago, # ^ | ← Rev. 2 →   0 My output is 1 2 3. Which looks correct to me atleast. But i failed 9th pretestEdit this is my code if you want to have a look. (http://codeforces.com/contest/911/submission/33736055)
•  » » » » 22 months ago, # ^ |   0 You can try 6 2 5 2the ans should be 5 2 1 4 3 6
•  » » » 22 months ago, # ^ |   0 1 2 3
•  » » 22 months ago, # ^ |   +3 It's random case with n = 200000, k = 2 and some permutation in answer
•  » » » 22 months ago, # ^ |   0 Found the bug. Thanks.
•  » » » » 22 months ago, # ^ |   0 Could you give me a case then?
•  » » » » » 22 months ago, # ^ |   +4 Mine failed on2 99 2
•  » » » » » » 22 months ago, # ^ |   0 Thanks mine fails on this too :(
•  » » » » » » 22 months ago, # ^ |   0 I think you mean this one?9 29 2 Anyway, thanks, mine failed on this too.
•  » » 22 months ago, # ^ |   0 200000 2102991 8046
 » 22 months ago, # | ← Rev. 2 →   0 What is the test 6 of problem C..?? :|
•  » » 22 months ago, # ^ |   0 2 4 4
•  » » 22 months ago, # ^ |   0 2 4 4 it seems
•  » » 22 months ago, # ^ |   0 2 4 4 gives output as Yes.
 » 22 months ago, # | ← Rev. 2 →   +6 Anyone has any idea regarding the test case 9 of problem E?
•  » » 22 months ago, # ^ |   +2 Try this:9 39 5 3
•  » » » 22 months ago, # ^ |   +3 Thank you bro, got my mistake :)
 » 22 months ago, # |   -26
 » 22 months ago, # |   +3 I literally did it .. today and couldn't find the mistake for 1hrs.45min. for the problem C.LOL if(a==b==c and b==3) cout << "YES" << endl; 
•  » » 22 months ago, # ^ |   +4 warning: suggest parentheses around comparison in operand of '==' [-Wparentheses] if (N==a==b)that's what -Wall, -Wextra etc is for
•  » » » 22 months ago, # ^ |   0 Yes.. learnt a lesson . Also I should've moved forward.
 » 22 months ago, # |   0 how to do problem D??
•  » » 22 months ago, # ^ |   0 You can count the initial number of inversions (we will call it x thenceforth) through brute force.For each query, it is certain that inside the segment, the inverse pair will become non-inverse and vice-versa. Therefore, the oddity of x after each query is decided by the oddity of nC2 (the number of distinct pair in the query's segment).If nC2 is odd, then if x was even back then, it will be odd, and vice-versa. Simply because the numbers of non-inverse and inverse pairs are not both odd or both even, therefore, the state of x will be changed.Similarly, if nC2 is even, x keeps the same state it was before the query.
•  » » » 22 months ago, # ^ |   0 "If nC2 is odd, then if x was even back" doesn't the x means the number of inverses back in this segment? And if so then how to calculate inversion for a particular segment online?
•  » » » » 22 months ago, # ^ | ← Rev. 2 →   +3 x is the number of inverses in the entire array.The idea here is to find out if x is odd or even. We don't have to (and in fact, to my experience, cannot within time) calculate the exact value of x.P/s: Maybe the ambiguity was caused by the "n" variable. By that I meant r-l+1 in each query actually.
•  » » » » » 22 months ago, # ^ | ← Rev. 2 →   0 inverting a segment [l, r] will inverse all the pairs within it or will change entire array? I am thinking it change only that segment and if so then the extra number we have to add or remove from our count of inversion will depends on the previous value of inversion in [l,r].I know i am missing something please correct me!
•  » » » » » » 22 months ago, # ^ |   +12 The pairs within it. It means only (r-l+1)C2 pairs are toggled.You don't need to update the permutation though. (well but you do need to update your count on the entire array, modulo 2).Let's assume that C = (r-l+1)C2 — the number of pairs in the current segment.Each pair among those C pairs are toggled — non-inverse will become inverse and vice versa.If we have z as the number of non-inverse pairs before applying the query, therefore we will have (C-z) inversions.After the query, as all pairs are toggled, we will have (C-z) non-inverse pairs and z inversions.Therefore, the difference of inversion count will be: abs(z - (C-z)) or abs(2*z-C).It's easy to see from there that, only the state of C (odd or even) affect the answer in each query.If C is even, then the difference will be even. Therefore, the state of the inversion count is unchanged; i.e. if it was odd, then it is still odd — same goes if it was even.If C is odd, then the difference will be odd. As a result, the state of the count is changed — from odd to even or from even to odd.
•  » » » » » » » 22 months ago, # ^ |   0 Now it is crystal clear! Thanks a lot mate :)Happy new year!
•  » » » » » » » » 22 months ago, # ^ |   0 Thanks :) Happy new year to you too ;)
•  » » » » » » » 22 months ago, # ^ |   0 Thanks a lot for the explanation
 » 22 months ago, # |   +6 How're you going to start a rated round before calculating rating for previous one?
•  » » 22 months ago, # ^ |   0 You can check out this comment.Also, since Good Bye 2017 seems to have no rating restrictions (Div.1 and Div.2 users can join equally), then I guess there is no need to calculate rating before this round.
•  » » » 22 months ago, # ^ |   0 That's an option. I thought, may be they'll cut hacking time and wanted to get the official answer.Thanks
 » 22 months ago, # | ← Rev. 2 →   0 How to find number of current permutation?
•  » » 22 months ago, # ^ | ← Rev. 3 →   +24 I think you mean inversions, in problem D you could have just done two loops to check for one, and for an better algorithm read this.And if by any chance you wanted the number of permutations, there are n! of them and you can read more about them here.Or you are trolling (no offence).edit : no trolling.
 » 22 months ago, # |   +7 The solution of E is guessable from sample cases..
 » 22 months ago, # |   +38 r/UnexpectedFactorial
 » 22 months ago, # |   0 Whats the solution for 2B? I tried DP by updating DP[i]= floor(DP[x]/2), DP[x] = DP[x] — DP[i]Where x is the index of the maximum element at each iteration but getting WA on T#3
•  » » 22 months ago, # ^ |   0 no need to use dp its just a simple math int n, a, b; cin >> n >> a >> b; int sm = min(a, b); int mxs = max(a, b); int ct = 1,mx = 0; while (ct < n) { int cx = n - ct; int smc = sm/ct; int mxc = mxs/cx; mx = max(mx,min(smc,mxc)); ct++; } cout << mx; 
•  » » » 22 months ago, # ^ | ← Rev. 2 →   0 Can you please explain the logic of these two lines: int smc = sm/ct; int mxc = mxs/cx; 
•  » » » » 22 months ago, # ^ | ← Rev. 2 →   0 i will explain using the second example 4 7 10 ct is number of plates for the smallest cake loop from 1 to n — 1 as ct for first round ct = 1 then i will put all the smallest cake in 1 plate and the remain plates for the big cake its like 7/1 = 7 and 10 / (4 — 1) = (int)3.333 = 3 so 3 is the lowest value do it for ct = 2 7/2 = (int)3.5 = 3 and 10/(4-2) = 5 so 3 is the lowest value ct = 3 7/3 = (int)2.3 = 2 and 10 / (4-3) = 10 so 2 is the lowest value ct = 4 = n 7 / 4 = (int)1.75 = 1 and 10/(4-4) = infinity 
•  » » » » » 22 months ago, # ^ |   0 I tried to distribute the cakes according to the ratios a/(a+b) and b/(a+b). So the person with more cakes gets more plates to fill and so on. It got hacked. Could anyone please suggest what is wrong in this logic of assigning plates to cakes?Here's my code https://ideone.com/cNB2Ly
•  » » » » » » 22 months ago, # ^ |   0 i generated 1 million testcase and compare with my solution you got tooo many WA for example for this testcases 4 11 18 your output is 5 my output 6 4 13 21 your output is 6 my output 7 4 15 24 your output is 7 my output 8
•  » » » » » » » 22 months ago, # ^ |   0 Thanks a lot for the cases! The issue was not in the logic, but in the implementation. Instead of using the round() function, checking the max of the answers for ceil and floor suffices IMO. Here's my final code: https://ideone.com/jeAaa2
•  » » 22 months ago, # ^ |   +3 Some of the n plates are going to be of type 1 and the others of type 2. If you know how much plates of each type you will have it's easy to get the optimal answer, Then just try every possible distribution of the number of plates, there are only O(n) of them.
 » 22 months ago, # |   +1 how to solve E?? Thanks in advance
 » 22 months ago, # |   +10 How to solve F?
 » 22 months ago, # |   +3 I have a question. Will the rating be updated before GoodBye 2017?I remember the distance between the ending time of this round and the beginning time of GoodBye 2017 is 23.5 hours. When GoodBye 2017 begins, this education round's hacking process haven't ended. Shall we decrease the hacking time of this round or postpone the beginning time of GoodBye 2017 to let us know the rating change before GoodBye 2017?
•  » » 22 months ago, # ^ |   +8 PikMike's words1.Testing of Educational round (after the end of Goodbye)2.Testing of Goodbye round3.Rating for Educational (probably somewhere during the testing)4.Rating for Goodbyethat's the order
 » 22 months ago, # |   +23 The problems were very good, especially problem F but I couldn't solve it.
•  » » 22 months ago, # ^ |   +5 if you understand the solution now then please explain it. It will be a great help :)
 » 22 months ago, # |   0 Will (un)successful hacking attempt cause increase/decrease in penalty?
•  » » 22 months ago, # ^ |   0 no
 » 22 months ago, # | ← Rev. 2 →   -7 I 'm sorry for this troubles make. Sorry! See you in Goodbye 2017
 » 22 months ago, # |   0 Will hacking change the rank list ?
 » 22 months ago, # | ← Rev. 4 →   0 Does hacking help in increasing the rank other than the people which is not hacking? Your text to link here...
•  » » 22 months ago, # ^ |   0 NO
•  » » » 22 months ago, # ^ |   0 So why do people waste time on hacking? the fault will eventually occur in system testing
•  » » » » 22 months ago, # ^ |   +32 You can add your test to system testset; You can appear at main page of codeforces by getting to top-5 hackers of the contest; You can have your friends to see that sweet "+k" near your handle in standings; You can just enjoy it!
•  » » » » » 22 months ago, # ^ | ← Rev. 2 →   0 You can learn the art of debugging.
 » 22 months ago, # |   0 In problem D if the question is modified as :- there will be Q queries and type 1 and 2 type 1 l r — reverse the segment from l to r type 2 l r — give the number of inversions from l to rThen how would we solve it ? . using a segment tree or something i guess
•  » » 22 months ago, # ^ |   +1 I am not sure if it can be solved in something under .Here is such a problem but with swaps instead of segment reversals.
•  » » » 22 months ago, # ^ |   0 do that fit time limit?
•  » » » 22 months ago, # ^ |   +5 If n=1500, then we can find all the pairs (i,j) and for each pair we can map it to 1 if inverted else 0, sort it according to j values and build a segment tree of sums out of that. Then, for every l and r we can find effective r' (means how many pairs are there till r) and update (1,r') and effective l' and update (1,l'). In update operation we just invert it (0 if 1, 1 if 0). And the answer will be sum of all nodes in segment tree. Complexity- O(q*log(n*n)) Will this work?
 » 22 months ago, # |   0 Any hint on how to solve E ??
•  » » 22 months ago, # ^ |   +11 When performing the stack sort, you can never push a number onto the stack that is bigger than a number already on the stack, otherwise they will come off the stack out of order. So a successful stack-sort, if it exists will always be: pop the stack until the top is bigger than the front of A (or empty), then pop from A onto the stack. You can simulate that for the first k values to check if it is valid (as in, numbers popped were 1, 2, 3, ... up to some value). Note that the stack will always be sorted (smallest at the top).To complete the sequence, suppose that the top of the stack is currently X. A must then contain all missing number less than X before any value greater than X. To get a lexicographically maximal solution, they should appear in A in decreasing order. It's also easy to verify that this will give a valid solution.
•  » » » 22 months ago, # ^ | ← Rev. 2 →   0 Thanx a ton !! can u mention the specific algo/DS to solve problem G ?
 » 22 months ago, # |   +38 Is there any way to stop the scoreboard auto-refreshing. It's really annoying when I'm looking at a solution to find a hack, and the scoreboard reloads and I lose what I was looking at.
•  » » 22 months ago, # ^ |   0 It's strange it doesn't auto-refresh for me when I open someone's code.
 » 22 months ago, # |   +5 How to solve G?
•  » » 22 months ago, # ^ |   0 segment tree. but i've tried to solve it by UFS && block_division
•  » » 22 months ago, # ^ |   0 Try to solve it with several segment trees :D
•  » » 22 months ago, # ^ | ← Rev. 3 →   0 I've seen two solutions: O((Q + H)\sqrt{N} + N), where H = 100. Divide the array into blocks of size . For each block and value, store a linked list of all the places that value occurs in that block (in no particular order). To process a query, process the two partial blocks at the ends iteratively, but for the full blocks, just do an O(1) splice of one linked list onto another. O(QH\log Q + N). Store a segment tree over the updates, where each element in the segment tree is a transition table. At the leaves, an transition table is either the identity (for an "inactive" update) or an identity but with f(x)=y (for an "active" query). The root of the segment tree gives the composition of all the active updates. Now do a sweep through the array, activating updates when reaching l and deactivating them when reaching r, and looking up each a[i] through the root of the segment tree. Composing two transition tables takes O(H) time, so each activation/deactivation takes O(H\log Q) time. EDIT: took the big-O times out of maths mode since the images seemed to be broken.
•  » » 22 months ago, # ^ |   0 Build a segment tree, where each node has an array to[1...100](to[i] refers to what the number i will become after all modifications on the interval).Yet actually, I solved the problem using 100 bitsets(S[1...100]) of length n, where S[i] consists of all appearances of number i. Despite the O(nq) complexity, the constant is so small that I passed all the test cases. 33723537
 » 22 months ago, # |   +7 I think Problem D needs N*M big test cases. Some of the programs are obviously O(NM), with constant > 2, which is most likely to be TLE, but we cannot submit that big test cases to hack.
•  » » 22 months ago, # ^ |   0 Can you link one of this submissions ?
•  » » » 22 months ago, # ^ |   +8
•  » » 22 months ago, # ^ |   +10 You can use test generators.
•  » » » 22 months ago, # ^ |   +26 I'm curious: are you using some sort of automated system to download source code for local testing? I can't imagine doing 300+ challenges by hand...
•  » » » » 22 months ago, # ^ |   0 Well, I always fill the hack form by hand (does copy-paste count?). It is as tedious as you can imagine.Local testing is the primary source of the challenges. It is a good idea to check the test locally in any case to avoid unsuccessful challenges. Unless it is UB, in which case I use custom invocation tab for checking and tuning the test. I also use Virtual Box for all local testing just in case.
•  » » » » » 22 months ago, # ^ |   0 Are you also manually copy-pasting from the solution view into the file you test on locally? Assuming the majority of solutions aren't hackable, then presumably that involves more work than the actual hacks.
 » 22 months ago, # |   0 how to solve F : Tree Destruction ?
•  » » 22 months ago, # ^ |   +10 Find a diameter of the tree first, then delete all the points outside the diameter, finally delete the points on it one by one..
•  » » » 22 months ago, # ^ |   0 thx
•  » » » 22 months ago, # ^ |   0 Any ideas to prove this?
 » 22 months ago, # |   0 E is just a simulation problem , why added the "data structure" tag ??
 » 22 months ago, # |   0 Got plenty of TLE on G qwq
 » 22 months ago, # | ← Rev. 2 →   0 When I first saw problem D, I thought of splay tree.... But then I found that a is equal to -a under modular 2.... Then it was solved under the complexity of O(n+m)...
•  » » 22 months ago, # ^ | ← Rev. 2 →   0 Can you explain the preprocessing part of your code? How to count initial no. Of inversions
•  » » » 22 months ago, # ^ | ← Rev. 2 →   +11 It's well known that if you want to get the exact number of inversions of a given permutation , you can solve it in no less than O(n log n).However ,this problem is only about the parity of the permutation.Consider a theorem in linear algebra:If you swap any 2 elements of a permutation ,the parity of the permutation will change.And we know that the permutation "1 2 ... n" is an even permutation.That is, if we swapped C pairs of numbers to make it identity permutation, the parity of the number of inversions is the same as C's.Sorry for my terrible English if it does trouble you :D
•  » » » » 22 months ago, # ^ |   0 Thanks that helped
 » 22 months ago, # |   0 In problem C, how to prove 4 2 4 is a valid case ?
•  » » 22 months ago, # ^ |   +3 ((1,3)(2)(4))for every 4 numbers.
•  » » » 22 months ago, # ^ |   0 Sorry still don't get it :-( maybe if you can tell me the logic behind your solution please.
•  » » » » 22 months ago, # ^ |   +3 Well...The question is to ask whether there exists some residue classes whose union is N_+.It's obvious that if S= 1/k_1 + 1/k_2 + 1/k_3 < 1 , then it's impossible to reach the condition.May wish to let k_1 <= k_2 <= k_3 , that means, if k_1 > 3 , it's invalid.Next, if k_1=3 the only solution is that k_1=k_2=k_3=3 , otherwise S < 1.We can easily get the idea that if there exist k_i = 1 , it's always correct.Finally we think of the state of k_1 = 2.The valid solutions are (2,2,x) and (2,4,4) ,because we can let (x_1,x_2,x_3)=(1,2,x)and(1,2,4) respectively.It can be proved that most of the other conditions lead to S < 1 , except for (2,3,3),(2,3,4),(2,3,5),(2,3,6), but we can verify that they are invalid.
•  » » » » » 22 months ago, # ^ |   0 Thanks for the help :-)
•  » » 22 months ago, # ^ |   0 We can start the garland with time interval = 2 on an odd number(let's say we start from 1). So according to the problem statement 1,3,5,7,......,2*n + 1 are covered by this garland. With odd time intervals covered, now we need to cover only the garlands that occur at even time intervals.Now lets start another garland with time interval = 4 from an even number( say 2). Now this garland covers time interval 2,6,10,14,....4*n — 2. Now we see the only time intervals left are multiples of 4. 4,8,12,....,4*n. Thus starting the next garland with time interval = 4 from 4 will cover all the time intervals. Hence we get the solution.Hope this helped!
•  » » » 22 months ago, # ^ |   0 Thanks for the help :-)
•  » » 22 months ago, # ^ |   0 Take values of k 1,2,3
 » 22 months ago, # |   0 when will we have editorials for this round ??
•  » » 22 months ago, # ^ |   0 After hacking phase ends. Maybe along with goodbye 2017.
 » 22 months ago, # | ← Rev. 5 →   0 Hi guys. I'm doing hack on prob.Ei used code generatorhttps://ideone.com/GslUJNon following two submissions. above code generator seems generating valid input (actually hack results show that "Checker: ok jury and participant have equal answers" in both submission)But the problem is that in my local environment, above submissions show different output... then, at least one hack should be succeeded. right?But both hack failed...is there any problem in my thinking ?
•  » » 22 months ago, # ^ |   0 There exist endl at the end of one of them. Remove it or add endl in other one.
•  » » » 22 months ago, # ^ | ← Rev. 2 →   0 What i mean different output was "Totally different" (if you execute code, then you will know) not the existence of endl or not... anyway thanks
 » 22 months ago, # |   0 For problem D, I computed the number of pairs being reversed in a range using (int)ceil(((float)r - l) / 2) And to get whether this would change the parity of inversions I just mod the above expression by 2.Can someone point the mistake.
•  » » 22 months ago, # ^ |   0 The correct formula to get the number of pairs being reversed in a range is d(d-1)/2, where d is the number of elements you are swapping ( r — l + 1 ). First number can form d-1 pairs, second one d-2, ... , 2 , 1.
•  » » » 22 months ago, # ^ |   0 Now I get it. Thanks.
 » 22 months ago, # |   +10 I don't know if it's already mentioned in the comments, but here's a solution for problem G that is online and can be adapted for arbitrary-sized alphabet:http://codeforces.com/contest/911/submission/33762818It uses the Split-Merge Segment Trees chinese trick, where merges amortize to overall O(n * log(n)) complexity. The code is conceptually simple.
•  » » 22 months ago, # ^ |   0 Could you sketch how to prove for q merge or split operations? (I only know a proof for (I posted that proof for a similar solution here.).)
•  » » » 22 months ago, # ^ |   0 If you look at the implementation, you can see that every split/make call creates log(n) nodes and every merge recursion step removes exactly one node, amortizing the total time to O(nlog(n))
 » 22 months ago, # |   +1 Editorial :/
 » 22 months ago, # |   0 It shows testing has finished. But, my solution is still in queue.
 » 22 months ago, # |   +46 Regarding to message from systemYour solution 33722462 for the problem 911A significantly coincides with solutions priyanka1998/33722461, priyanka1998/33722462. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties.Sir as you can see both solution priyanka1998/33722461 and priyanka1998/33722462 were submitted from same user priyanka1998. Sir due to network problem this error occured that when I clicked on submit button same solution submitted twice. I haven't violated any rules.
•  » » 22 months ago, # ^ |   +1 Maybe I have the same problem http://codeforces.com/blog/entry/56663?#comment-404188
•  » » 22 months ago, # ^ |   +1 Same thing happened with mme
 » 22 months ago, # |   +10
 » 22 months ago, # |   0 what the contest will be rated on # of prob. or what ?
•  » » 22 months ago, # ^ |   +2 Hi physics 0523. Same thing happened to me. "Your solution 33730274 for the problem 911C significantly coincides with solutions aashifkhanate/33729291, aashifkhanate/33730274. "
 » 22 months ago, # |   +3 I think I just got disqualified using my own solution.I recieved "Your solution 33730274 for the problem 911C significantly coincides with solutions aashifkhanate/33729291, aashifkhanate/33730274.". I changed the array size from 10^5 to 10^6 which may not be a huge difference to you but I was expanding my guessed solution space for problem C. Please see what's wrong here. Thanks
 » 22 months ago, # | ← Rev. 2 →   +4 Hi, I've just got disqualified because one of my solution coincides with another user's solution (the message is below).I want to clarify that I did not see/copy/plagiarize his solution prior writing my own solution. Our algorithms are very similar, but I assure you that's purely coincidental. I don't know what kind of evidence I can give, but I got my solution on my own, not from reading a leakage or something. I never even viewed user sazzach before.Thank you for you reconsideration.Attention!Your solution 33715309 for the problem 911A significantly coincides with solutions sazzach/33713630, hypermassive/33715309. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties.
 » 22 months ago, # |   +4 I have been caught in plagiarism with my own solution. Your solution 33722840 for the problem 911C significantly coincides with solutions sdssudhu/33722503, sdssudhu/33722840. I resubmitted my solution with some changes as I wasn't sure about my first one and since it was ICPC rules if my first one got AC the second one didn't matter.Please help.
 » 22 months ago, # |   +3 Attention! Your solution 33736695 for the problem 911A significantly coincides with solutions HunterYH/33715069, HunterYH/33736695. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. **my English is poor ** You can see both my 33736695 and HunterYH/33715069 and HunterYH/33736695 were submitted from same user HunterYH. I only submit same code twice,because at first I used GNU C++17 Diagnostics it will easy get TLE so I submit same code with GNU C++. I think I haven't violated any rules.
•  » » 22 months ago, # ^ | ← Rev. 5 →   +4 HunterYH sdssudhu hypermassive physics0523 aashifkhanate I got the same message :/
•  » » 22 months ago, # ^ |   0 So bad.
 » 22 months ago, # | ← Rev. 8 →   +4 Hello Everyone, This morning I got a message from system that my submission http://codeforces.com/contest/911/submission/33725640 during the Educational Codeforces Round 35, has been found significantly similar to http://codeforces.com/contest/911/submission/33725051 and my account may get blocked due to this.Both of the submissions were made my me for Question C, and i was thinking that the earlier one would be ignored as we have in any normal Round.I request the community to help me out here. I have attached the screenshots for more details.Educational Codeforces Round 35 (рейтинговый для Див. 2)
•  » » 22 months ago, # ^ |   0 probably, someone blocked problem C in your room and leak your code to another guy :C
•  » » » 22 months ago, # ^ |   +2 In another blog, MikeMirzayanov replied that its a bug and will be fixed soon :D
 » 22 months ago, # |   +1 Editorial?
•  » » 22 months ago, # ^ |   +8 soon
 » 22 months ago, # |   0 Auto comment: topic has been updated by PikMike (previous revision, new revision, compare).
 » 22 months ago, # |   +3 do we have editorials for educationals. if yes when will they be released??
 » 22 months ago, # |   0 Auto comment: topic has been updated by PikMike (previous revision, new revision, compare).
 » 21 month(s) ago, # | ← Rev. 2 →   +1 I know administrators are busy and this week is the New Year's Holiday, But please corresponding to the problem(the message from the system) as fast as you can... Because of this problem,I may will miss to promotion to blue coder... Please change my submission Rated...
•  » » 21 month(s) ago, # ^ |   +1 My rating should also increase. Please rerate the round. Atleast reply something.
•  » » » 21 month(s) ago, # ^ |   0 I think so too,I want some reply from administrator quickly...
 » 21 month(s) ago, # |   +1 Hey,do administrators forgot this problem...?I've not got any replys...
•  » » 21 month(s) ago, # ^ |   0 I noticed that my submission changed official andd became blue!! thx!
 » 21 month(s) ago, # |   0 I am new on codeforces. I have much question about this bootcamp. I am from bangladesh and I am a school student, Read in 0 Level. I want to participate on this bootcamp.but I didn't understand how? is there any school student's allowed?if allowed then I want to go. But I haven't money to pay for this my family isn't have enough money. and most of I haven't any passport and paypal or anything bank account.But I want to participate on this. But How? please Help me? Vovuh PikMike