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:
awoo for great coordination of this round, and the idea of solution of one task!
Nanako, Nezzar for useful discussion and testing this round!
antontrygubO_o, McDic, vovuh, TBeumsJryi, socho, Oak_limy, Amori, Stresshoover, I1I1I11I1I1, defolaut, hx073269 and Pavlova for testing this round and invaluable suggestions!
MikeMirzayanov for great systems Codeforces and Polygon!
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:
[user: _dawn]
people who were first to solve each task:
B: MagentaCobra
C: okwedook
E: GsjzTle
F: yooooooooo
G: GoGooLi
Lastly, thanks to Handsome2004 for the brilliant hack of E.
Auto comment: topic has been updated by triple__a (previous revision, new revision, compare).
this round suddenly come there was april fool contest and after that div1+div2 after last div3. thanku for the contest. :)
Welcome everyone to join in $$$⩾w⩽$$$
What does it mean?
maybe I should add a full stop
Welcome everyone to join in. ⩾w⩽
$$$⩾w⩽$$$ ← it's just a emoticons.
hoping to get expert
I really hope that this H̶o̶p̶e̶ ̶s̶o̶ works!
Small but strong pretests yey no more queue thank you
t = 1e5 in the sample...
That sounds cool but hard to copy :D
The number of participant is more and more large, it is another factor causing long queue, I think.
Long time no Chinese Round
corona
Waited for Div.2 Round long time. :)
I hope I can get a good score!
Hope to see my username in blue after this contest. ^_^
Good luck
All the best :D
The time is nice for Chinese :P
I see what you did there LOL
I like queueforces. My code feels like schrodingers cat.
But you're a dog
Thanks to all contest writers to make us busy during this lockdown situations. You are doing a great job. STAY SAFE STAY HOME
...To avoid queueforces, we will provide small amount but strong (hope so) pretests for first few tasks.
I hope that this contest will increase my rating.
Name a person wants his/her rating to be decreased !! -_- -_-
Maybe errorerror?
Why 150 minutes? Is it hard?
One of the reasons is there will be 7 problems, not 6 :)
how to get started in this contest , can anyone help i am new here
go here and click Register Now on Codeforces Round #630 (Div. 2) and be online at the given time.
thanks for the help @Jo3kerR
Just go to contests section and you will find the contest
You can register in it
Already did earlier i didn't know where to start
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!!!
Just curious about the "useful" discussion Nanako and Nezzar took part in.
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.
Hopefully I will :)
(PS -Didn't knew about the amount of efforts you guys give while preparing contests. Thanks :) )
Generally testing & discussion of problems. Hope you enjoy the problems triple__a prepared!
Due to Quarantine registration will exceed 20K for sure. Thanks codeforces for arranging contests, the only partner in this quarantine :)) #GOCORONA #STAYSAFE #HAPPYCODING.
how rating of expert contestents change in last div 3 round? sorry, I didn't notice.they fixed this.
it is andryusha_na_knopke magic
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!
How to test problems. How can i learn that. Thanks.
I hope one day you'll be able to host your own contest :)
Is it Subtask-forces ?
no
150 minutes...oh yeah!!...I got no work to do in this quarantine anyway.
Nice rating graph triple__a
I receive the message from admin and surprised
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.
I need triple(+7) to become Candidate .. I hope i will earn them !
good luck!
****I'm really honored to take part in this test**** ****Good luck everyone!****
Thanks all of the members of this contest to prepare another good contest hopefully
First time participating in a live contest. Y'all got any pointers ?
Alas! I can't solve solve problem B/C. I just can solve problem A.
I don’t remember asking
rekt
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.
CoronaChina :)Auto comment: topic has been updated by triple__a (previous revision, new revision, compare).
Auto comment: topic has been updated by triple__a (previous revision, new revision, compare).
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.
Maybe C and D are subtasks? Who knows ))
The author said that there are no subtasks
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!
Best of luck guys !!!
My request to admin to conduct more contests while this lockdown period. Thanks
They need time to prepare good quality rounds. Holding more rounds will definitely affect their quality.
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. :)
After seeing the score for question c and d. Excited to see which one will be easy one.
Guess, Which one will get more accepted, C or D?
I think, A will get the most
it depends if there will be sub task then obviously c will get more accepted. other than that let us in 1 hour.
C
We need more such contests in this quarantine period. Another Reason to stay at home.
.
HackForces?
SubtaskForces
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.
More than 20k people! this will be fun!! :D
Fun by waiting for the problem to get judged (long queue) ?
Quick Check:- This is first contest designed by triple__a
WOOOOO I am very expect to join the contest,hope for a good game experience and everybody will get good rating improving o-o
Huge participation indicates more people performing home quarantine.
CF gonna fall down
problems are so fricking complicated I dont mean it is hard it is complicated fricking contest
I guess it's just my taste but A was quite disgusting
Both A and B made me extremely uncomfortable:(
stop setting problems.
stop complaining. The service provided here is free, you are not paying anyone and why does it matter to unrated acc.
let's make a round which is neither queueforces nor readforces next time!
Now I'm curious what this comment was
Quality with Difficulty
Really all problem are look like more tougher than usual contest
I feel like 2:30H is too much for a cf contest.
fuch triple__a[user:triple__a] worst contest ever. dumbfuck dont know how to set problems
Stop insulting people just because you were not able to solve the problems.
Chinese Round is too hard for me.
I am glad that at today's round there were no queues and exits from the profile, thank you very much!
Praying God for not failing in system test.
I mean, that's literally the score distribution
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
It's also the first test on which not changing mod from 1e9 + 7 fails :P
Exactly the same problem. Fortunately noticed it in the last 5 minutes, and only needed 1 line change in code to solve it :D
How to solve G?
Video tutorial for problem D
Hope you enjoy it!
Could you explain how you approached C
You can observe that the string which is the period has to be palindromic as well
Just greedily choose the maximal frequency of each letter and drop from n the sum of maximal frequences
What is the minimum size of the matrix which could be formed in que D?
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)
I don't know how it was for you guys, but for me it was a hard round. :\
So hard :с
I am excited to see the editorial now :D
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.
Hardest ever A .
I think D was hard. It made me really sit and think.
D was really Trivial.
But it took me an hour because I was thinking in the wrong side
D is trivial then and only then you already know, how to solve it
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.
I solved B & C but not A. actually it seems so lengthy for me I didn't wanted to give time for this. :(
What is your approach for solving B?
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
Ahh, thanks!
When you realize B solution only need first 11 primes
1 2 137 137 u may get wrong answer
2 & 137 are not composite no.
had a bad experience
E is one of the most elegant problems I've seen so far :o
Can you tell your thought process for it?
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:
If 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.
If 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 :)
All 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}$$$.
Only 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:
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$$$.
Shouldn't it be ((a+b)^nm + (a-b)^nm)/2 ?
Thanks, corrected.
Can someone please help, how to calculate the number of correct boards in E when n * m is even.
if (r-l) is odd $$$\frac{(r-l+1)^{nm}}{2}$$$
else $$$\frac{(r-l+1)^{nm}}{2}+1$$$
How did you get that formula?
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
It should be $$$\frac{(r-l+1)^{nm}+1}{2}$$$ instead of $$$\frac{(r-l+1)^{nm}}{2}+1$$$
Can you tell how you get the formula in brief ?
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}$$$.
Thanks.
this is my first time to take part in a real contest. But... I couldn't solve a single task lol
Loved D ques.
It was really trivial if you know the basics of BitWise Operations.
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?
If n*m is even, you can do this always, your argument holds for odd n*m
oh snap! got it
Please share soln of B !!!!
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 .
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.
And, according to constraints given you can just colour all the numbers with the first 11 prime numbers.
Submission
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.
I did the same, got wrong answer somehow. Seems correct to me (Works on the testcases given)
https://codeforces.com/contest/1332/submission/74968519
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].
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.
Shortest solution to a D problem ever. Loved the simplicity ;)
.
I'm failed at D at the last minute because number larger rr than >300000 if only i had read the checker logs :(
-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
lmao :5head:
D sample test itself is a gigantic hint.
That is very true!Guess what xD? I copied the second sample output and modified it a little bit and done, accepted!
For G i did this following observations:
1. It's obvious that answer is 3 or 4
2. 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]<a[i1+1] and a[i3]<a[i3+1])
Is the solution based on developing this idea or I am going the wrong direction?
Ignore me, I was wrong, sorry :)
but 1,2,3,4 is the answer there.
Consider this case:
5 1
2 3 1 3 2
1 5
This Div2 was having more puzzle problems, I guess!
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.
Me RN
First of all kudos and thanks to codeforces for handling high participation so nicely.
Thanks for the contest. Wish problem-setters have good days <3
By the way, how to solve E guys ? :(
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.
Also , my logic gave incorrect ans on 4th tc (i got 17 but ans was 16)
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.
But how this formula is going to ensure that resulting string will be a Palidrome??
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.
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 % kand you are selecting max from that forpos = i % k.But you also have to consider
k - pos - 1characters forpos = i % k.Reason is we have to consider frequency of all characters which can come at
pos = i % kand they can be due to period positions and due to palindromic positions.My Submission 75017302
Am I the only one who did problem C. using a simple DFS with connected components? Felt like an overkill...
Wait DFS how?
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 letter
You 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.
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.
Can you briefly illustrate your approach?
lets take that example: 6 2 abaaba
transform 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 abaaba
Transformation: 123123
It 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.
I did it as well
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.
Solution for E: Let total odd numbers in the range be odd, and total even numbers in the range be even. Let tot=n*m
If tot is odd, then answer is power(even+odd,tot). else the answer is (power(even-odd,tot)+power(even+odd,tot))/2
IS THIS APPROACH CORRECT?
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.
Auto comment: topic has been updated by triple__a (previous revision, new revision, compare).
B has taken much time because I cannot understand the meaning of the range of $$$m$$$ at first.
Why Bob is incorrect in question D, i think his algo is correct for maximum??
3 3
7 4 7
3 7 7
7 7 3
Answer should be 3, but Bob's algorithm gives 0
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 ll long long
define ld long double
define pb push_back
define pi pair<int,int>
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;}
For problem B
Input:
23
437 519 865 808 909 391 194 291 237 395 323 365 511 497 781 737 871 559 731 697 779 841 961
My output is
10
1 2 2 3 3 1 3 2 2 4 1 4 5 5 6 6 7 7 8 8 1 9 10
And I got this message: wrong answer violates gcd constraint.
Can anyone help explain? I don't really understand the conditions of this problem
the numbers colored with 3: 808,909,194
they don't have a gcd larger than 1.
it was very good contest
Can someone tell me why I get TLE: https://codeforces.com/contest/1332/submission/74951923 I genuinely don't know.
My quick review:
A — classic shitty A with many cases
B — too long statement for such an easy task
C — good task but too simple for C
D — awful constructive
E — classic «try and guess» combinatorics
F — pretty standard dp (counting again)
G — good task
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.
There are 0 edge cases in C though :thinking:
I meant that A was good and C was not
In E, I sincerely thought that answer height had to be between L and R also and was losing my mind for an hour.
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.
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.
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!
Sample test 2 for D gave it away
A really Good Contest. Handled 23k Participants with almost negligible waiting queue and still fairly enough strong pretests.
Super Fast editorial
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 998244353
the sad thing is that %(mod-1) wasn't even needed. I wish this test case was in pre-tests
next time you can use
% (mod - 1) + mod - 1insteadThanks, missed the coprime condition :-(
Why my first submission to problem B get AC ? The array "to" is out of bounds 75000215
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.
But in some cases col[i] use all number from 1 to 11，and to[11] is also used
Undefined behavior is undefined...(You were lucky to have free memory after
toarray in each test, so you could use it. I'm obviously not expert in c++, but once I saw a similar example)On my machine it works, on cf's custom test too, but at the same time it is ub:
Okay I got it ,anyway I should avoid such errors，thank you very much
Hi, can someone help me figure out what was wrong with my submission for problem B?
https://codeforces.com/contest/1332/submission/74968519
I am a beginner and I am really confused as I implemented a very similar solution to the problem as is given in the editorial.
Re-read the "Output" part of problem statement and compare it with your output of the 3rd subtest.
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!
Am I the only one who started solving D with XOR instead of AND (and only realized the mistake after getting WA2)?..
I first started solving with OR got wa on test 2 and then realized its AND
Was A tougher than normal today or was it just me?
It was the worst A in my life:/
my theory is they made it a bit implementation-heavy to avoid the initial congestion of 20000 submissions in the first 2 minutes :p
Lmao
I hope problem setters don't find this tip xD
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
weak testcases and the queue wasn't full like last div3
Math forces :/
worst round even in history. puzzleforces.
Just f was computer problem (I didnt read g)
You haven't seen real Mathforces
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.
D was a 2 liner task even in C++
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.
Ya I meant implementation was easy!
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.
What does "violates gcd constrain" means?
means some of gcd == 1
Minus A
I really enjoyed the problems from this round
And the definitions of left, right, down and up in A were really weird
This doesn't feel right at all!
I feel left and down should be swapped same for right and up
it would be natural if you consider it as the 2D coordinators
Idk!
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.
triple__a, respect.
You should post the top scorers as well as the 1st solves for each problem. That would be cool
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!
Why do we need to consider both cnt[i%k][j] and cnt[k-i%k-1][j] in question C?
Because the segments of size k are palindromes, too.
OK！
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]
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$$$.
Auto comment: topic has been updated by triple__a (previous revision, new revision, compare).
Hey! I am very beginner to competitive coding. may anyone suggest any lead from where i should start?
Solve problems, the more the better. Click above on "Problemset" and just do it.
whatever you are typing here just type in google and press enter you will get millions of suggestions already suggested.
Hey guys, I made a video tutorial for problem F which, btw I really enjoyed solving! https://www.youtube.com/watch?v=oEPtZLUG4iQ