### zer0brain's blog

By zer0brain, 7 weeks ago, translation,

### Hello, Codeforces!

SomethingNew and I are glad to invite you to Codeforces Round #814 (Div. 1) and Codeforces Round #814 (Div. 2), which will take place on Aug/16/2022 17:35 (Moscow time). Each division will have 6 problems and 2 hours to solve them.

We would like to thank:

#### Score distribution:

Div. 2: 500 — 1000 — 1250 — (1250 — 1000) — 2500 — 2500

Div. 1: (500 — 500) — 1250 — 1250 — 2250 — 2250 — 2750

We hope that you will enjoy solving our problems!

#### Editorial

Congratulations to the winners!

Div. 2:

Div. 1:

• +250

 » 7 weeks ago, # | ← Rev. 2 →   +274 As an author, I authored this round.
•  » » 7 weeks ago, # ^ |   +38 Good
•  » » » 7 weeks ago, # ^ |   +22 I hope problem statements will be as short as announcement
•  » » » » 7 weeks ago, # ^ |   +24 As a contestant, i will contest.
•  » » 7 weeks ago, # ^ |   +62 As a participant, I will participate in this round.
•  » » 7 weeks ago, # ^ |   +35 As a tester, I tested this round.
•  » » » 7 weeks ago, # ^ | ← Rev. 3 →   +22 It was a joke .. Anyways I have edited it now.
•  » » » » 7 weeks ago, # ^ |   +15 Bro dont do these type of things honesty is important
•  » » » » » 7 weeks ago, # ^ |   +135 As a cheater, I will cheat in this round :) He already seems to be very honest.
•  » » » » 7 weeks ago, # ^ | ← Rev. 2 →   +56 Behind every joke there is some truth
•  » » » » » 6 weeks ago, # ^ |   0 And that is called sarcasm
•  » » » » 7 weeks ago, # ^ | ← Rev. 2 →   -16 .
•  » » » » » 7 weeks ago, # ^ |   0 Bro Just check my profile and you will get to know how honest I am. Secondly,never ever make false statement on someone untill you are confirmed about something.
•  » » » » » 7 weeks ago, # ^ |   0 lol all you people are mad because he is better than you and will win. classic codeforces people what can you do.
•  » » » » 7 weeks ago, # ^ | ← Rev. 2 →   -27 wow !
•  » » » 7 weeks ago, # ^ |   +10 As a Vladithur orzler, I will participate.
•  » » 7 weeks ago, # ^ |   +5 I am a participant if and only if I am a participant.
•  » » 7 weeks ago, # ^ |   0 Great, I think that the round will be good
•  » » 7 weeks ago, # ^ |   +14 As a participant
•  » » 7 weeks ago, # ^ |   -12 ok
•  » » » 7 weeks ago, # ^ |   -41 Aur mujhe bolta tha comment kyu padh rha :/
 » 7 weeks ago, # |   +12 Hope I won't participate in another Speedforces round.
•  » » 7 weeks ago, # ^ |   +95 i hope so too
•  » » » 7 weeks ago, # ^ |   +119 hopeforces
 » 7 weeks ago, # |   0 Is this round, a speedforces round?
•  » » 7 weeks ago, # ^ |   +5 spoilerforces moment
•  » » » 7 weeks ago, # ^ |   0 lol
•  » » » » 7 weeks ago, # ^ |   -22 question toh laga nhi rha, bas comment kara lo iss se
•  » » » » » 7 weeks ago, # ^ |   0 ++
•  » » 7 weeks ago, # ^ |   +20 penaltyforces
•  » » » 7 weeks ago, # ^ |   0 true
 » 7 weeks ago, # |   -32 I hope the questions are very difficult, so that I can show my strength. Ordinary div2 questions are too easy, and I type too slowly to get high scores. I hope it is more difficult!
•  » » 7 weeks ago, # ^ |   +16 ^^ If a protagonist with "the power of friendship" had a CF account
•  » » 7 weeks ago, # ^ |   +26 you can start solving problem D , Have a nice Day
•  » » » 7 weeks ago, # ^ |   0 Thx!
•  » » 7 weeks ago, # ^ |   0 Good luck
 » 7 weeks ago, # |   0 Is there going to be some limitation with regards to rating? I'm a newbie can I still participate?
•  » » 7 weeks ago, # ^ |   +6 Everyone can participate in every contest. The only issue is that if your rating is too high, your rating will not be affected by participating in lower-difficulty (higher Division number) contests. But since you're grey, your rating will be affected by all contests. In fact, if your performance is better than what is expected of your low newbie rating, you will very likely have your rating increased. I highly recommend participating in ALL contests.
•  » » » 7 weeks ago, # ^ |   0 Alright, thanks for letting me know. Excited to learn and improve!
 » 7 weeks ago, # | ← Rev. 2 →   +23 Respect for ilaburkov
•  » » 7 weeks ago, # ^ |   +2 “Thank ilaburkov for existing”……
 » 7 weeks ago, # |   +3 Hope . I'll reach pupil this time.
•  » » 7 weeks ago, # ^ |   0 Hope to specialist
 » 7 weeks ago, # |   +10 I WANT TO REACH MAAAAAAAAASTER!!!!!!!!!
•  » » 7 weeks ago, # ^ |   +77 ok
 » 7 weeks ago, # |   +4 Why do I feel that this announcement is quite shorter than others? In my impression the announcement of a contest is usually one screen long. (curious)
 » 7 weeks ago, # |   0 Really hope there is gonna be nothing wrong with this contest
 » 7 weeks ago, # |   0 Request for Authors: Please write the editorial with hints.
 » 7 weeks ago, # |   +92 Hope, I will get SomethingNew from this contest. After ContestBecame Green :)
•  » » 7 weeks ago, # ^ |   +116 Hope I will get some more brain after this contest. _After Contest_zer0brain
•  » » » 7 weeks ago, # ^ |   -20 Hope my brain gets bigger after this contest. After Contest-1024mb Brain Memory Limit
 » 7 weeks ago, # |   0 Hope to achieve a satisfactory result in this competition
 » 7 weeks ago, # |   0 Hope to get specialist back (again)
 » 7 weeks ago, # |   0 I hope to get expert on this round!!!
•  » » 7 weeks ago, # ^ |   0 Me too! I got specialist today, and hope I'll get Expert after this round
•  » » » 7 weeks ago, # ^ |   0 I am newbie since long and now pupil :)
•  » » » » 7 weeks ago, # ^ |   0 Why is it that every time I say "I will get Expert today", I lose a bunch of rating
•  » » 7 weeks ago, # ^ |   0 I hope to improve after every round!
 » 7 weeks ago, # |   0 Hope I'll reach Expert after this round.
 » 7 weeks ago, # | ← Rev. 2 →   +178 Hope I will see SomethingNew in this contest on my IP address 127.0.0.1 and won't be having zer0brain to solve a problem that would have a memory limit of 1024mb.
•  » » 7 weeks ago, # ^ |   -60 you're so cringe kid
•  » » » 7 weeks ago, # ^ |   +74 LOL, I usually try to do SomethingNew.
•  » » » » 7 weeks ago, # ^ |   0 yikes.
•  » » 7 weeks ago, # ^ |   +23 How about Wrong_answer_on_pretest2 ?
•  » » » 7 weeks ago, # ^ |   +1 nightmare
•  » » » 7 weeks ago, # ^ |   0 yeah if you store my WA on pretest2 in a 3 bit integer It overFlow :(
•  » » 7 weeks ago, # ^ |   0 qpee
 » 7 weeks ago, # |   0 By score distribution looks like round will be very balanced
 » 7 weeks ago, # |   +31 Problem D in Div2 and Problem A in Div1 both have subtasks so does this mean that Div1A=Div2D? Will this Div1 be harder than usual?
•  » » 7 weeks ago, # ^ |   -24 Either that or an extremely easy one, I'm hoping for the latter to allow me to get close to 2100 mark again after AK in Div2. :DI don't think sharing true info would be fair though, as some participants may opt to do/skip round if the answer favors them.
•  » » 7 weeks ago, # ^ |   +48 Yes, Div1 A is Div2 D. We think that this will make our round more balanced.
•  » » » 7 weeks ago, # ^ |   0 OK, thanks for your reply :)
•  » » » 7 weeks ago, # ^ |   0 so scared~ this could be my first DIV1 solving only A.....
 » 7 weeks ago, # |   +14 as a tester, I tested this round
 » 7 weeks ago, # |   +5 ilaburkov orz
 » 7 weeks ago, # |   +6 As a tester, I tested this round. Good luck everyone :)
 » 7 weeks ago, # | ← Rev. 2 →   0 Edit: I was wrong D:
 » 7 weeks ago, # |   -19 Hope to solve D this time :D
 » 7 weeks ago, # |   +3 This will be my first div 1 Wish me good luck!
 » 7 weeks ago, # |   -16 Hope to get pupil on this round ಥ_ಥ
•  » » 7 weeks ago, # ^ |   0 lol
 » 7 weeks ago, # |   +70 Interesting scoring distribution observation: In Div 2, the second part of the split problem is easier than the first part, but in Div 1, they’re apparently equally difficult…
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   -15 I'm quite sure the Div2D = Div1A exactly. I doubt there is much to be gleaned from the discrepancy in how the scores are distributed. The Hard version is treated like a Div1A problem (which oranges/reds should be able to solve), with the Easy version being worth exactly half. But for Div2 participants, it's treated as a D problem, which isn't as accessible, especially since ABC would take up some time at first, so it's a little harder to achieve the Hard solution for this Div2D. I guess that may justify giving it slightly more score than the Easy version in Div2, despite being identical to Div1A, and I don't think anything could be inferred by the relative difficulty of the two subtasks beyond the estimate that they're roughly equal.
 » 7 weeks ago, # |   +8 Make me closer to red, plz.
 » 7 weeks ago, # | ← Rev. 2 →   +32 A1,A2 ?! Really rare！Hope that the round will be nice to everyone. :)
 » 7 weeks ago, # |   -20 hope i will solve AB.
 » 7 weeks ago, # |   0 Only 50 points left to reach specialist. Wish us good luck!
•  » » 7 weeks ago, # ^ |   0 me too
 » 7 weeks ago, # |   0 Div1A1 = Div2D1 are not Div1A = Div2C As usual, So I expect that the first 3 problems in the Div2 will be very easy everyone can solveGood Luck everyone
•  » » 7 weeks ago, # ^ |   0 Predictionforces are strong with this one
 » 7 weeks ago, # |   0 Hope I can do well
 » 7 weeks ago, # |   +8 As an coder, we will code this round.
 » 7 weeks ago, # |   0 As a newbie, i will participate in this round as a hope to reach pupil...
 » 7 weeks ago, # |   0 All The Best EveryOne !!!
 » 7 weeks ago, # |   0 Kindly remove the candidate masters from div 2 registered participants.
 » 7 weeks ago, # |   0 Thank you ilaburkov for existing!
 » 7 weeks ago, # |   0 hope i become newbie again
 » 7 weeks ago, # | ← Rev. 2 →   -95 F**k your systems, Why I'm not able to register before 3/4 minute starting contest? What's the f***king system that's are it?
 » 7 weeks ago, # |   +30 Why Burenka and Tonya? Where are Alice and Bob?༼ つ ◕_◕ ༽つ
 » 7 weeks ago, # |   -42 Bad contest and bad implementation problems!Overall disliked this contest
•  » » 6 weeks ago, # ^ |   0 You just have skills issues lmao. The first 4 problem was really balanced
 » 7 weeks ago, # | ← Rev. 2 →   +94 Descriptions are there to help participants understand, not to prevent them from understanding.
 » 7 weeks ago, # |   0 I think Problem b is hard to understand and hard to solve!
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   0 it just needs a bit of number theory and some scribbling on paper, but I don't think it's that hard
•  » » » 7 weeks ago, # ^ |   0 Yes I spend all my time trying to solve it in a paper but I couldn't solve it! Waiting for the editorial.
•  » » 7 weeks ago, # ^ |   0 Just follow the pattern of the output of the samples. :) In a lot of problems, you will not need to go too deep and proof things mathematically during the contest.
•  » » 7 weeks ago, # ^ |   0 It was not hard. You just need to run some testcases on paper.
•  » » 7 weeks ago, # ^ |   0 Why is it hard to understand?
 » 7 weeks ago, # | ← Rev. 5 →   -18 Praise to Allah for the fact that I did not participate in the competition, if I participated in this contest, I, like many, would not be able to solve the problem C.
•  » » 7 weeks ago, # ^ |   -12 you know, my rating is not 1200
•  » » » 7 weeks ago, # ^ |   -15 Once again praise be to Allah
•  » » » 6 weeks ago, # ^ | ← Rev. 2 →   -11 toxic russian nigger
 » 7 weeks ago, # |   -9 lol i had the feeling that pretests are so weak ( especially for b) i hope i am wrong i realized that after locking the problem i didn't know why did i do that :(
 » 7 weeks ago, # |   +62 speedforces, penaltyforces, gapforces.
•  » » 7 weeks ago, # ^ |   0 Can't agree more
 » 7 weeks ago, # | ← Rev. 2 →   +4 How to solve D1 and D2?Also what's solution to B? I did some case work which is probably not intended.
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   0 Problem B: For k%2==1, just take (1,2), (3,4)... (n-1,n) For k%4==2 again take (1,2), (3,4).... ,but for pair (i,i+1) if (i+1)%4==0, take (i,i+1) else take (i+1,i) For k%4==2 there is no solution
•  » » 7 weeks ago, # ^ | ← Rev. 3 →   0 Detail B solution is: look at n%4 and k%4. Then look at pairs mod 4: for example n%4==0, so numbers%4= 1, 2, 3, 0, 1, 2, 3, 0. If k=0 its impossible, k=1: a=3, b=1 and a=2, b=0 — 2 pairs. (so 1st pair a%4=4-k%4, second pair b%4=0)
•  » » 7 weeks ago, # ^ |   0 First of all, lets do k %= 4. If k == 0 there is no answer, idk why.You can solve this problem from each group of 4 independently:1000 2 2 1 3 4 6 5 7 8 10 9 11 12 And so on...Now just some case-work for each k valueBtw, i got B 10 seconds before contest ended (01:59:50 Pretests passed [pretests])
•  » » 7 weeks ago, # ^ | ← Rev. 5 →   +9 I didn't have time to implement it, but I think D1 can be done using 2D DP. The key observation is that there is never any benefit to selecting a range of more than 2 elements, since the time taken for a block of size k + 2 is the same as the time taken for doing the block of k and the block of 2 separately. So to zero out an element whose current value is $v$, you would have to XOR it with $v$, but you can also choose to drag the next element to be XOR'd with $v$ (without costing additional time). There is no point in considering a longer range for this XOR.For an array of size $n$, consider the last element. You can either zero out the first $n - 1$ elements (DP) and then zero out the last element by itself, OR you can zero out the first $k$ elements, and then start an XOR chain from the $k + 1$-th element, where each element becomes 0 while XORing its next element as well. Depending on where you start the chain, the residue at the end varies, so you can check all possible values of $k$ to determine which of these XOR chains will zero out the last element and then choose the one with the shortest time.This takes $O(n^2)$ time, so it obviously wouldn't work with D2, for which I have no clue whatsoever.
•  » » » 7 weeks ago, # ^ | ← Rev. 2 →   +4 the trick is to maintain all possible residue values in a set, and then use it if it lets u merge the next guy with the next block.You can do this maintain by having a set and an additional "change" value that is supposed to modify all the elements of the set. To xor everything in the set, u just xor the change value, and to insert/query x, you insert/query x^change instead.
•  » » » » 7 weeks ago, # ^ |   0 Doesn't the set get really really big?
•  » » » » » 7 weeks ago, # ^ |   +1 u do it iteratively, like u only zero out the current block, and then consider pushing it one further (which adds/changes the residues). and if u can use a residue to merge a single guy with the next block u use it. So set only grows to O(n)
•  » » » » » » 7 weeks ago, # ^ |   0 Ah gotcha.
•  » » » 7 weeks ago, # ^ |   0 Tried this, TLEd
•  » » » » 7 weeks ago, # ^ |   +1 Hmm, I just submitted this approach right now and it was accepted (only 124ms): https://codeforces.com/contest/1719/submission/168605232I checked your submission, but I'm not too familiar with Java. However, it doesn't seem like you're actually a building a 2D array/table of the resulting XOR residues? So I'm guessing that you might be calculating the result of the XOR chain every time, which would yield a worst-case complexity of $O(n^3)$ (need to calculate the best time at a linear number of endpoints, each endpoint considering a linear number of XOR chains, with each XOR chain being computed in linear time).But if you maintained a table of the residues from each starting point (can be 1D, now that I think about it), then it should reduce to $O(n^2)$, which should definitely pass.
•  » » » » » 7 weeks ago, # ^ |   0 Ah, you are right. I was in n^3.Submitted an n^2 solution and passed, keeping a 1d array.
•  » » 7 weeks ago, # ^ | ← Rev. 3 →   0 Problem B solution:For k%4==0 we have that (a+0)*b=0(mod 4) => a*b=0(mod 4), so if a is odd than we have that b must be divisible by 4(we have n/2 odd nubmers from 1 to n and n/4 numbers divisible by 4 from 1 to n), so we have that for k%4==0 there is no solution.For k%4==1 we have that (a+1)*b=0(mod 4) we can see that we can just print pairs that contains one even and one odd number(like {1,2},{3,4}, etc.)(same approach is for k%4==3(k%2==1))For k%4==2 (a+2)*b=0(mod 4) than we can split all odd numbers from 1 to n in 2 groups. First group is 1,3,5,7,n/2-1 and the second one is n/2+1,n/2+3,...,n-1. Odd numbers from first group is gonna be first numbers of pairs(a) and the second numbers of that pairs(b) will be numbers that are divisible by 4(than we have pairs like {1,4},{2,8}, etc.). In other half of our pairs second group of odd numbers is second number(b) and the first number(a) is the numbers that gives rest 2 divided by 4.nichke u can see my approach here
 » 7 weeks ago, # |   0 I DID NOT CHOOOKE!!!
 » 7 weeks ago, # | ← Rev. 2 →   0 upd: nvm i overcomplicated
 » 7 weeks ago, # |   +3 Just guessed B looking at samples :)
•  » » 7 weeks ago, # ^ |   0 Guessforces
•  » » 7 weeks ago, # ^ |   +1 same i guessed a and b
•  » » 7 weeks ago, # ^ | ← Rev. 3 →   +1 thats true however, its easy to verify the validation of the solution by bruteforcing the solutions however, i feel like the test cases are too weak i forgot to use long long instead of int when calculating ((a + k) * b) % 4 would it pass? ps : never mind i also made k long long ( however a and b is int) thats too an accident ( what a good accident)!
•  » » 7 weeks ago, # ^ |   0 Same XD!
 » 7 weeks ago, # |   +75 Was the round really balanced? I feel D1C is very easy and D1A2 (and A1) are crazy hard (almost I missed it).
•  » » 7 weeks ago, # ^ |   +26 at least you didn't lose your mind optimizing the wrong solution for C lol
•  » » 7 weeks ago, # ^ |   0 idk, D1A1/A2 are quite simple with one observation, I missed A2 only because of i<=n in place of i
•  » » » 7 weeks ago, # ^ |   0 What observation is there in D1A1/A2?
•  » » » » 7 weeks ago, # ^ |   +10 you only need to xor segments of lenght either 1 or 2 (so when you find a sequence with xor 0, you can erase it for a cost = its length — 1, and you need to maximize such sequences)
•  » » » » » 7 weeks ago, # ^ |   0 Nice observation!
•  » » » » 7 weeks ago, # ^ |   0 it's optimal to consider ranges which have their xor = 0 (i.e. xor(l,r)=0), cause you can always make them all 0 in (r-l) moves. Now just use as many ranges as possible, the rest you can make 0 in 1 move for each element Example:1 3 7 5 5 5 7 6You can xor ranges: [0,1], [1,2], [2,3], so range [0,3] becomes full 0,Then you can xor [4,5], so this range becomes 0Then xor [6,6] [7,7]You can't have more optimal solution for this case, and in general it worked for all cases, so the rest is only implementation details.At least for A1 I can tell precisely, it worked. If you're still curious, what I did:A DP[N][N] where dp[l][r] means number of steps to make range l,r 0. It works in n^2, which fits A1 restrictionsthen i did another dp, ans[i]=min(ans[j]+dp[j][i]), j
•  » » » » 7 weeks ago, # ^ |   0 yeah, it got ACcode:
•  » » 7 weeks ago, # ^ |   +58 I mean, A might have been a bit tricky (maybe too tricky for an A), but crazy hard is definitely an exaggeration
 » 7 weeks ago, # |   +9 why
 » 7 weeks ago, # | ← Rev. 2 →   +8 I spent an hour trying to optimise 1C, then I realised you dont need to try all k = factors, just k = n/prime factor! Also, how do you prove that greedy works for 1B?
•  » » 7 weeks ago, # ^ |   0 I'm just the same as you. And I solve 1C in 1h51m, and don't have time to implement 1B. Haha
•  » » 7 weeks ago, # ^ |   +3 sum of alternating fib numbers is bounded by the next fib. So if u have multiple things > the biggest fib, then not taking the biggest letter u have means that there will not be enough space to use it.
 » 7 weeks ago, # |   +14 waiting for tutorial ...
 » 7 weeks ago, # |   0 div2 C , bet most of you all (who WA'd) got the approach right but missed some corner cases :D
•  » » 7 weeks ago, # ^ |   +5 Insn't it just simulate n fights and collect the wins foreach fighter? What edgecase?
•  » » » 7 weeks ago, # ^ |   +2 lol, i got 6 WAs just because i forgot to print max(0, res) for player with power n
•  » » » » 7 weeks ago, # ^ |   0 Ok, the strongest fighter is the edgecase :)
•  » » » » » 7 weeks ago, # ^ |   0 There's a test in the example for this edgecase though
•  » » 7 weeks ago, # ^ |   0 here I am with 5 WAs and 2 TLEs T_T (Too desperate to get pupil) Nvm, i enjoyed!
 » 7 weeks ago, # | ← Rev. 3 →   +6 Div2 C has too much corner cases, and Div2 DE is easier than Div2 C The gap between Div2D and Div2E is too small. I think the contest is not balanced.
•  » » 7 weeks ago, # ^ |   +7 what corner cases?
•  » » » 7 weeks ago, # ^ |   +1 For those id=1 and id>1, the answer is different.
•  » » » » 7 weeks ago, # ^ | ← Rev. 2 →   0 So, one corner case, I guess it's ok
•  » » » » » 7 weeks ago, # ^ |   0 My problem was that I forgot in some cases that there are k round, not infinite, and so I only managed to get AC on 6th try
•  » » » » 7 weeks ago, # ^ |   0 are there any other corner cases(not in the sample test cases)? because i did include it in my code it still gave wa
•  » » 7 weeks ago, # ^ |   +3 In Div2C I did simulation of the first $n-1$ fights while answering queries. I sorted the queries by $k$.
•  » » » 7 weeks ago, # ^ |   0 same
•  » » » 7 weeks ago, # ^ | ← Rev. 2 →   +1 OMG Is that work? I thought I must print the answer immediately after the query, So I use stack to find the Next Greater Element. My implementation is too complicated.
•  » » » 7 weeks ago, # ^ |   +3 As an alternative we can collect the numbers of the rounds for the winners, and do binary search on each query.
•  » » » » 7 weeks ago, # ^ |   0 I landed on this approach eventually, but still mad I didn't think to rearrange the queries (after however many past problems with 'try reversing them' as a main gag).I was also embarrassingly slow at making it work on account of managing to stab myself with seemingly every possible fence-post-y bug possible.With hindsight: it was right there too... "gee, this stresstesting sim sure keeps around a lot of old state in case it's relevant to a query" :P
•  » » 7 weeks ago, # ^ |   0 I spent all my time on C and solved it. Didn't get enough time for D and E :(
 » 7 weeks ago, # |   0 https://codeforces.com/contest/1180/problem/C and div2 C are very similar problems
 » 7 weeks ago, # |   +3 How to solve div2 D1? I tried to use dp but failed.
•  » » 7 weeks ago, # ^ |   +6 It is indeed DP. First it's easy to see that one either changes a[i] to i^x or changes a[i] to a[i]^x and a[i+1] to a[i+1]^x. So let's say that dp[i][j] stands for the minimum cost of changing the first i-1 elements to 0, and the i-th element becomes j. You can try to read my submission if you want: https://codeforces.com/contest/1719/submission/168590571
•  » » » 7 weeks ago, # ^ |   0 very clean and easy-readable solution, ty!
•  » » 7 weeks ago, # ^ |   0 Always do operation on a subarray of size 2. Go from left to right and maintain all possible values current element can have. If any one of them is zero then pass otherwise one more operation.
 » 7 weeks ago, # |   -25 good tasks i enjoyed the round
 » 7 weeks ago, # |   0 I used hashmap :(( RIP, hack is gonna be BRUTAL. At least I can do D1 tho
 » 7 weeks ago, # |   +7 I tried as never and fail as ever
 » 7 weeks ago, # |   +83 Problem E is a kind of Graph Isomorphism Problem, with many restrictions on the graph. And my solution is, ahem, to run a heuristic solution to the general case (+ a bit of optimization).
 » 7 weeks ago, # |   -50 in my opinion Div1: A1
•  » » 7 weeks ago, # ^ |   +39 I thought that B >>>>> A = C and that having subtasks in A was completely pointless, so your order is very surprising.
 » 7 weeks ago, # |   +148 I think the author should give more meaningful sample. My program that have so many wrong place can still accept the sample in problem A and B. But I don't think giving contestant meaningless sample should be the difficulty of the problem.
 » 7 weeks ago, # |   +11 How to solve E in something like $O(nm\log(nm))$?I found an $O(nm\min\{n,m\})$ solution which unfortunately cannot pass:You are checking if two bipartite graphs, with edges colored, are isomorphic;For each component of the bipartite graph, if you sort all edges by their color, choose a starting vertex on the smaller side, then DFS would give a unique sequence that determine this component. But in my solution I have to iterate the starting vertex, thus ends up with $O(nm\min\{n,m\})$ complexity. Just do this to both graphs and check if they are the same.
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   +11 I had $O(nm \min(n,m))$ which passed the tests in 670ms, I think it was the intended or they would increase limits to make ti TLE. However, Um_nik managed to get it in 140ms. Maybe he found a better solution?
•  » » » 7 weeks ago, # ^ |   +3 I guess hashing paths of length at most $O(\min\{n,m\})$ starting from each vertex is correct? If so, this would decrease constant by a lot.
•  » » » » 7 weeks ago, # ^ | ← Rev. 2 →   +10 I don't think I did that. I just hashed the entire grid. My code for reference//もう布団の中から出たくない //布団の外は寒すぎるから //布団の中から出たくない //布団の中はあたたかすぎるから #include using namespace std; #define int long long #define ll long long #define ii pair #define iii tuple #define fi first #define se second #define endl '\n' #define debug(x) cout << #x << ": " << x << endl #define pub push_back #define pob pop_back #define puf push_front #define pof pop_front #define lb lower_bound #define ub upper_bound #define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--)) #define all(x) (x).begin(),(x).end() #define sz(x) (int)(x).size() mt19937 rng(chrono::system_clock::now().time_since_epoch().count()); const int MOD=998244353; const int P=177013; int hv[200005]; int n,m; struct dat{ vector r,c; int h=0; }; vector > v; vector ord1[200005]; vector ord2[200005]; bool has1[200005]; bool has2[200005]; dat get_equiv(vector R,vector C,int X,int Y){ for (auto it:R) has1[it]=false; for (auto it:C) has2[it]=false; has1[X]=true; has2[Y]=true; vector r={X},c={Y}; int idx1=0,idx2=0; bool flag=true; while (idx1v[x][j]; }); rep(y,0,m) sort(all(ord2[y]),[y](int i,int j){ return v[i][y]>v[j][y]; }); vector vis1(n,false); vector vis2(m,false); // rep(x,0,n){ // rep(y,0,m) cout< R,C; int H=0; rep(x,0,n) rep(y,0,m) if (v[x][y] && !vis1[x]){ vector stk; vis1[x]=true; stk.pub({0,x}); vis2[y]=true; stk.pub({1,y}); vector r,c; while (!stk.empty()){ int a,b; tie(a,b)=stk.back(); stk.pob(); if (a==0){ r.pub(b); rep(y,0,m) if (v[b][y] && !vis2[y]){ vis2[y]=true; stk.pub({1,y}); } } else{ c.pub(b); rep(x,0,n) if (v[x][b] && !vis1[x]){ vis1[x]=true; stk.pub({0,x}); } } } int mx=0; for (auto it1:r) for (auto it2:c) mx=max(mx,v[it1][it2]); vector res; for (auto it1:r) for (auto it2:c) if (v[it1][it2]==mx){ res.pub(get_equiv(r,c,it1,it2)); } for (auto &it:res) if (res[0].h generate_moves(vector v){ vector pos(sz(v)); rep(x,0,sz(v)) pos[v[x]]=x; vector res; rep(x,0,sz(pos)) if (pos[x]!=x){ res.pub({x,pos[x]}); int temp=v[x]; swap(v[x],v[pos[x]]); swap(pos[temp],pos[x]); } return res; } signed main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin.exceptions(ios::badbit | ios::failbit); rep(x,0,200005) hv[x]=rng()%MOD; cin>>n>>m; vector > a(n,vector(m)); vector > b(n,vector(m)); rep(x,0,n) rep(y,0,m) cin>>a[x][y]; rep(x,0,n) rep(y,0,m) cin>>b[x][y]; v=a; dat res1=solve(); v=b; dat res2=solve(); if (res1.h!=res2.h){ cout<<"-1"< v; vector ans; v=generate_moves(res1.r); reverse(all(v)); for (auto [a,b]:v) ans.pub({1,a,b}); v=generate_moves(res1.c); reverse(all(v)); for (auto [a,b]:v) ans.pub({2,a,b}); v=generate_moves(res2.r); for (auto [a,b]:v) ans.pub({1,a,b}); v=generate_moves(res2.c); for (auto [a,b]:v) ans.pub({2,a,b}); cout<
•  » » » 7 weeks ago, # ^ |   +2 My submission: 168607716I guess they added some tests after it was 140 ms, but it is still reasonably fast. $O(nm \min(n, m))$ too, no hashing, if you match one pair of vertices, there is at most one way to match their connected components, just run two parallel dfses.
•  » » 7 weeks ago, # ^ |   -25 even u get doubts?
•  » » 7 weeks ago, # ^ |   0 Added #pragma GCC optimize("O3") And it now passes in 1400ms
 » 7 weeks ago, # | ← Rev. 3 →   0 Thanks for the good question.
 » 7 weeks ago, # |   0 Why this solution of problem Div2.C get WA2 ?? I test it against thousands of random test cases but I didn't find the Wrong answer.
•  » » 7 weeks ago, # ^ |   0 No need to use deque and other data structures like this. Just think that given array is a permutation
•  » » » 7 weeks ago, # ^ |   0 Can you give me any test case make my code fail ?
•  » » 7 weeks ago, # ^ |   0 1 7 1 1 2 3 6 5 4 7 4 2 Expected : 0 Your output : 2
•  » » » 6 weeks ago, # ^ |   0 Thanks a lot.
 » 7 weeks ago, # |   0 I don't understand where my solution is going wrong for problem Div2. C.Submission : 168591816Solution : Let $cnt$ be the number of rounds before the $i$th player, $cnt = max(0, i - 2)$then, if $cnt \ge k$, then, the $i$th player cannot play. Otherwise, subtract $cnt$ from $k$, so, now we have the maximum number of rounds the $i$th player could win, $k' = k - cnt$. If the $a_{i} = n$, then, we win all remaining rounds, else, if the prefix has some $j$, such that $a_{j} > a_{i}$, then, $i$th player can never win, otherwise, the suffix must have some $j$ such that $a_{j} > a_{i}$, the maximum we can get is the next greater element, which yields an answer $1 + min(k - 1, j - i - 1)$.Please help me if I have made any wrong statement or I have misunderstood something.
•  » » 7 weeks ago, # ^ |   +3 if i=1,print 0+min(k,j-i-1)
•  » » » 7 weeks ago, # ^ | ← Rev. 2 →   0 Oh, I see where I am going wrong now. Thank you for pointing out that edge case.
 » 7 weeks ago, # | ← Rev. 2 →   +9 I think one reason why the author hasn't put tutorial out is that he is strengthening the tests of F. $O(nC \sqrt q)$ passes pretests. Amazing.edit: It's actually $O(qC \log \log C)$, which is still not the intended time complexity.
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   -6
•  » » 7 weeks ago, # ^ |   0 Fun fact: you can use bitsets to get a smaller total number of operations.
•  » » » 7 weeks ago, # ^ |   -6 Fun fact: It passes main test. Victory of adventurer, haha.
•  » » » » 7 weeks ago, # ^ |   0 ok maybe I misunderstood the meaning of 'adventurer', if 'the brave'?
•  » » 7 weeks ago, # ^ |   +8 I believe if you analyze my algorithm carefully, it is $O(q C log(log(C)))$, still too slow of course (somebody uphacked me), but closer to passing than you might think. I was aware that it could be too slow, but roughly quadratic for $10^5$ is worth a shot.
•  » » » 7 weeks ago, # ^ |   +20 Yes I know the analysis, but I wouldn't have a try because I trust the author would be responsible for the task. I admire your courage to write the code with little chance to pass, but I don't think any responsible author would make such a mistake.
•  » » » » 7 weeks ago, # ^ | ← Rev. 2 →   +10 When writing the code I thought my code had a better complexity than it actually has. 5 minutes before the end I saw that the complexity was actually pretty bad. I submitted anyway, because it is only a penalty of -50, and the reward is way higher.Edit: I thought you also got a -50 penalty when getting WA on a problem you didn't solve. Turns out I am wrong.
 » 7 weeks ago, # |   0 For Problem C in Div2, Can someone point out the mistake in the below logic. LogicCreated an array — For each index , stored the next highest no's indexFor each query,No of rounds missed = max(0, i-2)Reduce k with the missed rounds (k = k — No of rounds missed)Then, If k == 0 , print 0 Else If given index same as the index of highest no, print k Else If given index occurs after the index of highest no, print 0 Else, Find the no. of rounds between current index and the next highest number's index (highestNoIndexOnRight-i-1). Then, Print the minimum of k and the above value (i.e., min( highestNoIndexOnRight-i-1 , k)) (My submission — 168599929 — WA on Pretest 2)
•  » » 7 weeks ago, # ^ |   +1 what if k has become negative try to output max(0,Math.min( highestNoIndexOnRight-I-1 , K));
•  » » » 7 weeks ago, # ^ |   0 Thank you for the reply. Some test cases passed after this change. I was not expecting that value to go below 0. Still not convinced how it could be less than 0. Will check further.Looks like some other issue also exists (even after that change). Will check. Thank you.
 » 7 weeks ago, # |   +262
•  » » 7 weeks ago, # ^ |   +6 Dammn! An Indian rainboy!
•  » » 7 weeks ago, # ^ |   0 Chad...
 » 7 weeks ago, # |   -18 This score distribution sucks. I solved 3 problems, but got as much points as those who solved only 2, cuz of wrong submissions on B and C. If it was ICPC-ruled, I'd had penalty = infinity, but still would be higher cuz solved more problems...
 » 7 weeks ago, # |   0 if you store my WA on pretest2 in a 3 bit integer It overFlow :(
 » 7 weeks ago, # |   +8 How many participants are aware that, unlike Berland, Buryatia is not a fictional land? :)
 » 7 weeks ago, # |   0 C was nice one... applied maxtillnow and nextgreater still got WA
•  » » 7 weeks ago, # ^ |   0 Is it necessary to use monotonic stack in C?
•  » » » 7 weeks ago, # ^ |   0 i used it to calculate next greater element for each index
•  » » 7 weeks ago, # ^ |   0 me either, i just wanna know why it doesn't work and how to solve this problem.
 » 7 weeks ago, # |   +14 Hi,For anyone that solved Div1C/Div2F, how do you prove that checking all cycles of length $\frac{n}{p}$ for prime $p$ is sufficient? I was setting $p$ as all factors of $n$ instead, and spent most of the contest optimising something that wasn't even intended...Thanks!
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   +55 Imagine you have $\frac{n}{pq}$. This means you are collected $pq$ thing. Let's label them $1,2,\ldots,pq$ from left to right. If we used $\frac{n}{p}$ instead, we would collected $1,q+1,2q+1,\ldots$ or $2,q+2,2q+2,\ldots$ etc. etc. instead.The mean of the (mean of each smaller sequence) is equal to the mean of the original sequence. Therefore, at least one of the sequences has a mean that is greater than or equal to the original sequence.Another way to think about it is to think about why they banned jumping with a distance of $n$.
 » 7 weeks ago, # |   0 submission why does it give WA on test 2
•  » » 7 weeks ago, # ^ |   0 1 11 1 10 5 7 6 9 4 2 8 1 11 3 1 1 Ans->1 Your output->0
 » 7 weeks ago, # |   -22 好疲惫啊，有点乏力
•  » » 7 weeks ago, # ^ |   -8 居然还能打中文
 » 7 weeks ago, # |   +11 Test cases for C Div.2 were really weak, because O(n*q) will pass.
•  » » 7 weeks ago, # ^ |   0 In every query, you can take for from 0 to index of given number to check if there is bigger number than given.
 » 7 weeks ago, # |   -8 Descriptions are there to help participants understand, not to prevent them from understanding.
 » 7 weeks ago, # |   0 How to solve D1A2?
•  » » 7 weeks ago, # ^ |   0 Transform [l, r] into (r — l + 1) / 2 segment with length of 1 or 2 unit.
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   +6 An array of size $n$ can be cleared in time $n$ by simply applying the operation on each element one at a time, or by applying the operation on two elements at a time (first and second, then second and third, then third and fourth, etc), until one element remains for one more final operation. The nice thing about the time being exactly equal to the size (no additions or constant factors) is that the total time is unchanged even if we partition the array into any number of subarrays of any length and apply the procedure separately on each subarray.The only way to actually save time is if there is a subarray for which the XOR of its elements in equal to 0. Then when we apply the operation on two elements at a time, the last remaining element will be 0, so we don't need to perform the final operation. Thus, we save one time unit for each such disjoint subarray, irrespective of the locations or sizes of these time-saving subarrays.How do we find these time-saving subarrays? We can maintain an running XOR of the elements, and record each result. If our running XOR is $r$ before entering a time-saving subarray, then the result after we see the last element of this subarray is $r \oplus (\text{XOR of subarray}) = r \oplus 0 = r$. So when we see a residue again, then we know that we found a time-saving subarray. We don't care about when this subarray begins; only that it saves us one time unit. Our time-saving subarrays need to be disjoint though, so we need to reset $r$ after this. tl;dr — Declare a residue set and initialize the residue to 0. Read through the values, applying the XOR operation to our residue. If the result is not in our residue set, then insert it. Otherwise, increment a counter, clear the set, and reset the residue to 0, and continue. My submission: https://codeforces.com/contest/1719/submission/168615233
 » 7 weeks ago, # |   0 Check out my Div.2 C solution without queues, dequeues or vectors:https://codeforces.com/contest/1719/submission/168582562
 » 7 weeks ago, # |   0 Div2 C test cases could have been better tbh, you just covered 2 cases where a[i] == n (we win everytime after max(0, i — 1) games) and where i is higher than the position of n (answer is 0)
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   0 C like C was good problem, but test cases are too weak.
 » 7 weeks ago, # |   +2 Once you realise that A has to do with the parity of n and m, the kind authors have already provided the answers for all cases of odd and even in the samples. Thanks sirs!
 » 7 weeks ago, # |   0 Probably the easiest first 3 questions I ever encountered in a Div2 contest.
 » 7 weeks ago, # |   +19 Why this naive Mo's algorithm can pass system test of Div.1 F? I think simply place the primes one by one can hack it.https://codeforces.com/contest/1718/submission/168599096
•  » » 7 weeks ago, # ^ |   +36 Maybe the problem setters didn't think about such a dumb approach. So they didn't have good tests for it.
•  » » » 7 weeks ago, # ^ |   +9 seems like they haven't any good tests for whole set
 » 7 weeks ago, # |   +10 After 21 months of perseverance, I finally became an expert. After countless frustrated and frustrated nights, my hard work has paid off. I will keep trying to be a CM and never give up. Bless all those who struggle.
 » 7 weeks ago, # |   +21 For me, my solution for div1B is a total mystery. I have no idea how an apparent backtracking could pass in 233 ms. However, the problems were not very interesting and, combined with some overthinking it was catastrophical. Hope to see some better div1 A and B problems in the future:))
•  » » 7 weeks ago, # ^ |   0 Hello stranger!
•  » » » 7 weeks ago, # ^ |   0 Hello stranger!
 » 7 weeks ago, # |   +8 Ratings updated preliminarily. We will remove cheaters and update the ratings again soon!
 » 7 weeks ago, # | ← Rev. 2 →   +19 bad and strange tests in Div1Bduring contests I had submitted $O(k^2\log k)$ solution per test, it passed pretests in 800msI resubmitted faster version before end of contest paying 130 placesAfter systest original submit have passed tests in 1300 ms (!!!)I tried to hack it with exterimely stupid test and it was successful 168605608 generatormt19937 rnd(309935741); int tn = 1e4; cout << tn << endl; for(int i=0; i v; int x = 1e9; for(int i=0; i
•  » » 7 weeks ago, # ^ |   +29 I would argue that setting $t$ large with $n$ really small is just bad practice in general -- with such small values of $n$ it often happens that constant optimization matters more than complexity and as such it becomes really hard to intuit if your solution will pass in time or not.Adding a n<45 check to your code makes it pass reasonably comfortably for the stupid test, at least: 168630258
 » 7 weeks ago, # |   -10 Okay i think problem C should have had more points assigned to it compared to problem B. In my opinion problem B was easier, i got baited by the point values.
 » 7 weeks ago, # |   0 I spent a lot of time on Div2E thinking that there is max flow or min cost max flow solution but i did not figured out how to use it. Sad :(
 » 7 weeks ago, # |   0 i did c using a map and storing how many wins every number does till the biggest one, how did u guys do it? are there other ways which do not require such a tedious implmentation?
 » 7 weeks ago, # |   +15 Quick review for D1 ABC:A: Answer = n — (max # of disjoint intervals that has xor sum zero). A fair problem.B: First check if sum(a) is sum of Fib numbers. Then brute force where Fib(n), ..., Fib(0) comes from. I never know why backtracking runs so fast.C: For each divisor d of n s.t. $n/d$ is a prime, use a segtree/multiset to maintain $\max_{0\leq i < d}\sum_{k} a_{kd+i}$. There are at most 7 such d-s. Therefore, it won't TLE. Quite a standard problem.
 » 7 weeks ago, # |   0 can someone help me figure out what's wrong in my code for problem Div2-B and what is the possible test case it is failing. https://codeforces.com/contest/1719/submission/168580820
•  » » 7 weeks ago, # ^ |   0 Try n = 2 and k = 1
 » 7 weeks ago, # |   0 Question C was hard to implement
•  » » 7 weeks ago, # ^ |   0 solutions- ** A, B — https://youtu.be/YDywuWYuEK4** ** C — https://youtu.be/8kTiOcHczVA** **** ****
 » 7 weeks ago, # |   +5 d2E is among the worst problems I have ever seen on this platform
 » 7 weeks ago, # |   0 how to make a good cp template, i dont understand other template completely except few thimgs most of the part is unreadable to me. any suggestion in your mind? regards
 » 7 weeks ago, # |   0 solutions- ** A, B — https://youtu.be/YDywuWYuEK4**** C — https://youtu.be/8kTiOcHczVA** **** ****
 » 7 weeks ago, # |   0 can some1 gimme some tcs for this!!
•  » » 6 weeks ago, # ^ |   0 Take a look at Ticket 16042 from CF Stress for a counter example.
 » 7 weeks ago, # |   0 In problem A of Div2, please explain how Tonya wins in the testcase "2 2". I don't understand that.
•  » » 7 weeks ago, # ^ |   0 Burenka is at (1,1) so she can either go to (1,2) or (2,1). From both cases Tonya plays chip at (2,2) , since it is the corner, there isn't any more place to go for Burenka.
•  » » » 7 weeks ago, # ^ |   0 I didn't get it. Burenka starts at (1,1), then lets say she moves to (1, 2) after than its Tonya's turn. He starts at (1, 1) and lets say he moves to (2,1). Now Burenka's turn, she moves to (2, 2), which is the only possible cell. Now it's Tonya's turn but he can't go to any cell according to the conditions in the problem. Thus Burenka wins. Where am I wrong here?
•  » » » » 7 weeks ago, # ^ | ← Rev. 2 →   0 it seems like you misread the statement tonya will start from the index where burenka left and then burenka start from the index tonya will left and so on
•  » » » » 7 weeks ago, # ^ |   0 They are moving the chip , not moving themselves
•  » » » » » 7 weeks ago, # ^ |   0 Thank you for helping me. I misread the statement.
 » 7 weeks ago, # | ← Rev. 2 →   +5 A fun fact about Div2 A: the outcome does not depend on the players' moves.Hint. The parity of the Manhattan distance to the destination alternates between moves, and a move is always possible when that distance is odd.
 » 7 weeks ago, # |   0 i have tried out every single test case i feel like but i dont know where am i going wrong. can anyone pls look into it. https://codeforces.com/contest/1719/submission/168625241
•  » » 7 weeks ago, # ^ |   +19 Your code fails on:1 2 1 2 1 1 2 Correct output2 Your output3 How did I get this test?168630508 (Take a look at checker's comment for second pretest)
•  » » » 7 weeks ago, # ^ |   -11 thank you mate but its still wrong lol. can u pls check again for test case 2
 » 7 weeks ago, # |   +4 editorial?
 » 7 weeks ago, # |   +17 DIV2 （ABCDEF）video Editorial for Chinese ：Bilibili
 » 7 weeks ago, # |   0 When will we be expecting the tutorials? I struggled on question D1, could someone shed some light on the problem?
•  » » 7 weeks ago, # ^ | ← Rev. 8 →   +16 First, observe that there is no benefit to applying the operation on a range of more than 2 elements, since it doesn't save any time compared to applying the operation multiple times (on ranges of size 1 and 2 only).Applying the operation on one element at a time will cost $n$ time units. Applying the operation on two elements can guarantee zeroing one element, but we'd then need to include the other in the next operation. We can perform this kind of pairwise sequence of operations until one element remains, which we apply a final operation to. This also costs $n$ time units.How do we save time? If there is a subarray of $k$ elements such that XORing all elements results in 0, then we can perform the pairwise sequence of operations on this subarray. The one element that remains must be 0 after this, so we can skip the final operation and spend only $k - 1$ time. This generalization also includes the case of $k = 1$ (if an element is initially 0, we need 0 operations to zero it). DP solution (works for D1): For an array of $n$ elements, if there is a suffix of say $k$ elements whose XOR is 0, then we can apply the optimal solution (through DP) on the first $n - k$ elements and then start a XOR chain for the last $k$ elements. We would, however, need to try all values of $k$ to find which suffixes XOR to 0, and pick the one with least time. Even if the suffix does not XOR to 0, we need to store the result, so that we can quickly extend the chain to a new element (instead of recalculating the XOR chain). My approach defined $dp[i][j]$ as the result of the XOR being applied from index $i$ to index $j$: https://codeforces.com/contest/1719/submission/168605232This has $O(n^2)$ runtime, so it won't work in D2. A 1D table should work too (since it's only the different starting points we care about), but I didn't bother refining this further and it would still take $O(n^2)$ runtime. Counting solution (works in both D1 and D2): Actually simpler than DP, but you need the additional observation that the locations and sizes of the time-saving subarrays (where the elements in the subarray XOR to 0) are completely irrelevant. Each time-saving subarray saves one time unit regardless, so the optimal time is simply $n$ minus the maximum number of disjoint time-saving subarrays. We can detect a time-saving subarray by maintaining a running XOR and inserting the results in a set. If we receive the same result twice, i.e., $r \oplus a_i \oplus a_{i + 1} \oplus \cdots a_{i + k} = r$, then the subarray $[a_i, \ldots, a_{i + k}]$ XORs to 0 and saves time. We don't need to know when this subarray starts; we just need to detect when it ends, allowing us to increment our saving counter and reset the XOR chain. You can check out how simple it is here: https://codeforces.com/contest/1719/submission/168640804
•  » » » 6 weeks ago, # ^ |   0 LightBrand99, can you please explain What it actually means by " disjoint subarrays with XOR of 0 " . Actually a little bit confused in understanding that. For example on array :(in case you want to know) 1 3 2 1 2 3 1 ,I kind of got stuck on this.
•  » » » » 6 weeks ago, # ^ |   0 Note that $1 \oplus 2 \oplus 3 = 0$. So for the array $[1, 3, 2, 1, 2, 3, 1]$, the subarrays $[1, 3, 2]$ (first three elements), $[1, 2, 3]$ (fourth to sixth elements) and $[2, 3, 1]$ (last three elements) all satisfy the property that the XOR of the elements is 0. Let's denote this as a 0-XOR subarray.So for example, we can zero out the first three elements in two operations as follows: $[1, 3, 2, 1, 2, 3, 1] \to [1 \oplus 1, 3 \oplus 1, 2, 1, 2, 3, 1] = [0, 2, 2, 1, 2, 3, 1]$$[0, 2, 2, 1, 2, 3, 1] \to [0, 2 \oplus 2, 2 \oplus 2, 1, 2, 3, 1] = [0, 0, 0, 1, 2, 3, 1]$In general, if you have a 0-XOR subarray of $k$ elements, then this subarray can be zero'd out in $k - 1$ operations. So we can partition our original array as $[(1, 3, 2), (1, 2, 3), 1]$, where the brackets represent 0-XOR subarrays. So it takes two operations to zero out $(1, 3, 2)$, two operations to zero out $(1, 2, 3)$, and then there is a $1$ remaining that needs one operation (number of operations to zero out elements outside the 0-XOR subarrays is equal to the number of such elements), for a total of 5 operations.Alternatively, you could also partition the array as $[(1, 3, 2), 1, (2, 3, 1)]$, which also requires 5 operations. There are actually three 0-XOR subarrays in the original array, but two of them overlap, so we can only exploit at most two of them, hence the need to count the maximum number of disjoint 0-XOR subarrays. In any case, since we can have two disjoint 0-XOR subarrays from an array with seven elements, the output should be $7 - 2 = 5$, regardless of the size and location of these 0-XOR subarrays.
•  » » » » » 6 weeks ago, # ^ | ← Rev. 3 →   0 Thank you very much LightBrand99, for explaining so much in detail and taking out your time to reply to my comment. Thank you very much bro.
 » 7 weeks ago, # |   0 Can someone please tell me why a specialist won the div 2 round? Did the guy purposely create a new smurf account?
•  » » 7 weeks ago, # ^ |   +4 This is only their fifth contest, with their first contest being in July 31st, so it's very likely that they're simply new to Codeforces but are actually really skilled and experienced in CP (through numerous other mediums). So even though they start as grey, they would perform far above what's expected of their current rating, (getting a significant boost from each contest) until they reach the rating that more accurately reflects their skill level, at which point it would be more stable. While it's unfortunate that someone who might be Div 1 tier is rated in Div 2, the reality is that we won't know that they're Div 1 tier until they prove themselves through these very same contests that they would dominate in. If they really are Div 1 tier though, it shouldn't take long for them to reach a more accurate rating.
•  » » » 6 weeks ago, # ^ |   0 fifth? That's not true. It is only their second. Also, out of the top 5 in div 2, only one of them (TasselFlower in 3rd place) has actually competed in more than five contests. I don't see why so many people who are so good at competitive programming will only just be joining Codeforces given how big of a platform it is. It only makes sense for me to think that they either cheated (which I don't think so) or that they have created new accounts
•  » » » » 6 weeks ago, # ^ |   +3 Sorry, I mistook who you were referring to. I do think there are many outside Codeforces who are so good in competitive programming, due to the numerous other alternative mediums. In fact, I myself used to train through weekly offline contests at university, and I would prefer that over Codeforces if it was still an option for me now. I think the use of alt accounts to participate in contests below your actual level would still qualify as cheating, but in any case, I don't think there's any evidence that suggests that whether it's an alt, a cheater, or someone new to CF. But unless it's a cheater, they should quickly jump up to the appropriate rating and this should no longer be an issue.
 » 7 weeks ago, # | ← Rev. 3 →   +6 The recent contests are so wrong. There's a huge gap between C and D
•  » » 6 weeks ago, # ^ |   0 Not really. Look at LightBrand's solution of D1 and D2 above. It is quite simple apart from the fact that you have to make some key observations.
 » 7 weeks ago, # | ← Rev. 3 →   -28 I resubmitted my code of problem div1c several times after the contest, which has got a TLE(above 3000ms) on the system test, but it passed all the tests in below 2800ms each time ...(including system tests)I think the efficiency of the judging machine has fluctuates too much.submissions:TLE,during the contest: 168600537AC,after the contest: 168640013Is it possible to rejudge my submission?
•  » » 7 weeks ago, # ^ |   0
•  » » 6 weeks ago, # ^ |   0 Why are there so many downvotes :(
 » 7 weeks ago, # |   +5 Problem D1 and D2 is my favourite
•  » » 7 weeks ago, # ^ |   0 Because this problem helps me learn more about greedy
 » 7 weeks ago, # |   +42 When will the editorial be published?
 » 6 weeks ago, # |   0 I am a newbie,where can I find the tutorial of this contest?
•  » » 6 weeks ago, # ^ |   0 It usually appears in announcements, but it hasn't been published yet…
•  » » » 6 weeks ago, # ^ |   0 okey，thx bro!
 » 6 weeks ago, # |   +15 What does "Unexpected verdict" mean in hacks?
 » 6 weeks ago, # | ← Rev. 2 →   +37 Now I'm uphacking solutions of Div2E/Div1B and I used the data generated by: Code#include using namespace std; int f[104]; int main(){ cout<<10000<
•  » » 6 weeks ago, # ^ |   +23 When I set $T=1$ it shows "Unsuccessful Hacking Attempt" but why when $T=10000$ I receive "Unexpected Verdict"? So is it reasonable for me to doubt that the authors' code gets TLE on this test?
•  » » » 6 weeks ago, # ^ |   0 I think it's reasonable for you to suspect that the authors' code gets TLE'd on this test. I think hacks are judged by first validating that it satisfies input constraints, then running them on the authors' solution to generate the correct answer, before running them on the hack target's code. But if the authors' solution itself doesn't pass (due to TLE, MLE, or anything other than "Wrong Answer"), then it would make sense to consider this as an Unexpected Verdict. I don't know for sure whether this is the case here, but it does sound like the most plausible explanation (especially with how tight the limits are).
•  » » 6 weeks ago, # ^ |   -11 I don't think this affects the Unexpected Verdict, but your code contains an signed integer overflow, because the 50'th fibonacci number is too big to fit into an int.
•  » » » 6 weeks ago, # ^ |   +13 Oops, I just wrote a simplified version of my code in the comment so I didn't notice that, sorry. But my original code uses long long which gets the same result. Also I only used the first 43 fibonacci numbers (which is actually $\le 10^9$) so int is enough for them.
 » 6 weeks ago, # | ← Rev. 5 →   +10 UPD: I'm sorry I checked on other compilers and the answer seem to be correct.
•  » » 6 weeks ago, # ^ |   0 I tried both of these in the Custom Invocation (https://codeforces.com/contest/1719/customtest) and the correct answer seems to be printed in both cases. I think the issue is from the medium that you're trying these tests on. Are you sure you're using a C++20 compiler and not some older version?
•  » » » 6 weeks ago, # ^ |   0 I'm using c++21. Thank you for correcting me though
•  » » 6 weeks ago, # ^ |   0 Randboys code outputs 4 on both of your test on my laptop...
 » 6 weeks ago, # |   0 Can anybody help me find a testcase for Div.2 C where my code(168707975) fails? I tried to use all the ones posted here and they seem to work. I've simulated n-1 fights till the n comes to the first position, storing indices where a number wins and loses.
•  » » 6 weeks ago, # ^ |   0 1 5 1 1 2 3 4 5 2 2 Expected : 1Your output : 0
•  » » » 6 weeks ago, # ^ |   0 Thanks a lot. It got accepted. orz
 » 6 weeks ago, # |   0 Hi, I got a message from the system saying that my solution is similar to that of another user. However, this is because we both use the same template which can be found at https://github.com/JaroPaska/competitive_cpp_17 and was published before the competition.
 » 6 weeks ago, # |   0 Can you give me a thumbs up
 » 6 weeks ago, # |   0 A good round
 » 6 weeks ago, # |   0 I just got a message about violating the rules as my submission (https://codeforces.com/contest/1719/submission/168578470) is apparently too similar to (https://codeforces.com/contest/1719/submission/168549952) [written by my friend during the contest]. The thing is that I know I have not seen his code at all during the contest and my solution is my own (I also believe that it's very different but I'll let you be the judge). However, I am using the same template as my friend I was supposed to copy from. He allowed me to use his template (it was published before the contest and can be found here: https://github.com/JaroPaska/competitive_cpp_17).
 » 6 weeks ago, # |   0 I got a message that my answers were copied from someone called sahil667788 which cannot be true as I haven't known this person or made contact with him ever in my life. I am open to clarify further but I request you to please give me my rating back.
 » 2 weeks ago, # |   0 Can anyone help me with Div2 BWhat would be the output for input n = 6 and k = 1`