Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

### triple__a's blog

By triple__a, history, 18 months ago,

Hello Codeforces!

I am glad to invite you to my first official round Codeforces Round #630 (Div. 2), which will take place on Mar/31/2020 16:35 (Moscow time) (please note for the unusual starting time) and will be rated for all Division 2 participants.

You will be given 7 tasks and 150 minutes to solve them.

All tasks in this round were prepared by me. Hope that you will enjoy those tasks!

I would like to thank:

To avoid queueforces, we will provide small amount but strong (hope so) pretests for first few tasks. Hope it works!

Score distribution will be announced later.

Good luck and have fun!

UPD1: Score distribution: 500-1000-1250-1250-1750-2250-3000

UPD2: Contest is over, and here is the editorial.

UPD3:

I am sorry that pretests were not as strong as I excepted.

Congratulations to the winners:

div1+div2:

div 2:

1. epii10

2. sorry_to_tourist

3. camilla

4. jerome_wei

5. [user: _dawn]

people who were first to solve each task:

B: hu_tao

C: okwedook

E: GsjzTle

G: GoGooLi

Lastly, thanks to Handsome2004 for the brilliant hack of E.

• +713

 » 18 months ago, # |   +7 Auto comment: topic has been updated by triple__a (previous revision, new revision, compare).
•  » » 18 months ago, # ^ |   -54 this round suddenly come there was april fool contest and after that div1+div2 after last div3. thanku for the contest. :)
 » 18 months ago, # | ← Rev. 2 →   0 Why isn't this blog on homepage? Edit: Nevermind it is now.
 » 18 months ago, # |   +43 Welcome everyone to join in $⩾w⩽$
•  » » 18 months ago, # ^ |   +5 What does it mean?
•  » » » 18 months ago, # ^ |   +19 maybe I should add a full stopWelcome everyone to join in. ⩾w⩽$⩾w⩽$ ← it's just a emoticons.
 » 18 months ago, # |   -17 hoping to get expert
 » 18 months ago, # |   +30 I really hope that this H̶o̶p̶e̶ ̶s̶o̶ works!
 » 18 months ago, # |   +46 Small but strong pretests yey no more queue thank you
•  » » 18 months ago, # ^ |   +110 t = 1e5 in the sample...
•  » » » 18 months ago, # ^ |   +3 That sounds cool but hard to copy :D
•  » » 18 months ago, # ^ |   +8 The number of participant is more and more large, it is another factor causing long queue, I think.
•  » » » 18 months ago, # ^ |   0 You're right
 » 18 months ago, # |   0 Long time no Chinese Round
•  » » 18 months ago, # ^ |   +3 corona
 » 18 months ago, # |   -60 Waited for Div.2 Round long time. :)
 » 18 months ago, # |   -7 I hope I can get a good score!
•  » » 18 months ago, # ^ | ← Rev. 2 →   -29 And so me :)
 » 18 months ago, # |   +3 Hope to see my username in blue after this contest. ^_^
•  » » 18 months ago, # ^ |   +2 Good luck
•  » » 18 months ago, # ^ |   +6 All the best :D
 » 18 months ago, # |   -26 The time is nice for Chinese :P
•  » » 18 months ago, # ^ |   +4 I see what you did there LOL
 » 18 months ago, # |   +180 I like queueforces. My code feels like schrodingers cat.
•  » » 18 months ago, # ^ |   +68 But you're a dog
 » 18 months ago, # | ← Rev. 2 →   +18 Thanks to all contest writers to make us busy during this lockdown situations. You are doing a great job. STAY SAFE STAY HOME
 » 18 months ago, # |   +28 Best line...To avoid queueforces, we will provide small amount but strong (hope so) pretests for first few tasks.
 » 18 months ago, # |   -11 I hope that this contest will increase my rating.
•  » » 18 months ago, # ^ | ← Rev. 2 →   +18 Name a person wants his/her rating to be decreased !! -_- -_-
•  » » » 18 months ago, # ^ |   +6 Maybe errorerror?
 » 18 months ago, # |   0 Why 150 minutes? Is it hard?
•  » » 18 months ago, # ^ |   +45 One of the reasons is there will be 7 problems, not 6 :)
 » 18 months ago, # |   +15 how to get started in this contest , can anyone help i am new here
•  » » 18 months ago, # ^ |   +8 go here and click Register Now on Codeforces Round #630 (Div. 2) and be online at the given time.
•  » » » 18 months ago, # ^ |   +3 thanks for the help @Jo3kerR
•  » » 18 months ago, # ^ |   0 Just go to contests section and you will find the contestYou can register in it
•  » » » 18 months ago, # ^ |   0 Already did earlier i didn't know where to start
•  » » » » 18 months ago, # ^ |   0 Didn't notice that someone replied :D
•  » » » » 18 months ago, # ^ |   0 the problems are (mostly) ordered in the order of difficulty. So start with A and then B,etc.. But if you are stuck for a long time and can't go anywhere in current question try out another. Also if you have an issue with how to workaround with the UI recommend checking youtube video, there are some which will explain it and also try out a virtual contest to get a practical understanding of it. Best of luck for the contest!!!
 » 18 months ago, # |   +125
 » 18 months ago, # |   -30 Just curious about the "useful" discussion Nanako and Nezzar took part in.
•  » » 18 months ago, # ^ |   +73 Test different kinds of strange solutions, help to structure test datas, give some advice about problems to make difficulty gaps reasonable and so on.My work range is not much more than a tester, but my workload is more. I keep communicating with triple__a about these since 2 months ago, and help for much more than 7 problems meanwhile (you know, some problems will be denied when preparing a round), instead of temporarily taking a virtual participation.Actually I also tried to give a Problem B when needed, but it was denied. :thinking:Don't want to tell much before the contest lol. wish you get a good result in this round.
•  » » » 18 months ago, # ^ | ← Rev. 2 →   -22 Hopefully I will :) (PS -Didn't knew about the amount of efforts you guys give while preparing contests. Thanks :) )
•  » » 18 months ago, # ^ |   +10 Generally testing & discussion of problems. Hope you enjoy the problems triple__a prepared!
 » 18 months ago, # | ← Rev. 2 →   -43 Due to Quarantine registration will exceed 20K for sure. Thanks codeforces for arranging contests, the only partner in this quarantine :)) #GOCORONA #STAYSAFE #HAPPYCODING.
 » 18 months ago, # | ← Rev. 3 →   -8 how rating of expert contestents change in last div 3 round? sorry, I didn't notice.they fixed this.
•  » » 18 months ago, # ^ |   0 it is andryusha_na_knopke magic
 » 18 months ago, # |   +27 I am glad to be the contributor to this round.But due to my weak ability I can't test hard problems :-(Wish you guys like this round of Div2!
•  » » 18 months ago, # ^ |   +3 How to test problems. How can i learn that. Thanks.
•  » » 18 months ago, # ^ |   +3 I hope one day you'll be able to host your own contest :)
 » 18 months ago, # |   -11 7 Problems !!Is it Subtask-forces ?
•  » » 18 months ago, # ^ |   +113 no
 » 18 months ago, # |   +5 150 minutes...oh yeah!!...I got no work to do in this quarantine anyway.
 » 18 months ago, # |   +30
 » 18 months ago, # |   +7 Nice rating graph triple__a
 » 18 months ago, # |   0 I receive the message from admin and surprised The allowed programming languages are C/C++, Pascal, Perl, Java, C#, Python (2 and 3), Ruby, PHP, Haskell, Scala, OCaml, D, Go, JavaScript and Kotlin. Is Rust banned? I can't see the name on the list.Below is the one from the last educational and surely see Rust before Kotlin. The allowed programming languages are C/C++, Pascal, Java, C#, Python, Ruby, Perl, PHP, Haskell, Scala, OCaml, Go, D, JavaScript, Rust and Kotlin.
 » 18 months ago, # |   +24 I need triple(+7) to become Candidate .. I hope i will earn them !
•  » » 18 months ago, # ^ |   +7 good luck!
 » 18 months ago, # | ← Rev. 2 →   0 Good luck everyone, have fun. ~.~
 » 18 months ago, # |   +14 ****I'm really honored to take part in this test**** ****Good luck everyone!****
 » 18 months ago, # |   +3 Thanks all of the members of this contest to prepare another good contest hopefully
 » 18 months ago, # |   +5 First time participating in a live contest. Y'all got any pointers ?
 » 18 months ago, # |   -23 Alas! I can't solve solve problem B/C. I just can solve problem A.
•  » » 18 months ago, # ^ |   +44 I don’t remember asking
•  » » » 18 months ago, # ^ |   +12 rekt
 » 18 months ago, # |   +15 Corona has definitely increased the participation in the recent contests. Thank you MikeMirzayanov for providing a great platform and, Thanks to problem setters too, for providing set of some amazing problems.
•  » » 18 months ago, # ^ | ← Rev. 2 →   +10 Corona China :)
 » 18 months ago, # |   0 Auto comment: topic has been updated by triple__a (previous revision, new revision, compare).
 » 18 months ago, # |   0 Auto comment: topic has been updated by triple__a (previous revision, new revision, compare).
 » 18 months ago, # | ← Rev. 2 →   +56 B worth 1000 and D worth 1250 points? Quite weird, I think you could have saved one problem (C or D) for a future contest.
•  » » 18 months ago, # ^ |   0 Maybe C and D are subtasks? Who knows ))
•  » » » 18 months ago, # ^ |   +11 The author said that there are no subtasks
•  » » » » 18 months ago, # ^ |   0 My bad. Perhaps it is because of the fact that all the tasks are made of the same author, so it would be better to gather them together. Wish we will experience a great round with full of new challenging problems!
 » 18 months ago, # |   +7 Best of luck guys !!!
 » 18 months ago, # |   -28 My request to admin to conduct more contests while this lockdown period. Thanks
•  » » 18 months ago, # ^ |   +33 They need time to prepare good quality rounds. Holding more rounds will definitely affect their quality.
•  » » » 18 months ago, # ^ | ← Rev. 2 →   +3 Yeah, But by taking help of good programmer may help to conduct. Code forces is known for its good quality rounds. Yeah.Quality of rounds should not be compromised. :)
 » 18 months ago, # |   +13 After seeing the score for question c and d. Excited to see which one will be easy one.
•  » » 18 months ago, # ^ | ← Rev. 2 →   -14 T
 » 18 months ago, # |   0 Guess, Which one will get more accepted, C or D?
•  » » 18 months ago, # ^ |   +1 I think, A will get the most
•  » » 18 months ago, # ^ |   0 it depends if there will be sub task then obviously c will get more accepted. other than that let us in 1 hour.
•  » » 18 months ago, # ^ |   0 C
 » 18 months ago, # |   -9 We need more such contests in this quarantine period. Another Reason to stay at home.
 » 18 months ago, # | ← Rev. 2 →   +11 .
 » 18 months ago, # |   0 HackForces?
•  » » 18 months ago, # ^ |   0 SubtaskForces
 » 18 months ago, # | ← Rev. 2 →   0 i smell a C1, C2 task
 » 18 months ago, # |   +9 Small number of pretests is somehow already making me feel uncomfortable, I just hope it works well. BTW, I am curious how hard it is for Codeforces to scale to the increasing number of users, I think registrations are about thrice the amount I used to see in last year, so can't just CF add some more processors(so that now they get 3x processors) or get something like thread ripper to judge systems so that queues are gone. I expect the number of submissions to be linear to the number of participants.
 » 18 months ago, # |   +5 More than 20k people! this will be fun!! :D
•  » » 18 months ago, # ^ | ← Rev. 3 →   0 Fun by waiting for the problem to get judged (long queue) ?
 » 18 months ago, # |   +2 Quick Check:- This is first contest designed by triple__a
 » 18 months ago, # |   +3 WOOOOO I am very expect to join the contest,hope for a good game experience and everybody will get good rating improving o-o
 » 18 months ago, # |   0 Huge participation indicates more people performing home quarantine.
 » 18 months ago, # | ← Rev. 2 →   +8 CF gonna fall down
 » 18 months ago, # |   +27 problems are so fricking complicated I dont mean it is hard it is complicated fricking contest
 » 18 months ago, # |   -10 Really ? div2 ?
 » 18 months ago, # |   +54 I guess it's just my taste but A was quite disgusting
•  » » 18 months ago, # ^ |   +6 Both A and B made me extremely uncomfortable:(
 » 18 months ago, # |   -84 stop setting problems.
•  » » 18 months ago, # ^ |   +19 stop complaining. The service provided here is free, you are not paying anyone and why does it matter to unrated acc.
 » 18 months ago, # |   -27 let's make a round which is neither queueforces nor readforces next time!
 » 18 months ago, # | ← Rev. 2 →   -27 The comment removed because of Codeforces rules violation
•  » » 18 months ago, # ^ |   +27 Now I'm curious what this comment was
 » 18 months ago, # |   +7 Quality with Difficulty
 » 18 months ago, # |   +4 Really all problem are look like more tougher than usual contest
•  » » 18 months ago, # ^ |   0 And actually from c its like hardness level >>> for people like me
 » 18 months ago, # |   0 I felt the questions were kinda lengthy, not complicated, just lengthy.
 » 18 months ago, # |   +15 I feel like 2:30H is too much for a cf contest.
•  » » 18 months ago, # ^ | ← Rev. 3 →   -49 fuch triple__a[user:triple__a] worst contest ever. dumbfuck dont know how to set problems
•  » » » 18 months ago, # ^ |   +26 Stop insulting people just because you were not able to solve the problems.
 » 18 months ago, # |   -9 Chinese Round is too hard for me.
 » 18 months ago, # |   0 I am glad that at today's round there were no queues and exits from the profile, thank you very much!
 » 18 months ago, # |   +5 Praying God for not failing in system test.
 » 18 months ago, # |   +40
•  » » 18 months ago, # ^ |   +12 I mean, that's literally the score distribution
 » 18 months ago, # |   +14 For everyone that had WA#3 on E: Every board is valid for odd N and odd M... Took me more than an hour to notice it :D
•  » » 18 months ago, # ^ |   +21 It's also the first test on which not changing mod from 1e9 + 7 fails :P
•  » » 18 months ago, # ^ |   0 Exactly the same problem. Fortunately noticed it in the last 5 minutes, and only needed 1 line change in code to solve it :D
 » 18 months ago, # |   +8 How to solve G?
 » 18 months ago, # |   +8 Video tutorial for problem DHope you enjoy it!
•  » » 18 months ago, # ^ |   0 Could you explain how you approached C
•  » » » 18 months ago, # ^ |   +3 You can observe that the string which is the period has to be palindromic as wellJust greedily choose the maximal frequency of each letter and drop from n the sum of maximal frequences
•  » » 18 months ago, # ^ | ← Rev. 2 →   0 What is the minimum size of the matrix which could be formed in que D?
•  » » » 18 months ago, # ^ |   0 You need at least two lines to make some variation(for n = 1 the DP algorithm is optimal)You also need at least two columns to generate the variation, but we need one more column to actually translate the new result, so 2x3 is min size(or 3x2, it's the same thing)
 » 18 months ago, # |   +25 I don't know how it was for you guys, but for me it was a hard round. :\
•  » » 18 months ago, # ^ |   +4 So hard :с
•  » » » 18 months ago, # ^ |   0 I am excited to see the editorial now :D
•  » » » 18 months ago, # ^ |   0 It is true that the problems were hard to comprehend at first. But I think it's only A and B that hindered the progress of most participants. While the problem A was quite obnoxious, B was not as bad. I personally think they should have swapped B and C.
 » 18 months ago, # |   +46 Hardest ever A .
•  » » 18 months ago, # ^ |   +1 I think D was hard. It made me really sit and think.
•  » » » 18 months ago, # ^ |   -29 D was really Trivial.But it took me an hour because I was thinking in the wrong side
•  » » » » 18 months ago, # ^ |   +17 D is trivial then and only then you already know, how to solve it
•  » » » » » 18 months ago, # ^ |   0 Lmao the example case literally gave you the working grid. If it weren't for the example case it would've taken me much longer.
•  » » 18 months ago, # ^ |   +1 I solved B & C but not A. actually it seems so lengthy for me I didn't wanted to give time for this. :(
•  » » » 18 months ago, # ^ |   0 What is your approach for solving B?
•  » » » » 18 months ago, # ^ | ← Rev. 2 →   +1 B was easy I just generated all primes within 1000. and for each prime p (from least >=2) I traverse the array and i checked if(arr[i]%p==0) I assigned same color to these because gcd will be >=2. and you can see you can't have composite number n<=1000 such that n= pi*pj & pi,pj both > 11st prime
•  » » » » » 18 months ago, # ^ |   0 Ahh, thanks!
 » 18 months ago, # |   +80 When you realize B solution only need first 11 primes
•  » » 18 months ago, # ^ |   -33 1 2 137 137 u may get wrong answer
•  » » » 18 months ago, # ^ |   +18 2 & 137 are not composite no.
 » 18 months ago, # |   +41 E is one of the most elegant problems I've seen so far :o
•  » » 18 months ago, # ^ |   0 Can you tell your thought process for it?
•  » » » 18 months ago, # ^ | ← Rev. 2 →   +30 First, note that you can replace all numbers with their values mod 2. Indeed, take m = max(a_ij), and then add 2 to each cell until they become either m or m + 1. The parity will not change. Then the first operation in the statement is useless, and the second one is simply inversion mod 2 (0 -> 1, 1 -> 0). In fact you can swap numbers in adjacent cells. This means you can move 1's arbitrary around the board. Also, if you have two 1's in adjacent cells, you can turn them into 0's by adding 1 to each.So the problem reduces to the following: you have nxm board with 0's everywhere apart from the corner cell, where it stands 1 or 0 (depending on the parity of the initial sum in all cells). Then 2 cases: 1) n*m is oddIf all numbers are zeroes, the problem is solvable. If there is one 1, it is easy to show you can fill the entire board with 1's (it is like filling the board with odd sides and 1 corner cell removed, with dominoes). So in this case every input is doable. 2) n*m is evenIf initial sum of all numbers is odd, the problem cannot be solved (because final sum must be even — it is n*m*final_number), as every time you add 2 cubes. Otherwise the initial board is all zeroes.So the answer is the following: if n*m is odd, it is always possible with any a_ij. If n*m is even, it is possible if the sum of all a_ij is even. Now, let's solve the problem :) 1) n*m is oddAll inputs are fine. How many inputs can be there? Each of n*m numbers can be from L to R, so the answer is $(R-L+1)^{nm}$. 2) n*m is evenOnly inputs with even sum of a_ij are fine. How many of those are there? First, let's select which positions on the board will be odd ($C_{nm}^{i}$, there can be i = 0, 2, 4,...,n*m odd numbers to make sum even). When we chose positions, each position is restricted to either odd or even numbers, according to the selection. Let's say we have $a$ even and $b$ odd numbers in the segment $[L, R]$. Then the answer will be: $\sum_{i=0}^{i=nm/2} C_{nm}^{2i}\cdot a^{2i} \cdot b^{nm - 2i}$. Wow! Fortunately, you can realize that these are the parts of an explicit equation $(a+b)^{nm}$, only terms with even powers. We know how to converge this will all terms, but how do you split into odd and even powers? The trick is to use -b instead of b: even-power terms will stay the same, and odd-power terms will change their sign. This makes it an elegant formula: $\sum_{i=0}^{i=nm/2} C_{nm}^{2i}\cdot a^{2i} \cdot b^{nm - 2i} = \frac{1}{2}\left((a+b)^{nm} + (a-b)^{nm}\right)$Just then remember that $a+b = R - L + 1$, and $a-b = \pm 1$ if $R = L (\mod 2)$ and 0 otherwise.All what is left is to calculate n*m powers — this you can do by fast power calculation, and fact that $x^{nm} = ({x^n})^m$.
•  » » » » 18 months ago, # ^ |   0 Shouldn't it be ((a+b)^nm + (a-b)^nm)/2 ?
•  » » » » » 18 months ago, # ^ |   0 Thanks, corrected.
 » 18 months ago, # |   +19 Can someone please help, how to calculate the number of correct boards in E when n * m is even.
•  » » 18 months ago, # ^ |   -10 if (r-l) is odd $\frac{(r-l+1)^{nm}}{2}$else $\frac{(r-l+1)^{nm}}{2}+1$
•  » » » 18 months ago, # ^ |   +3 How did you get that formula?
•  » » » » 18 months ago, # ^ |   0 In odd case, it is number of all possible grids. In even case, it is same but divided by 2, because we only need ones whose sum of initial heights is even
•  » » » 18 months ago, # ^ |   +1 It should be $\frac{(r-l+1)^{nm}+1}{2}$ instead of $\frac{(r-l+1)^{nm}}{2}+1$
•  » » » » 18 months ago, # ^ |   0 Can you tell how you get the formula in brief ?
•  » » » » » 18 months ago, # ^ | ← Rev. 2 →   +1 If $nm$ is odd, all grids are valid. One way to prove it is coloring the grid with a checkerboard pattern (let's assume that the cell in the upper left corner is black) and noticing that you can fill the grid with $\frac{nm+1}{2}$ dominoes of size $2 \times 1$ in such a way that each cell is covered and a white cell is covered twice. Using the operation 1, you can increase the value of any white cell by 2 and the value of the other cells by 1 (let's call it operation 3). So, a possible strategy to win is to make the height of all black cells the same, and then use the operation 3 to fix the height of the white cells. On the other hand, if $nm$ is even you can win if and only if the parity of the sums of the heights in the white and in the black cells is the same. First, let's calculate in how many ways you can fill k cells with numbers in the range $[l, r]$ and even/odd sum ($dp_{even}[k], dp_{odd}[k]$). You can get these values by the following relations: $dp_{even}[k] = dp_{even}[k - 1] * dp_{even}[1] + dp_{odd}[k - 1] * dp_{odd}[1]$ $dp_{odd}[k] = dp_{even}[k - 1] * dp_{odd}[1] + dp_{odd}[k - 1] * dp_{even}[1]$ The relations can be obtained by fixing the parity of the sum of the first $k - 1$ cells. If $r - l$ is even, there are $\frac{r - l}{2}$ even numbers and $\frac{r - l}{2}$ odd numbers in the range, so $dp_{even}[1] = dp_{odd}[1]$ and $dp_{even}[k] = dp_{odd}[k] = \frac{(r - l + 1)^k}{2}$. Then let's fill all the grid ($\frac{nm}{2}$ white cells and $\frac{nm}{2}$ black cells). The result is $dp_{even}[\frac{nm}{2}] * dp_{even}[\frac{nm}{2}] + dp_{odd}[\frac{nm}{2}] * dp_{odd}[\frac{nm}{2}] = \frac{(r - l + 1)^{nm}}{2}$. If $r - l$ is odd, you can prove by induction that $dp_{even}[k] - dp_{odd}[k] = \pm 1$. Using some algebra, you can get the result $\frac{(r - l + 1)^{nm} + 1}{2}$.
•  » » » » » » 18 months ago, # ^ |   0 Thanks.
 » 18 months ago, # |   -8 Very difficult for a beginner like me.
 » 18 months ago, # |   +4 this is my first time to take part in a real contest. But... I couldn't solve a single task lol
 » 18 months ago, # |   +11 Loved D ques.It was really trivial if you know the basics of BitWise Operations.
 » 18 months ago, # |   +22
 » 18 months ago, # |   0 for E, the idea I had in mind was the total count of odd numbers in the grid must be even, then with finite no of moves we can get all numbers with same parity. can someone say where this is going wrong?
•  » » 18 months ago, # ^ |   0 If n*m is even, you can do this always, your argument holds for odd n*m
•  » » » 18 months ago, # ^ |   0 oh snap! got it
 » 18 months ago, # |   0 Please share soln of B !!!!
•  » » 18 months ago, # ^ | ← Rev. 3 →   +3 Hint : all number given as input must have a prime factor in 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 because if all factors are above 31 then number will go beyond 1000 .
•  » » 18 months ago, # ^ |   0 The concept is based on Sieve of Eratosthenes, that is crossing out multiples of each prime number, and while crossing out multiples of primes, mark them with colours. p, p*2, p*3, ... , p*n (You can see gcd will be at least p-prime number.) And, according to constraints given you can just colour all the numbers with the first 11 prime numbers.Submission
•  » » » 18 months ago, # ^ |   -17 1 2 137 137 wrong answer right ?? shan't it be 137 yr answer is 0
•  » » » 18 months ago, # ^ |   0 sieve is not really needed here just make a set of smallest prime divisor of all numbers it will(number of sets) be less than equal to 11.
•  » » » 18 months ago, # ^ |   0 I did the same, got wrong answer somehow. Seems correct to me (Works on the testcases given)https://codeforces.com/contest/1332/submission/74968519
•  » » » » 18 months ago, # ^ |   0 Your output is not correct. It outputs a total number of 10, which means you can only use color from 1 to 10. Your solution actually uses color 11, but not 9. You are missing one step here, iterate over your color array and do a mapping to make each color used within the range of [1, total unique color count].
•  » » » » » 18 months ago, # ^ |   0 Thanks a lot! Understood now.
•  » » 18 months ago, # ^ |   0 Since they said Answer will always exist, simply brute over all multiples of numbers from 2 to 1000 present in array which are univisited and assign them color.
 » 18 months ago, # |   +15 Shortest solution to a D problem ever. Loved the simplicity ;)
•  » » 18 months ago, # ^ | ← Rev. 2 →   -9 .
 » 18 months ago, # | ← Rev. 2 →   +3 I'm failed at D at the last minute because number larger rr than >300000 if only i had read the checker logs :(
 » 18 months ago, # |   +41 -what if we use 100% of the brain?=write a hard contest so many participants will hardly solve A and dont solve any other questions and leave the contest so the traffic on the server wont be huge like the last contests
•  » » 18 months ago, # ^ |   0 lmao :5head:
•  » » 18 months ago, # ^ |   0 lol MikeMirzayanov restrin such people from setting problems. dont be like codechef. this was the worst contest ever,
 » 18 months ago, # |   +11 D sample test itself is a gigantic hint.
•  » » 18 months ago, # ^ |   0 That is very true!Guess what xD? I copied the second sample output and modified it a little bit and done, accepted!
 » 18 months ago, # | ← Rev. 2 →   +5 For G i did this following observations:1. It's obvious that answer is 3 or 42. Let's suppose we have answer with 4 elements and the indexes are i1,i2,i3,i4. if there exists a solution, that means that there is a solution where i1 and i2 are adjacent indexes + i3 and i4 are adjacent indexes too.3. So from point 2 , we conclude that we need to find i1 & i3 indexes, such that a[i1]>a[i1+1], a[i3]>a[i3+1] , a[i3]>a[i1] and a[i3+1]>a[i1+1] (or vice versa for a[i1]
•  » » 18 months ago, # ^ | ← Rev. 2 →   0 Ignore me, I was wrong, sorry :)
•  » » » 18 months ago, # ^ |   0 but 1,2,3,4 is the answer there.
•  » » 18 months ago, # ^ | ← Rev. 3 →   0 Consider this case:5 12 3 1 3 21 5
 » 18 months ago, # |   +13 This Div2 was having more puzzle problems, I guess!
 » 18 months ago, # |   +11 A,B,C Indexfiddlingforces.However given that lengthy statements it was still fun to participate. For me B was much harder than C. Felt like being testet on how much index-one-off-errors can one avoid.
 » 18 months ago, # |   +6 Me RN
 » 18 months ago, # |   +13 First of all kudos and thanks to codeforces for handling high participation so nicely.
 » 18 months ago, # |   0 Thanks for the contest. Wish problem-setters have good days <3 By the way, how to solve E guys ? :(
 » 18 months ago, # | ← Rev. 2 →   0 Can anyone help me , what i am missing in my logic for question C (k- string)??Logic : I deduced condition that all of given condition will be satisfied if we try to make an string of length K which is a palidrome. and replace it in all n position (i%k th place).So first , i stored max count of the variable occuring at a position i(1<=i<=k) ; i stored and made a char array for so(max var);then afterwards in order to make those k char a palidrome ,i checked from both side to find the optimal character for each pos,at last i ran loop on string and counted the number of pos (pos%k) ,i need to change ,in order to make it combination of k legth optimal string. Codecin>>t; while(t--) { ll ans=0; ll n,k; cin>>n>>k; string s; cin>>s; for(ll i=n-1;i>=0;i--) { s[i+1]=s[i]; } //can make k changes ll M[2001][28]; ll Mx[2001]; char S[2001]; memset(M,0,sizeof(M)); memset(Mx,0,sizeof(Mx)); ll px=(ll)'a'; //wudixiaoxingxingheclp for(ll i=1;i<=n;i++) { ll pp=i%k; if(pp==0) { pp=k; } ll z=(ll)s[i]; z=z-px+1; M[pp][z]++; if(M[pp][z]>Mx[pp]) { S[pp]=s[i]; Mx[pp]=M[pp][z]; } } ll p1=1; ll p2=k; while(p1 M[p2][cy]) { S[p2]=S[p1]; } else { S[p1]=S[p2]; } p1++; p2--; } for(ll i=1;i<=n;i++) { ll j=i%k; if(j==0) { j=k; } if(s[i]!=S[j]) { ans++; } } cout<
•  » » 18 months ago, # ^ |   0 One way to solve it to group positions which must have same characters to satisfy the rules. Then, foreach such group contribute $ans+=countPositions-maxFreqInGroup$ of that group.
•  » » » 18 months ago, # ^ |   0 But how this formula is going to ensure that resulting string will be a Palidrome??
•  » » » » 18 months ago, # ^ |   0 You need to choose the groups of positions right.That is, every segment of k chars must be a palindrome, too. So within each segment of k chars is is that $s[i]==s[k-1-i]$ and all segments are equal. So there are $(k+1)/2$ groups of positions.We need to find the min count of operations to make all chars of one group same, for all groups. If they are same, the whole string is a palindrome.
•  » » 18 months ago, # ^ | ← Rev. 3 →   +4 I also had this problem in my code. But I corrected it after realizing that we have to consider both positions period and palindromic as they all should have same characters.As you are considering all characters frequency which are at at pos = i % k and you are selecting max from that for pos = i % k.But you also have to consider k - pos - 1 characters for pos = i % k.Reason is we have to consider frequency of all characters which can come at pos = i % k and they can be due to period positions and due to palindromic positions.My Submission 75017302
•  » » » 18 months ago, # ^ |   0 Why so many downvotes have I written the wrong logic? PLease correct me then.
 » 18 months ago, # |   +4 Am I the only one who did problem C. using a simple DFS with connected components? Felt like an overkill...
•  » » 18 months ago, # ^ |   0 Wait DFS how?
•  » » » 18 months ago, # ^ |   +1 Build a graph as follows: — each node represents a position in the array — an edge (u,v) exists if and only if u and v must have the same letterYou can build the edges from the palindromic and period conditions.Then, all the vertices in a connected component must have the same letter. And in order to be optimal, we choose the letter that is the most frequent in that component. Then we repeat this for all components. Connected components are usually handled with a DFS.
•  » » 18 months ago, # ^ |   0 I did that too. I knew there would be an easier way but I just went with the connected components approach and it took me a lot of time.
•  » » » 18 months ago, # ^ |   0 Can you briefly illustrate your approach?
•  » » » » 18 months ago, # ^ | ← Rev. 2 →   +1 lets take that example: 6 2 abaabatransform it into: 121212 To make it palindrome, the last number and the first number must be the same. You will connect all the components together and use DFS to know which one belongs to which and then get the most repetitive character from all the numbered ones and then subtract it by the total characters that you counted in the set. It is like DSU but DFS is easier and faster to implement than DSU. It is clearly shown in that example that 1 and 2 are connected. So all characters must be the same. But that example:6 3 abaabaTransformation: 123123It is clearly shown that 1 and 3 components are connected. But 2 is not connected. So all 1's and 3's characters' must be the same. But 2 is independent.
•  » » 18 months ago, # ^ |   0 I did it as well
•  » » 18 months ago, # ^ | ← Rev. 2 →   0 I solved C using DSU (managing connected components). It was the first (and only) approach that came to my mind. I thought it will be the most intuitive approach (for others as well).Here's my solution: https://codeforces.com/contest/1332/submission/74985309.
 » 18 months ago, # | ← Rev. 3 →   0 Solution for E: Let total odd numbers in the range be odd, and total even numbers in the range be even. Let tot=n*mIf tot is odd, then answer is power(even+odd,tot). else the answer is (power(even-odd,tot)+power(even+odd,tot))/2IS THIS APPROACH CORRECT?
•  » » 18 months ago, # ^ | ← Rev. 2 →   0 The second formula should just be (power(even+odd,tot)+1)/2. EDIT: Nevermind, I think this is equivalent to what you said, you are correct.
 » 18 months ago, # |   0 What's testcase 3 in problem A?
 » 18 months ago, # |   0 Auto comment: topic has been updated by triple__a (previous revision, new revision, compare).
 » 18 months ago, # |   0 B has taken much time because I cannot understand the meaning of the range of $m$ at first.
 » 18 months ago, # |   0 Why Bob is incorrect in question D, i think his algo is correct for maximum??
•  » » 18 months ago, # ^ | ← Rev. 2 →   0 3 37 4 73 7 77 7 3Answer should be 3, but Bob's algorithm gives 0
»
18 months ago, # |
-75

MikeMirzayanov

My Code is giving right answer for the given test cases of problem -c while running in IDE geeksforgeeks and ide codechef Then I submit it on codeforces..bt it gives wa for the 3rd case of given pretest..It's really frustrating!! Please check once my code..tell why this is happening

# include<bits/stdc++.h>

using namespace std;

# define pl pair<ll,ll>

int main() { ll t; cin>>t; while(t--) { ll n,k,i,mx,tot=0,j,f; cin>>n>>k; ll fr[27]={0}; string s; cin>>s; for(i=0;i<k/2;i++) { for(j=0;j<26;j++) fr[j]=0; f=0; for(j=i;j<n;j=j+k) { fr[s[j+k-1]-'a']++;

fr[s[j]-'a']++;
}

mx=*max_element(fr,fr+26);
for(j=0;j<26;j++)
{
// cout<<fr[j]<<endl;
tot+=fr[j];
}
// cout<<tot<<" "<<mx<<endl;
tot=tot-mx;
//cout<<tot<<endl;
}
if(k%2==0)
{
cout<<tot<<endl;
}
else
{
for(i=0;i<26;i++)
fr[i]=0;

for(i=k/2+1;i<n;i=i+k)
{
fr[s[i]-'a']++;
}
mx=*max_element(fr,fr+26);
for(i=0;i<26;i++)
{
tot+=fr[i];
}
tot=tot-mx;

cout<<tot<<endl;
}
}
return 0;

}

•  » » 18 months ago, # ^ |   +20 Suggesting adding code into the spoilerAnd this code block 
 » 18 months ago, # |   0 For problem BInput:23437 519 865 808 909 391 194 291 237 395 323 365 511 497 781 737 871 559 731 697 779 841 961My output is101 2 2 3 3 1 3 2 2 4 1 4 5 5 6 6 7 7 8 8 1 9 10And I got this message: wrong answer violates gcd constraint.Can anyone help explain? I don't really understand the conditions of this problem
•  » » 18 months ago, # ^ |   +4 the numbers colored with 3: 808,909,194they don't have a gcd larger than 1.
•  » » » 18 months ago, # ^ |   0 Okay, thanks for answering @dapingguo8
 » 18 months ago, # | ← Rev. 2 →   -51 it was very good contest
 » 18 months ago, # |   +1 Can someone tell me why I get TLE: https://codeforces.com/contest/1332/submission/74951923 I genuinely don't know.
 » 18 months ago, # |   -41 My quick review:A — classic shitty A with many casesB — too long statement for such an easy taskC — good task but too simple for CD — awful constructiveE — classic «try and guess» combinatoricsF — pretty standard dp (counting again)G — good task
•  » » 18 months ago, # ^ |   +9 My views on A and C are opposite to yours. There is only one special case in A and even that is given in sample tc.
•  » » » 18 months ago, # ^ |   0 There are 0 edge cases in C though :thinking:
•  » » » » 18 months ago, # ^ |   0 I meant that A was good and C was not
 » 18 months ago, # |   0 In E, I sincerely thought that answer height had to be between L and R also and was losing my mind for an hour.
 » 18 months ago, # |   -97 I just downvoted your contest.FAQ What does this mean? The amount of contribution (points) on your comment and codeforces account has decreased by one.Why did you do this? There are several reasons I may deem a comment to be unworthy of positive contribution. These include, but are not limited to:Rudeness towards me,Making bad contest,Sarcasm not correctly flagged with italic font.Am I banned from the Codeforces? No — not yet. But you should refrain from making contests like this in the future. Otherwise I will be forced to issue an additional downvote, which may put your commenting and posting privileges in jeopardy.I don't believe my comment deserved a downvote. Can you un-downvote it? Sure, mistakes happen. But only in exceedingly rare circumstances will I undo a downvote. If you would like to issue an appeal, shoot me a private message explaining what I got wrong. I tend to respond to Codeforces PMs within several minutes. Do note, however, that over 99.9% of downvote appeals are rejected, and yours is likely no exception.How can I prevent this from happening in the future? Accept the downvote and move on. But learn from this mistake: your behavior will not be tolerated on CodeForces.com. I will continue to issue downvotes until you improve your conduct. Remember: Codeforces is privilege, not a right.
•  » » 18 months ago, # ^ |   +48 If you want to criticize someone just say what you don't like, there's no need to be snarky with this whole 'legal downvote' act or whatever this is supposed to be.
 » 18 months ago, # |   0 I really liked the problems :)I thought they were balanced; considering the score distribution of course.I think the reason some found them to be unbalanced is that they were kind of unusual. Especially B D which were not like most B Ds. If you ask me though, that's a very good thing.(some saw A to be too tricky and long though, which is kinda true)The round was smooth enough to be a success considering how many registered.Good job, you should be proud!
 » 18 months ago, # |   +28 Sample test 2 for D gave it away
 » 18 months ago, # |   0 Thanks for the Fast Editorial!!
 » 18 months ago, # |   +5 A really Good Contest. Handled 23k Participants with almost negligible waiting queue and still fairly enough strong pretests.
 » 18 months ago, # |   0 Super Fast editorial
 » 18 months ago, # |   +12 I figured out why many people(including me) got wa on test 57 in E) it was because of %(mod-1)x^y≡x^(y%(p-1))mod p but there is a condition that x needs to be coprime to p the following test case was a corner case- 998244352 2 1 998244353the sad thing is that %(mod-1) wasn't even needed. I wish this test case was in pre-tests
•  » » 18 months ago, # ^ |   +4 next time you can use % (mod - 1) + mod - 1 instead
•  » » 18 months ago, # ^ |   0 Thanks, missed the coprime condition :-(
 » 18 months ago, # |   +8 Why my first submission to problem B get AC ? The array "to" is out of bounds 75000215
•  » » 18 months ago, # ^ | ← Rev. 2 →   +7 It's an array, so you have undefined behavior without errors. It's not affected to your solution, because you aren't using values from to[11-13], but you're only assigning it.
•  » » » 18 months ago, # ^ |   +8 But in some cases col[i] use all number from 1 to 11，and to[11] is also used
•  » » » » 18 months ago, # ^ | ← Rev. 2 →   +9 Undefined behavior is undefined...(You were lucky to have free memory after to array in each test, so you could use it. I'm obviously not expert in c++, but once I saw a similar example)
•  » » » » 18 months ago, # ^ | ← Rev. 3 →   +8 On my machine it works, on cf's custom test too, but at the same time it is ub: int arr[3] = {1,2,3}; arr[3] = 4; cout << arr[3]; //output is 4 
•  » » » » » 18 months ago, # ^ |   +9 Okay I got it ,anyway I should avoid such errors，thank you very much
 » 18 months ago, # |   0 Hi, can someone help me figure out what was wrong with my submission for problem B?https://codeforces.com/contest/1332/submission/74968519I am a beginner and I am really confused as I implemented a very similar solution to the problem as is given in the editorial.
•  » » 18 months ago, # ^ |   0 Re-read the "Output" part of problem statement and compare it with your output of the 3rd subtest.
•  » » » 18 months ago, # ^ | ← Rev. 2 →   0 Output from my solution for testcase 3:108 2 3 1 2 7 1 2 2 3 7 3 4 4 5 5 6 6 7 7 8 10 11Output from solution copied from Editorial for testcase 3:108 2 3 1 2 7 1 2 2 3 7 3 4 4 5 5 6 6 7 7 8 9 10I only see 1 difference, but isn't mine also a solution?
•  » » » » 18 months ago, # ^ |   0 Figured out the problem, I was going out of range.
 » 18 months ago, # |   +76 To not keep you waiting, the ratings updated preliminarily. In a few hours, I will remove the cheaters, fix wrong division cases and update ratings them again!
•  » » 18 months ago, # ^ |   -30 chup be.
 » 18 months ago, # |   +11 Am I the only one who started solving D with XOR instead of AND (and only realized the mistake after getting WA2)?..
•  » » 18 months ago, # ^ |   +8 I first started solving with OR got wa on test 2 and then realized its AND
 » 18 months ago, # |   +3 Was A tougher than normal today or was it just me?
•  » » 18 months ago, # ^ |   +6 It was the worst A in my life:/
•  » » 18 months ago, # ^ |   +9 my theory is they made it a bit implementation-heavy to avoid the initial congestion of 20000 submissions in the first 2 minutes :p
•  » » » 18 months ago, # ^ |   +3 Lmao I hope problem setters don't find this tip xD
•  » » 17 months ago, # ^ |   0 I think no.. One simple solution is to print 'W' at last cell i.e at (n,m) and keep all cell 'B'..It will be quite tough if try in other way
 » 18 months ago, # |   0 weak testcases and the queue wasn't full like last div3
 » 18 months ago, # |   +1 Math forces :/
•  » » 18 months ago, # ^ |   -33 worst round even in history. puzzleforces.
•  » » » 18 months ago, # ^ |   0 Just f was computer problem (I didnt read g)
•  » » 18 months ago, # ^ |   +120 You haven't seen real Mathforces
 » 18 months ago, # |   0 Nice contest. A was somewhat harder than usual Div2 contests (BTW, thanks for including the third testcase in the sample — I completely missed that possibility), but I have seen far worse. B and C were good problems — moderate implementation. I felt D was a bit more difficult to think of, so D should have been worth more points than C. D should probably be worth 1500 points, and E at least 2000 points.
•  » » 18 months ago, # ^ |   0 D was a 2 liner task even in C++
•  » » » 18 months ago, # ^ |   +6 No. of lines is never a good estimate of difficulty. It took me a lot of time to think of an idea for solving D.
•  » » » » 18 months ago, # ^ |   0 Ya I meant implementation was easy!
 » 18 months ago, # |   0 Was it really necessary to make the bounds up to 2 * 10 ^ 5 instead of 10 ^ 5, I felt this was unnecessary. I am a bit biased because this was the cause of my FST on problem C.
 » 18 months ago, # |   0 What does "violates gcd constrain" means?
•  » » 18 months ago, # ^ |   0 means some of gcd == 1
 » 18 months ago, # |   0 Minus A I really enjoyed the problems from this round And the definitions of left, right, down and up in A were really weird exactly a steps L: from (u, v) to (u − 1, v); exactly b steps R: from (u, v) to (u + 1, v); exactly c steps D: from (u, v) to (u, v − 1); exactly d steps U: from (u, v) to (u, v + 1); This doesn't feel right at all! I feel left and down should be swapped same for right and up
•  » » 18 months ago, # ^ |   +5 it would be natural if you consider it as the 2D coordinators
•  » » » 18 months ago, # ^ | ← Rev. 3 →   -11 Idk!
•  » » » 18 months ago, # ^ |   +1 It would be natural to not name them a,b,c,d but l,r,u,d. And maybe using the terms rows and cols.
 » 18 months ago, # |   +3 triple__a, respect.
 » 18 months ago, # |   +3 You should post the top scorers as well as the 1st solves for each problem. That would be cool
 » 18 months ago, # |   +3 Thank you for the contest triple__a, I really enjoyed it :) Particularly problem D, which I managed to get in the last 2 minutes (luckily), which was really fun to do!
 » 18 months ago, # |   0 Why do we need to consider both cnt[i%k][j] and cnt[k-i%k-1][j] in question C?
•  » » 18 months ago, # ^ |   +1 Because the segments of size k are palindromes, too.
 » 18 months ago, # | ← Rev. 2 →   0 OK！
 » 18 months ago, # |   0 does memset work slow?problem c gives TLE using memset [submission:https://codeforces.com/contest/1332/submission/74982492]with vector got AC [submission:https://codeforces.com/contest/1332/submission/74983633]
•  » » 18 months ago, # ^ |   +1 Memset is wildly fast. The issue with your submission is that you memset the entire array (of size 5.2 million) for each of up to 100000 test cases. This is $5.2 \cdot 10^{11}$ operations, which is way too many. Manually filling the array with zeroes up to $n$ or $k$, or using vectors in your case, makes your runtime on the order of $\sum n$ instead of $T \cdot 5.2 \cdot 10^6$.
 » 18 months ago, # |   +3 Auto comment: topic has been updated by triple__a (previous revision, new revision, compare).
 » 18 months ago, # |   0 Hey! I am very beginner to competitive coding. may anyone suggest any lead from where i should start?
•  » » 18 months ago, # ^ |   0 Solve problems, the more the better. Click above on "Problemset" and just do it.
•  » » 18 months ago, # ^ |   +1 whatever you are typing here just type in google and press enter you will get millions of suggestions already suggested.
 » 18 months ago, # | ← Rev. 2 →   0 Too many competitors,,too much discussion,too much fun,,:)Good ratings always brings happiness for coders.
 » 18 months ago, # |   0 Everyone is pro here.. I am new. I wanna learn Programming like those expert guys . :( Help me ! -_-
 » 18 months ago, # |   0 Hey guys, I made a video tutorial for problem F which, btw I really enjoyed solving! https://www.youtube.com/watch?v=oEPtZLUG4iQ