### Agnimandur's blog

By Agnimandur, 2 months ago,

Hello, Westeros!

I'm glad to invite you to Codeforces Round #736 (Div. 1) and Codeforces Round #736 (Div. 2), which will be held on Aug/01/2021 17:35 (Moscow time).

The round will be rated for both divisions. Each division will have 5-7 problems and 2 hours and 15 minutes to solve them. There will not be an interactive problem, so yay!!!

This round would not have been possible without the following individuals:

1. Aleks5d, for awesome coordination of my round.
2. Benq, for extensive testing and contributions throughout the round, especially for 1548E - Gregor and the Two Painters.
3. 1-gon, for discussing problems and statements with me for hours on Discord.
4. amgfrthsp, for translating statements into Russian.
5. MikeMirzayanov, for Codeforces and Polygon.

#### 32 testers

The round had a total of 32 testers. I tried to get a "rainbow" of testers to help guarantee a most balanced round. Thank to you to each and every one of them!

This is my first round ever written, and I sincerely hope you enjoy it, regardless of your rating!

#### Score Distribution

Div 1: 500 — 1000 — 1750 — (2000 — 1000) — 3500

Div 2: 500 — 750 — 1250 — 2000 — 2500 — (2000 — 1500)

## Winners

Congratulations to all our winners in the round!

#### Div1

1. Miracle03, congratulations on the AK!
2. tourist, congratulations on the AK!
3. yhx-12243
4. heno239
5. Isonan

Special congratulations to antontrygubO_o and Subconscious for definitely reaching the rank of Legendary Grandmaster!

#### Fastest Solves

• +1253

 » 2 months ago, # |   +83 Thanks for the early score distribution!
•  » » 2 months ago, # ^ |   +351 Yeah no problem!There's no reason to needlessly hide the score distribution.
 » 2 months ago, # |   -13 2 hour 16 min
 » 2 months ago, # |   +49 Newbie Testers Go Hereanyways I'm excited for this contest good luck to all those who are planning on participating
•  » » 2 months ago, # ^ |   -6 can newbies be testers?
•  » » » 2 months ago, # ^ |   0 Yes.
•  » » » 2 months ago, # ^ |   +17 anyone can be a tester if he/she is a trustable friend of the author or the author himself asked someone for testing
•  » » 2 months ago, # ^ |   -14 I hope to be solved at least two problems...
•  » » » 7 weeks ago, # ^ |   +18 Codeforces, sorry for my comment, I will not write comments like this anymore. :(
 » 2 months ago, # |   -132 Div 2 Speedforces incoming Spoiler Just look at the score for c
 » 2 months ago, # |   +268 As a tester, let me participate officially Spoilerupvote for +100 delta
•  » » 2 months ago, # ^ |   +76 As a tester, zyzzsama stole my as a tester comment :(Anyways, I liked the problemset of this contest a lot, and I am sure you would also do the same ! Wish you enjoyable contest duration :)
 » 2 months ago, # |   +87 Discrimination of testers on the basis of colour :(
•  » » 2 months ago, # ^ |   +24 "#justice_for_testers" XD
•  » » 2 months ago, # ^ |   +29 tester lives matter
 » 2 months ago, # |   +47 As a tester, problems are great!
 » 2 months ago, # |   +13 Benq, for extensive testing and contributions throughout the round, especially for problem G.1-gon, for discussing problems and statements with me for hours on Discord.I tried to get a "rainbow" of testers to help guarantee a most balanced round.check here for the hint-based editorial!Stop it... don't give me this hope...
 » 2 months ago, # |   +285 As a VIP tester I recommend everyone to gain rating!
•  » » 2 months ago, # ^ |   +454
•  » » » 2 months ago, # ^ |   +84 purplecrayon is purple :<
•  » » » » 2 months ago, # ^ |   +45 Spoilerpurplecrayon is actually a crayon :O
•  » » » » » 2 months ago, # ^ |   +9 What about DioHERO?
 » 2 months ago, # | ← Rev. 2 →   +62 As a tester, I think you will collectively get down on your knees and orz Agnimandur for his hard work and awesome problems after contest. I recommend you to read all of his problem statements and wish you good luck!
 » 2 months ago, # | ← Rev. 3 →   +15 As a tester, this round is balanced for every participators in both divisions. I recommend you to read all the problem and try to solve as much as you can. Good luck! -QuangBuiYT
•  » » 2 months ago, # ^ |   0 I miss u brother :(
 » 2 months ago, # |   +94 Thanks for a great set of problems. I recommend everyone to participate and gain rating! OMG My first "As a tester..." comment
•  » » 2 months ago, # ^ |   +11 I recommend you to participate and be master again :P
•  » » 2 months ago, # ^ |   0 Am I the Only One who Read ** OMG My first "As a tester..." comment**... In this comment?
•  » » » 2 months ago, # ^ |   +5 No
•  » » 2 months ago, # ^ |   +5 How to write an invisible text? (OMG My first "As a tester..." comment)
•  » » » 2 months ago, # ^ | ← Rev. 2 →   +20 Use some html, I did  insert_text_here
•  » » » » 2 months ago, # ^ |   +8 Thanks
•  » » 2 months ago, # ^ |   +29
 » 2 months ago, # |   -15 I hope to become specialist after this round
•  » » 2 months ago, # ^ |   0 i want to do D nothing else matters, focus on action rather than outcome
•  » » 2 months ago, # ^ |   +68 Biggest lesson I have learnt is to never target any certain color or rank in cp.I still don't forget the day I registered for codeforces. That is a memorable day of my life.A young kid ( I am still a kid ) had no other other thoughts in mind except writing some codes and how to get the AC verdict.As months went by,I slowly started to think about colors but recently I had come to some realisations : My love for problem solving is greater than any random color If I keep loving what I do I will eventually end up reaching my highest potential Competitive Programming is something which has gifted me a beautiful life.I should keep loving it and not take it as a duty.I should take it as my passion and hobby
•  » » » 2 months ago, # ^ |   +6 Expectations: (see above) Reality: I solve contests to gain my rating (It's just a joke, don't be so serious <3)
 » 2 months ago, # |   +99 lighthearted meme
•  » » 2 months ago, # ^ |   +14 i am at 1399 , i was hurt by this lighthearted meme
 » 2 months ago, # | ← Rev. 2 →   0 Good to see that Problem A is of 500 again
 » 2 months ago, # |   0 This may not be the best place to ask it but can we deduce the difficulty of problem from the scoring distribution? Like here in Div2, there is high gap between score for problem B and C.. does it mean the same for their difficulty gap too?
•  » » 2 months ago, # ^ |   +11 There is no certainity about difficulty of a problem on the basis of a its score in the contest.
•  » » » 2 months ago, # ^ |   +4 Thanks :) Hope to solve till C!!
•  » » 2 months ago, # ^ |   0 Scoring distribution is a hint to how hard the problem is, but it doesn't necessarily signify difficulty.
 » 2 months ago, # |   0 is Div2 for people <1900 or <2100 ? in these rounds.
•  » » 2 months ago, # ^ |   0 <1900
 » 2 months ago, # |   -41
•  » » 2 months ago, # ^ |   0 I don't know what's the benefit of ratings distribution. Problems will come and ratings will go.
 » 2 months ago, # |   0 Good job
 » 2 months ago, # |   -28 You should provide model solution in python too .
 » 2 months ago, # | ← Rev. 2 →   +13 You got "rainbow" of testers, but not "rainboy". That might have led to unusual round ;)
•  » » 2 months ago, # ^ |   +108 That unusual round might have a scoring distribution like :(2500 - 2000 ) -2500 - 2000 - 1250 - 750 - 500
 » 2 months ago, # |   +63 Now I wonder what will happen when the contest starts...
•  » » 2 months ago, # ^ |   -9 depending on your rating you are a rated contestant for one contest and unofficial contestant for other. But as long as you don't submit code on a single problem. It is taken as you not participating in the contest
•  » » » 2 months ago, # ^ |   +69 If so he can submit in div2 till pretest passed to avoid penalties in div1.
•  » » 2 months ago, # ^ |   +6 Well, I have seen a participant in situation like this, and he said 404 Error was displayed when contest started :D
•  » » » 2 months ago, # ^ |   +8 It seems that all registered participants whose rating is higher than 1899 have been deleted from div.2, so I can't find out what will happen(
 » 2 months ago, # |   0 Thx for nice score distribution;)
 » 2 months ago, # |   0 Tester squad from Errichto's Discord!!
 » 2 months ago, # |   0 Hope the problems with the scoring distribution 2000 will be like in previous round(not educational)
•  » » 2 months ago, # ^ |   +6 ahahah that problem D in round 735?) yeah, it was to ooverrated, should be like 1000
 » 2 months ago, # |   0 Hope the Difficulty level will not be like last Codeforces Round #735PS: Puplis Like Me need +ve Delta :)
•  » » 2 months ago, # ^ |   0 i feel like i was at fault at that round , b wasn,t that hard i realise now
 » 2 months ago, # | ← Rev. 3 →   +14 and thanks MikeMirzayanov for this amazing platform
•  » » 2 months ago, # ^ |   +10 You could have said it without tagging him :|
•  » » » 2 months ago, # ^ |   +6 Umm... Lemme edit
•  » » » 2 months ago, # ^ |   +29 Why so many downvotes people? He changed his comment :(
 » 2 months ago, # |   +30 In this announcement Total comments = 32 Tester's comments = 69
 » 2 months ago, # |   0 Going to participate from beyond the wall.
 » 2 months ago, # |   +3 As a non-tester, I will participate this round!
 » 2 months ago, # |   +5 Positive post
 » 2 months ago, # | ← Rev. 2 →   0 I would like to be a newbie tester.(and I will solve 0 problems)
 » 2 months ago, # |   +40 2000 points for div1C OMG
 » 2 months ago, # |   +9 As a tester I can confirm that Agnimandur put a great deal of time and effort into creating a very clear and engaging problemset. I hope you guys enjoy the problems as much as I did.
 » 2 months ago, # |   0 Hoping for a good round.
 » 2 months ago, # |   0 Again I will participate and not answer anything . Cause this one be !easy too ...
 » 2 months ago, # |   0 Hope the round will be interesting and i will cross 1350
 » 2 months ago, # |   -44 ![ ]()
 » 2 months ago, # |   +3 rainbow follows VIBGYOR btw
 » 2 months ago, # |   0 Thanks for putting effort for this round! Also hint-based editorial is nice :)
 » 2 months ago, # |   0 Newbie Testers Go HerePOV: Newbie contestants are testers for future contests.
 » 2 months ago, # |   +1 I hope the problem statements are short and the pretests are strong.
•  » » 2 months ago, # ^ |   0 Thank you, the pretests are strong!!
 » 2 months ago, # |   +3 I hope I become specialist after this one.
•  » » 2 months ago, # ^ |   0 Best of luck, you are near at specialist
•  » » » 2 months ago, # ^ |   0 Thank you so much!!
 » 2 months ago, # |   +12 I Like Div2-735 round because of short statement and more interesting problem. Hope this round will be more interesting. );
•  » » 2 months ago, # ^ |   +16 dont bomb the contest
•  » » » 2 months ago, # ^ |   +3 I don't bomb on innocent platform like (Codeforces). Cz, Everybody loves it. I also love it.
•  » » » » 2 months ago, # ^ |   0 Is Codeforces halal, probably not
•  » » » » » 7 weeks ago, # ^ |   0 I think, you should focus on yourself brother. It is not debating site.);
•  » » » » » » 7 weeks ago, # ^ | ← Rev. 2 →   +15 bin laden is a terrotist there is no debating
 » 2 months ago, # |   0 I'm exiting about the round. Thank You.
 » 2 months ago, # |   +6 I trust a Game of Thrones fan
•  » » 2 months ago, # ^ | ← Rev. 2 →   +4 Spoiler
 » 2 months ago, # |   0 Did the newbie testers outperform the experts?
 » 2 months ago, # |   +29 As a tester, I can confirm that this round has good problems and I hope that you will enjoy it
 » 2 months ago, # |   0 I am really excited about it. By the way, how can someone become a problem test. Just asking out of curiosity.
•  » » 2 months ago, # ^ |   0 You can be a tester if you're a trusted friend of the author of the contest.
 » 2 months ago, # |   -17 I hope I can solve the problem of 3 quickly
 » 2 months ago, # |   +1 I hope i don't struggle with B again
 » 2 months ago, # |   0 First round in August! Excited!
 » 2 months ago, # |   +179 https://millionaire.fandom.com/wiki/Shiva_OswalAgnimandur is it you? Amazing!
•  » » 2 months ago, # ^ |   +13 Agnimandur orz!
 » 2 months ago, # |   +6 “regardless of your rating!”I hope so,but it keeps decreasing.T_T
 » 2 months ago, # |   +14 so div1 has only one harder problem than div2? maybe it should have been div(1+2) in this case
•  » » 2 months ago, # ^ |   -21 Count again, for me it looks like the usual two.
•  » » » 2 months ago, # ^ |   +21 the last div2 is (2000-2500) and the one before last in div1 is (2000-2000) so it's the same problem which means div1 has one extra harder problem right?
•  » » » » 2 months ago, # ^ |   +8 Ah, ok, I see.
 » 2 months ago, # |   0 good luck competitors.
 » 2 months ago, # | ← Rev. 2 →   0 Loved the testers section..
 » 2 months ago, # |   0 What with the rating of E, is it easier than D?
 » 2 months ago, # |   0 Better than contest with 750 as first problem :)
 » 2 months ago, # |   +20 Oh f I just realised that you are shiva oswal ,champion of history bee tournament , see this, orz
 » 2 months ago, # |   +1 My trash luck , I forgot to register so I have to wait for 10min. 5k submission for problem a . now when I can finally register, I am in long queue.
 » 2 months ago, # |   -11 Well Balanced Round. Thank you writers and testers :)
 » 2 months ago, # | ← Rev. 2 →   0 First few minutes problem statements to me (In m2 and m3. not able to check m1.)Your text to link here...
 » 2 months ago, # |   -26 I hate div 2 C.
•  » » 2 months ago, # ^ | ← Rev. 2 →   -24 ///
•  » » » 2 months ago, # ^ |   0 thank god i got it finally, wish the same for you guys. But the contest was surely very well made.
•  » » 2 months ago, # ^ |   0 +1 ( may be i am too bad to understand the statement (: )
 » 2 months ago, # |   0 problem D :( >>>> :) problem C
 » 2 months ago, # |   -17 Could not even get into codeforces/m1 codeforces/m2 codeforces during first 10 minutes!! Even after that it was loading wayyy too much. Then I panicked and could not even get B right for silly mistakes!!
 » 2 months ago, # |   -18 speedforces!!!!!!!!!!!!!!!!!!
 » 2 months ago, # |   0 Hi, Regarding problem D just to be sure I would like to confirm whether we are looking for a contiguous subarray or any subarray?Thank you very much!
•  » » 2 months ago, # ^ |   0 Go to problem set there you will find Ask a question ask there!
•  » » » 2 months ago, # ^ |   0 Hi, Thank you!
 » 2 months ago, # |   +31 Statement of C was very confusing :(
•  » » 2 months ago, # ^ |   +4 Yeah, like why use the word "die" in the statement. I missed the part where they are resurrected and all friendships restored. Wasted an hour trying to see what is wrong. Could've been much clearer with a better wording.
 » 2 months ago, # |   +10 Thanks for such an amazing round!
 » 2 months ago, # |   +1 Thanks for great round , solved upto C
 » 2 months ago, # |   -11 RuntimeErrorForces
 » 2 months ago, # |   0 Getting wrong answer at pretest(5) for D
•  » » 2 months ago, # ^ |   0 i think the mistake you are doing is for test case :-[3,4] here ans should be 1 but my code was giving 2 and get wa in test 5. so you can verify from this case.
•  » » » 2 months ago, # ^ |   0 it's giving 1
•  » » » » 2 months ago, # ^ |   0 I created the difference array, computed the gcd of subsequent terms, but it's giving wrong answer at pretest(5)
•  » » » » » 2 months ago, # ^ |   0 Which terms did you take to compute gcd?
•  » » » » » 2 months ago, # ^ | ← Rev. 2 →   0 welp, I can't read.
•  » » » » » » 2 months ago, # ^ |   0 It is guaranteed that all the numbers in a are distinct....
•  » » » » » » 2 months ago, # ^ |   0 elements are distinct
•  » » » » » » » 2 months ago, # ^ | ← Rev. 2 →   -61 .
•  » » » » » » » 2 months ago, # ^ |   0 Anyone can tell me why i got wrong answer my code. Because 2 and n/2 should be answer on problem A of question A and my loop can easily got n/2 value. void solve() { ll n; cin >> n; for (int i = 3; i < 1e6; i++) { if (n % 2 == n % i) { cout << 2 << " " << i << "\n"; return; } } } 
•  » » 2 months ago, # ^ |   +4 Does your code manage the case n=1? That was my problem.
 » 2 months ago, # |   +38 I submitted B first time right when CF crashed, then I went to one of the mirror sites, the submission wasn't showing up. I submitted again, only after that did the first submission show up. Both were TLE, so I got penalty for both. Is there a way to remove the penalty, considering it happened because of the crash? The codes were identical, which confirms my story.
•  » » 2 months ago, # ^ |   +20 The second submission has been removed, thank you!
•  » » 2 months ago, # ^ |   0 I have faced same problem like u
•  » » » 2 months ago, # ^ |   +5 I fixed all such cases automatically.
•  » » » » 2 months ago, # ^ |   0 Thank You so much for considering this❤️
•  » » 2 months ago, # ^ | ← Rev. 5 →   0 On the same question i submitted twice with just 31 sec gap one through codeforces website and second through m1.codeforces.com.First approach was correct so they took 50 points for resubmission.Those 54 points cause of codeforces crash is causing me 500 rank difference.The codes were identical, which confirms my story.Don't know why MikeMirzayanov is not looking into it.Maybe cause i am just a specialist. :(
 » 2 months ago, # |   0 Submitted a problem 2 mins ago.. still in queue
 » 2 months ago, # |   +51 cf predictor not showing results anyone has the same issue
•  » » 2 months ago, # ^ |   +6 +1
 » 2 months ago, # |   +41 Congrats antontrygubO_o you'll be LGM for the first time!
 » 2 months ago, # |   +11 the unclear problem c statement cost me -50 :( ,maybe they could have told something like "for type 3 queries, we want to give the number of invulnerable nobles, IF we start killing all vulnerable nobles till there are none left" maybe that could have helped
 » 2 months ago, # |   +5 How to solve D?
•  » » 2 months ago, # ^ |   +9 i think binary search can do it but my solution getting TLE
•  » » » 2 months ago, # ^ | ← Rev. 3 →   +5 i tried similar, detailed logiclets say for an sequence $A$ of integers $[a_1, a_2, a_3, ... a_n]$, there exists an integer $m \ge 2$ such that $a_i\bmod m = k$ for $1 \le i \le n$ where $k$ is a constant.that means $a_i \equiv a_{i+1} \bmod m$ for $1 \le i < n$.$\implies (a_{i+1}-a_i)\equiv 0 \bmod m$ for $1 \le i < n$.that implies that all consecutive differences in $A$ should be divisible by $m$ or $0$. Lets define another sequence $D$ of integers $[d_1, d_2, d_3 .. d_{n-1}]$ where $d_i = |a_{i+1}-a_i|$ for $1 \le i 1$. then there must be a $m > 1$. for which $a_i\bmod m = k$ for $1 \le i \le n$.Now, in problem we have to check $\binom{n}{2}$ such sequences if they satisfy this $m>1$ or not.We can easily observe that if $\text{gcd}(a, b, c, d)=1$ is true, then $\text{gcd}(a, b, c, d, \text{(any integer)})=1$ would also be true.so we can do binary search at every index $1 \le i \le n$ for an index $i \le j \le n$, such that sequence $[a_i, a_{i+1}, ... a_{j}]$ hold true for condition $m>1$ (which i wrote in paragraph of this explaination). this was my first attempt. but we can also use two pointer to find $i$ and $j$, and that should reduce total time complexity by a factor of $\log n$. but still i am getting TLE in attemp2. :(.attempt1complexity is $\mathcal{O}(n \space \log^2n \space \log{10^{18}})$, first log from binary search , second from segment tree query, third log from gcd function.that is not suffucient for $n = 10^5$. because $10^5 \times 20 \times 20 \times 60 = 2.4 \times 10^9$ that is high.So i did second attempt turning my binary search into two pointer.complexity is $\mathcal{O}(n\space\log{n}\space\log{10^{18}})$, first log from segment tree query and second from gcd function. this is similar to editorial's complexity. but still i am getting TLE and i am unable to figure where is it getting wrong. UPD: found it was a stupid mistake only and codes are working now.My stupid ass was building a segment tree of max size (2e5) for every test case. i didn't realized that it will be called from every test case. :(. and also missed n==1 base case.
•  » » » » 7 weeks ago, # ^ |   0 Can u please check my solution, I have used segtree+sliding window+gcd. Here is my solution https://codeforces.com/contest/1549/my
•  » » » » » 7 weeks ago, # ^ |   0 very first of all sorry for late reply.first of all , that is not sliding window, in sliding window we fix the width of window at first.you have implemented two pointer, same as mine (but slight differently). { min ran at <200ms all cases }i found one error in your code and three errors that have yet not gave you WA/RE. Error1void build(ll segtree[], vector diff, int vertex, ll start, ll end){ you are passing vector diff to build() by value.this will cause your program to copy all values of vector diff to another new vector diff of build() scope. and this will happen every time your code call build()because there will be $2n$ calls to build()and every time it will copy $n$ element of vector diff.this will cause to $2n^2$ unnecessary operations just to copy diff in every call.you can avoid this by writing following code: void build(ll segtree[], vector &diff, int vertex, ll start, ll end){ & specifies that this argument is called by reference and not by value. so it will not copy you vector diff rather just pass the regerence to original diff. hence will save of unnecessary $2n^2$ operations.This is where you are gettting TLE from. Error2 } ll segtree[4*n]; build(segtree,diff, 1, 0, n-2); ll ans = 1; ll s = 0, e = 0; here you are allocating space for segtree on stack memory. this will definately cause stack overflow and will give you RE. here is a video to know about allcoations.You can allocate this segtree array on global scope, that will save you from RE. Error3check your code what will happen when n==1. Error4 while(e < n-1){ if(diff[e] == 1){ s = ++e; currgcd = diff[e]; continue; } Here you are first checking if e < n-1 // size of diff arrayand then incrementing it in first if conditionand value of e could be n-1 in the line 4. this can cause RE.thats all what i could find out of first glance there could be more.
•  » » » » » » 7 weeks ago, # ^ |   0 Thanks for such a detailed error analysis. Finally, I was able to get AC in it.
•  » » » » » » » 7 weeks ago, # ^ |   +1 you are welcome.
•  » » 2 months ago, # ^ |   0 Computing the difference array and finding the gcd works (a-b)%m = 0 i.e a-b = k*m
•  » » 2 months ago, # ^ |   +13 Binary Search on answer + segment tree for range GCD. The segment tree gives TLE in Python so I used the Sparse table for that.
•  » » » 2 months ago, # ^ |   0 i realized it in last moment and couldn;t able to write whole code before time
•  » » 2 months ago, # ^ |   +9 Using two pointers work. The fact that the contiguous array of the difference array (array containing the differences of the original array) has to have gcd greater than 1 in order for a subarray to be good allows this approach (hopefully) works
•  » » » 2 months ago, # ^ |   0 I DID THAT, BUT GOT WA IN PRETEST(5)
•  » » » » 2 months ago, # ^ |   0 The funny thing is when I got WAs, I just resorted to good ol' #define int long long and it worked for me, but I got WA in pretest 7 so this may not be applicable for you.
•  » » 2 months ago, # ^ | ← Rev. 3 →   0 HintSparse Table + GCD + Two pointers SolutionLet's make an array b for differences a[i] — a[i — 1]. Now let's use the two pointers technique to find the largest subarray of b with gcd > 1. The answer is its length + 1. Code: Codeint my_gcd(int a, int b) { return (a == 0ll ? b : gcd(b % a, a)); } int st[200000][20]; void build(vector b) { for(int i = 0; i < len(b); i++) st[i][0] = b[i]; for(int j = 1; j < 20; j++) { for(int i = 0; i + (1 << j) <= len(b); i++) { st[i][j] = my_gcd(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]); } } } int query(int l, int r) { return my_gcd(st[l][log(r - l + 1)], st[r - (1 << log(r - l + 1)) + 1][log(r - l + 1)]); } void test_case() { int n; cin >> n; vector a(n); cin >> a; vector b(n - 1); for(int i = 1; i < n; i++) b[i - 1] = abs(a[i] - a[i - 1]); debug(b); build(b); int ans = 1; for(int L = 0, R = 0; R < n - 1; R++) { while(L < R && query(L, R) == 1) L++; if(query(L, R) != 1) ans = max(ans, R - L + 2); } cout << ans << "\n"; } 
•  » » 2 months ago, # ^ |   0 Video Solution for D, this is how i did it!
•  » » » 7 weeks ago, # ^ |   0 I have written the same solution, still getting the tle on tc-3, can u please check https://codeforces.com/contest/1549/my
 » 2 months ago, # |   +1 First contest where I was able to solve A, B and C. Maybe they were too easy but still.
 » 2 months ago, # | ← Rev. 2 →   +49 Problem C is actually very nice if perceived through generating functions. We're basically interested in the sequence generated by$F(x) = \sum\limits_{n_0=0}^n (x+1)^{3n_0}=\frac{(x+1)^{3(n+1)}-1}{(x+1)^3-1}$ Here numerator can be calculated in $O(n)$ after which $F(x)$ can be obtained by standard long division division also in $O(n)$.
•  » » 2 months ago, # ^ |   +5 I figured out a different method : Lets start at second s, and say last second is e, then S(x) = -C(3s,x+3) + C(3e+3, x+3) — 3*(S(x+2) + S(x+1)). This can also help in solving it on O(n) I think.
•  » » 2 months ago, # ^ |   +30 TL was very tight :')
 » 2 months ago, # |   +22 It seems like none of the testers spotted the easy solution of Div1D1.
•  » » 2 months ago, # ^ |   +16 What was the easy solution? I used pick's theorem for finding that number of boundary points should be multiple of 4.
•  » » » 2 months ago, # ^ | ← Rev. 2 →   +16 HintAfter that you can split the points into groups based on the x coordinate and the y coordinate's remainders modulo 4.
•  » » » » 2 months ago, # ^ |   +30 I'm pretty sure that was one of the intended solutions for D1.
•  » » » » » 2 months ago, # ^ |   +8 Then I don't know how it is harder than C...C is such a troll problem.
•  » » » » 2 months ago, # ^ |   +8 That's exactly what I submitted in testing... (Infact, mod 2 after diving all coordinates by 2)
 » 2 months ago, # | ← Rev. 3 →   +10 Time constraint on problem C is too tight I think. Just calculating factorials caused tle :(
 » 2 months ago, # | ← Rev. 3 →   0 A moment of silence for those who read the announcement about C after 1 hour from reading the problem including meEdit : it's actually my fault if i read the problem better i would have understood that but I did the same mistake again i should not hurry up solving before completely understanding the problem
•  » » 2 months ago, # ^ |   0 Damn! I didn't read it and got WA on pretest 4.
 » 2 months ago, # |   +17
•  » » 2 months ago, # ^ |   0 same :( ... Does anyone know what pretest5 was? Using 2 pointer approach. I did handle n=1 and 2 separately.
•  » » » 2 months ago, # ^ | ← Rev. 3 →   +1 I used segment tree (for gcd) on differences and then binary search to find longest length.
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 I cried for 30 minutes but then I realised..1 2 15 14(hope this testcase helps you pass pretest 5 :)
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   -10 Can u please check my solution, I have used segtree+sliding window+gcd. I am getting TLE at tc-3 Here is my solution https://codeforces.com/contest/1549/my
 » 2 months ago, # |   +52 Way too many points given to Div1D1/Div2F1 for its actual difficulty, in my opinion.
 » 2 months ago, # |   +3 Idk why but problem D seems to be easier for me.
•  » » 2 months ago, # ^ |   +3 Same :-)
•  » » 7 weeks ago, # ^ | ← Rev. 3 →   -13 Can u please check my solution, I have used segtree+sliding window+gcd. I am getting TLE at tc-3 Here is my solution https://codeforces.com/contest/1549/my
 » 2 months ago, # |   0 In my opinion, it was hard
 » 2 months ago, # |   -69 please try to avoid useless implementation problems like C.... couldn't the problem setters find any better problem??
•  » » 2 months ago, # ^ |   +20 You found it hard doesn't mean the problem was bad. And you can't just bash problem setters for the same.
•  » » » 2 months ago, # ^ |   -6 whether i find the problem hard or easy is irrelevant to the problem being bad... in my opinion that problem was just there to give people some typing practice
•  » » 2 months ago, # ^ |   +6 What implementation was there? The trick was to understand you only need to know how many nobles there are that are not friends with higher nobles. That's it. look at my solution...
•  » » 2 months ago, # ^ |   0 Why? The best way to train is to focus on your weakness and improve it, even I got a little bit tricky on problem C.
 » 2 months ago, # |   +1 lmao, I was 7th person to solve D, yet I struggled to solve B for an hour. I sometimes hate myself. :(
•  » » 2 months ago, # ^ |   0 i also struggled with B after solving d
 » 2 months ago, # | ← Rev. 2 →   -8 Sorry guys, please don't downvote >_<
 » 2 months ago, # |   0 Div2 Problem C was elegant! Enjoyed solving it!
 » 2 months ago, # |   0 How to solve B?
•  » » 2 months ago, # ^ |   +5 Check if you can kill enemy pawn in the same column, previous column (if enemy exists) and then next column (if enemy exists) for each pawn. Submission
•  » » » 2 months ago, # ^ |   0 thanks
•  » » » 2 months ago, # ^ |   +1 also keep updating those pawns that have already reached the end line.
 » 2 months ago, # |   0 I used Graph with Adjacency list implemented using a vector of sets, was getting TLE on pretest 4, what could be wrong?
•  » » 2 months ago, # ^ |   0 because adjacency list can go upto size of O(n^2).
 » 2 months ago, # | ← Rev. 2 →   +9 I have submitted solution for b twice within a interval of 30 seconds both the solutions are exactly same.Thing is when i was submitting my first solution the website crashed so i submitted again from m1.codeforces.com .I lost 54 points cause of that it would be great if someone can help me through this.MikeMirzayanov
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 At least MikeMirzayanov should look into it and update me.
•  » » » 2 months ago, # ^ |   0 Thanks MikeMirzayanov.Keep up the good work
 » 2 months ago, # | ← Rev. 2 →   0 In Problem Div2B, Solution passed the pretest when I used string instead of char array. Before it was giving wrong answer verdict for test case 5.Wasted 1hr. Any idea, why it happens? Passed — 124580177 Failed — 124546623
 » 2 months ago, # |   0 I am 'newbie' I have solve 2 question from div2 do I will get rated ?
•  » » 2 months ago, # ^ |   0 Yes for sure!! and welcome to codeforces
 » 2 months ago, # |   -18 WEIRD CODEFORCES COMPILER and WHY DOES THE CUSTOM INVOCATION EVEN EXIST DURING THE CONTESTS.(T_T)Hello Codeforces community,I joined codeforces recently but faced a weird issue in todays contest. In the problem C.Web of Lies.The answers to sample input were compiling and showing perfectly correct answer in my sublime code editor and even online on more than 5 different sites.BUT, I don't know what sort of a compiler does codeforces have (T_T) it always showed wrong answers on the sample test case.More over if I try to use the CUSTOM INVOCATION, it literally takes 10 minutes to compile 1 piece of code.WHAT TO DO IN SUCH A SITUATION, when all other compilers are showing correct result but codeforces compiler doesn't and the custom invocation is almost useless through out the contest.Please someone with prior experience EXPLAIN how to tackle.I know something must be wrong in my code.... BUT WHERE DO I DEBUG IT? (T_T)
•  » » 2 months ago, # ^ |   -9 Your profile pic is violating CF terms and conditions, consider changing it.
•  » » 2 months ago, # ^ |   0 I had a similar issue in the last two contests. Last contest was from going out of bounds in an array, and this contest was accessing a key that did not exist in a map. You probably have some type of runtime error
•  » » » 2 months ago, # ^ |   0 bro.. the answer is being printed... no errors. Just the answers don't match on cf compiler but matches on other compilers
•  » » » » 2 months ago, # ^ |   0 Mine printed answers too. Just different ones.
•  » » 2 months ago, # ^ |   0 Look, in some compilers, it ignores out of bounds or erasing elements not in the set and so on. but in Codeforces the compiler doesn't, it prints an unexpected answer. here are some tips when you face these problem: You can check your code on custom innovation (in the contest the custom invocation takes more time to compile because there are others in the contest that are submitting solutions but at any other time it works fine) Check if you call an index in the array which is bigger than size or smaller than 0 (out of bounds). Check if you are erasing or poping an element from a set, vector, queue, etc... and the size is 0 or the element that you are erasing doesn't exist Check for any overflows I think that you can find an offline compiler that is similar to custom invocation also if you are using CodeBlocks you can edit the settings to not ignore these problems
 » 2 months ago, # | ← Rev. 2 →   +3 Div1 B is basically same as this problem
 » 2 months ago, # |   0 How to solve Div 2D? please write your solution in hints.
•  » » 2 months ago, # ^ | ← Rev. 2 →   +3 Hint 1Difference array Hint 2Find the size of the largest subarray in the difference array which all elements have GCD>1 Hint 3Use two pointers
•  » » » 2 months ago, # ^ |   +2 I did the same thing. It failed pretest 5. Any idea what it could be?
•  » » » » 2 months ago, # ^ |   +3 I was stuck at pretest 5 TLE because i bugged two pointers inequality
•  » » » » 2 months ago, # ^ |   0 Maybe ? 1 1 1 
•  » » » » » 2 months ago, # ^ |   0 Ans is 1 right? I did handle n=1 and n=2 separately.
•  » » » » » » 2 months ago, # ^ |   0 not sure, I got two wrong answers because of that case :/
 » 2 months ago, # |   -15 I love your problems <3.E is #combinatoricsF is #geometry, Pick's theorem? I don't know for sure.Not only the topic you covered but also: Short, clear statements.You got my orz, sir!Waiting for the solution!
 » 2 months ago, # |   -10 Great Round! Thanks!
 » 2 months ago, # |   +9 I HATE GCD
•  » » 2 months ago, # ^ |   +40 I LOVE GCD
 » 2 months ago, # |   0 How to solve C ? I couldn't even get a clue after 1.5 hours
•  » » 2 months ago, # ^ |   +5 All you need to do is maintain $indegree$ for each vertex and add initial $vulnerable$ vertices in a set . For $query$ of type 3 $answer$ will be $n-vulnerable$ $points$. For type 1 $query$ increase $indegree$ of smaller vertex by 1 and add it to the set if not already added . For type 2 $query$ decrease $indegree$ of smaller vertex by 1 and remove it from set if it's $indegree$ after update becomes 0
•  » » » 2 months ago, # ^ |   +3 Oh.. Thanks a lot. I was doing something complicated unnecessarily
•  » » 2 months ago, # ^ |   0 Make a frequency array $f$, where $f_i$ represents how many nodes $j$ are greater than $i$. The answer is $n - k$, where $k$ represents the number of nodes $i$ where $f_i > 0$. For each $1$ operation, increase $f_u$, where $u < v$ by one. If $f_u$ was initially 0, then increase $k$ by one. For each $2$ operation, decrease $f_u$ by one. If $f_u$ was initially 1, then decrease $k$ by one. Code#include using namespace std; using ll = long long; using vi = vector; using vb = vector; using vl = vector; using pl = pair; using pi = pair; using vpl = vector; using vpi = vector; #define forn(i, n) for(int i = 0; i < n; i++) #define rofn(i, n) for(int i = n; i >= 0; i--) #define FOR(i, a, b) for(int i = a; i < b; i++) #define ROF(i, b, a) for(int i = b; i >= a; i--) #define TRAV(a, x) for(auto& a: x) #define ABC(c) for(char c = 'a'; c <= 'z'; c++) #define all(x) begin(x), end(x) #define sor(x) sort(all(x)) #define rsor(x) sort(all(x), greater()) #define rev(x) reverse(all(x)) #define pb push_back #define mp make_pair #define ins insert #define ub upper_bound #define lb lower_bound #define len(x) (int)(x).length() #define sz(x) (int)(x).size() #define f first #define s second #define dbg(x) TRAV(a, x) cout << a << " " void solve(){ int n, m; cin >> n >> m; vector worse(n + 1); int bad = 0; forn(i, m){ int u, v; cin >> u >> v; if(u > v) swap(u, v); if(!worse[u]) bad++; worse[u]++; } int q; cin >> q; forn(i, q){ int query; cin >> query; if(query == 1){ int u, v; cin >> u >> v; if(u > v) swap(u, v); if(worse[u] == 0) bad++; worse[u]++; } else if(query == 2){ int u, v; cin >> u >> v; if(u > v) swap(u, v); if(worse[u] == 1) bad--; worse[u]--; } else { cout << n - bad << endl; } } } int main(){ // int t; cin >> t; // FOR(i, 0, t){ // solve(); // } solve(); } 
•  » » » 2 months ago, # ^ | ← Rev. 4 →   -12 I submitted a similar solution during contest, but it failed pretest 4 as WA. Can someone help? 124599669 Edit: Just found out why. It was because I unnecessarily reset the states after doing query type 3.
 » 2 months ago, # |   0 Can anyone tell me, what's wrong in my code. my codeint n,m; cin>>n>>m; vectoradj[n+1]; for(int i=0;i>x>>y; adj[x].push_back(y); adj[y].push_back(x); } int has[n+1]={0},fam[n+1]={0}; for(int i=1;i<=n;i++) { int cc=0; for(auto it:adj[i]){ if(it>i && has[it]==0){ cc++; } } if(cc>0){ has[i]=1; } fam[i]=cc; } int cnt=0; for(int i=1;i<=n;i++) if(has[i]) cnt++; int q; cin>>q; while(q--) { int x; cin>>x; if(x==3) cout<>y>>z; if(x==1){ if(y>z && fam[z]==0 && has[z]==0){ cnt++; has[z]=1; } else if(yz) fam[z]++; if(z>y) fam[y]++; } else{ if(y>z && fam[z]==1 && has[z]==1){ cnt--; has[z]=0; fam[z]--; } else if(y
 » 2 months ago, # |   -6 Great problems!
 » 2 months ago, # |   -9 Great contest!
 » 2 months ago, # |   0 I really hope C task did not have any spoilers. T_T. Just started GOT. ><
 » 2 months ago, # |   +6 i like the sentence "the wolf does not eat the little pigs, he only makes plans"
 » 2 months ago, # |   0 Problem E: The three Little PigCan anyone suggest any improvement to my code other than taking mod of 1e9+7 while output ans1 so that it doesn't show TLE. 124595320
 » 2 months ago, # | ← Rev. 2 →   +3 is fft possible for d1c somehow? i understand that modulo is bad, but maybe it's possible with some magic
•  » » 2 months ago, # ^ |   0 Yeah, I designed the problem to be as hard as possible for FFT to pass. Maybe it works, IDK, but it would be a very very tight squeeze.
•  » » » 2 months ago, # ^ |   -10 Any particular reason for this choice? I don't think FFT-based deconvolution is any more or less interesting than the long division approach I ended up coding.
•  » » » 2 months ago, # ^ | ← Rev. 2 →   +2 It's barely even possible to calculate multiplicative inverses of $1, \ldots, 3N$. No way even a single $O(3N\log N)$ FFT would pass.Or so I thought...
•  » » » » 2 months ago, # ^ |   +23 You can use the formula $(n!)^{-1}=((n+1)!)^{-1}\cdot (n+1)$ to calculate multiplicative inverses of factorials in linear time, and thus multiplicative inverses in linear time.
•  » » » » » 2 months ago, # ^ |   +8 Ah, of course! I was always using the trick that $(2n)^{-1} = 2^{-1} n^{-1}$.
•  » » » » » 2 months ago, # ^ |   +5 Nice trick. I usually find inverse modulo $m$ for all numbers from 1 upto n with $i^{-1}=-[m/r] \times (m\%i)^{-1} (mod\, m)$ and then multiply them all together to get inverse factorials. (Proof can be found here: http://e-maxx.ru/algo/reverse_element#4 )
•  » » 2 months ago, # ^ |   +19 This works in 764ms.
 » 2 months ago, # |   0 For the last one hour I was stuck on D with this problem- "If I apply two-pointers on diff array, how can I find gcd of each segment?". At the last minute, it occurred to me that I can use Segment Tree. But it was too late by then. Looks like I have to practice more seg tree problems.Great Problems tho. Loved them all :)
•  » » 2 months ago, # ^ |   +9 Or if you are in the minority like me — use the sparse tables :P
•  » » » 2 months ago, # ^ |   0 I also used sparse tables. I still don't know how two pointers works
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   +1 Notice that for $i$ if it contributes to the final answer $f(i) >= f(i - 1)$ This essentially means that we should keep some suffix of the maximum result for $i$ in the result of $i + 1$. So just traverse left indices from $0$ to $n - 1$ and greedily try to match the maximum suffix of $i - 1$ to $i$. Take a look at my submission to understand it better.To practice this sort of things take a look at last educational round's E or CodeChef Lunchtime Div1A that was held yesterday. Both of them utilize two pointers in the same fashion this one does.
•  » » » » » 2 months ago, # ^ |   +1 Got it, thanks. I confused myself. I thought there was some raw two pointers magic to solve it without using sparse tables or segtree, but the two pointers is just the alternative to binary search
 » 2 months ago, # |   0 Thanks for the contest.
 » 2 months ago, # |   -11 Good questions, Good contest . Hope the pretests are strong !
 » 2 months ago, # |   +2 Why aren't they allowing segment trees to pass in D. I didn't knew about sparse tables.. :((
•  » » 2 months ago, # ^ |   +12 Actually I passed the pretests using segment tree
•  » » 2 months ago, # ^ |   +1 depends on whether you used binary search or 2 pointers
•  » » » 2 months ago, # ^ |   0 Yeah, I totally get it.. I should have used 2 pointers
•  » » » » 2 months ago, # ^ |   0 I have passed pretest(hopefully system test also) using binary search + segment tree
•  » » » » » 2 months ago, # ^ | ← Rev. 2 →   0 Pray for ACCEPTED ^)
 » 2 months ago, # |   +10 Editorial has been released!
•  » » 2 months ago, # ^ |   0 thanks for making a balanced contest. problems were really nice.
•  » » 2 months ago, # ^ |   +13 Thanks for a quick editorial!
 » 2 months ago, # |   +114 why the system tests are so slow?
•  » » 2 months ago, # ^ |   +17 seem like OJ is lazy today :)
 » 2 months ago, # | ← Rev. 2 →   +68 Seems like system testing stopped, does anyone now why?
 » 2 months ago, # |   +33 Cool contest!Is it just me or did the expected rating calculator break during contest?
•  » » 2 months ago, # ^ |   +3 Yeah, it was broken throughout the whole contest for me
•  » » 2 months ago, # ^ |   +30 Because the server banned the API for rating calculator during the contest,so everyone was affected.
 » 2 months ago, # | ← Rev. 2 →   -40 Problem C- Web lies My code is giving memory limit exceed on pretest 4 Can anyone give an efficient solution ? so that i can check where I did wrong. submission :- 124601371
•  » » 2 months ago, # ^ |   +3 paste your code and run it on (https://ideone.com/) and share the link . It is very difficult for anybody to read your code now.
•  » » 2 months ago, # ^ |   0 You seem to be using an adjacency matrix to represent your graph, which has O(n^2) space complexity. Try using an adjacency list instead.
 » 2 months ago, # |   +5 system testing is teasing now !
 » 2 months ago, # |   +77 Come on guys, technical issues are unavoidable but at least you need to communicate. Or are we due for another donation campaign?
 » 2 months ago, # | ← Rev. 3 →   +14 It was great to listening to Light of the seven while reading C.Web of Lies. that's why my fantasy drived me far away from the solution.
•  » » 2 months ago, # ^ |   +3 I was getting constant GOT nostalgia while solving D2C.
 » 2 months ago, # |   +3 Best editorials <3
 » 2 months ago, # |   0 when it is possible to virtually participate?
•  » » 2 months ago, # ^ |   0 Anytime after a round is completely over.
 » 2 months ago, # |   +24 Why is system testing slower than my learning rate?
 » 2 months ago, # |   0 I am waiting for hacking
 » 2 months ago, # |   +7 Was someone as savage as me to submit a flow solution to div2B? XD
•  » » 2 months ago, # ^ |   -8 I believe no XD
•  » » 2 months ago, # ^ |   +3 Hopcroft-Karp-Karzanov algorithm with some optimization might pass the tests within the time limit. Because the number of edges will be at most 3n.
•  » » » 2 months ago, # ^ |   0 Yes, sure. With Max flow I meant the max matching approach.
•  » » 2 months ago, # ^ |   +3 I did XD
 » 2 months ago, # |   +8 SAAAAAAAAAAD man! I got MLE in problem D for not handling the case n=1 as I was using Segment tree. Even though I don't know why it gives MLE I think in this problem, it should give a runtime error.
•  » » 2 months ago, # ^ |   0 Same. Not handling n=1 case. And got MLE. (╯︵╰,)
•  » » 2 months ago, # ^ | ← Rev. 3 →   0 Same didn't realized that until I saw your comment, I thought maybe $4N$ was too large but fortunately writing iterative segment tree worked it didn't required handling $n=1$ case separately.
•  » » » 2 months ago, # ^ |   0 I was thinking the same as you, typically! but the problem is that the contest ends before I finished writing the iterative segment tree as I haven't trained before on the iterative ones.
 » 2 months ago, # |   +3 Time taken for system testing == Number of times the site crashed
•  » » 2 months ago, # ^ |   0 You didn't even took part in the contest, what system testing are you waiting for?
 » 2 months ago, # |   -13 I submitted A first time right when CF crashed, then I went to one of the mirror sites Codeforces3, the submission wasn't showing up. I submitted again, only after that did the first submission show up. so my first solution was skipped last solution wask taken. Is there a way to remove the last submissions, considering it happened because of the crash? The codes were identical, which confirms my story.→ Reply
•  » » 2 months ago, # ^ |   0 As a newcomer it's really frustrating for me. I think CF CF team will consider my situation.Thank you
•  » » » 2 months ago, # ^ |   +3 Apparently you can't resubmit your same code.
•  » » 2 months ago, # ^ |   +6 You literally copy-paste this comment and moreover, YOU FORGOT TO ERASE THE "→ Reply" text
•  » » » 2 months ago, # ^ |   0 Bro i have faced the same problem but my english isn’t good at al so i copy past his comment.is there any problem.
•  » » 2 months ago, # ^ |   +34 Come on, at least make an efford
•  » » » 2 months ago, # ^ |   +13 Hehe nice, imitation is the sincerest form of flattery...
•  » » » » 2 months ago, # ^ |   +5 I replied it in your comment that i have faced the same problem like you.My english isn't good so i decided to copy your.by the way give me some pro tips that how can i be a master like you?
•  » » » » » 2 months ago, # ^ |   +21 No worries, I just found it funny. There aren't many pro tips I can give you, but here are a few notes for you current level: 1) don't focus on known algorithms, you will never see them in div2 A and B problems 2) focus on coding and learning to debug efficiently (you will always make mistakes) 3) always upsolve problems A, B and sometimes C from rounds, if you miss a round try to do it virtually. Biggest tip is to have fun and don't worry too much about rating. You are at a point where much improvement is possible. Best of luck!
•  » » » » » » 2 months ago, # ^ |   0 Thanks for your valuable suggestions❤️
•  » » » » » » » 2 months ago, # ^ |   -6 Anyone can tell me why i got wrong answer my code. Because 2 and n/2 should be answer on problem A of question A and my loop can easily got n/2 value. void solve() { ll n; cin >> n; for (int i = 3; i < 1e6; i++) { if (n % 2 == n % i) { cout << 2 << " " << i << "\n"; return; } } } `
•  » » » » » » » » 2 months ago, # ^ |   0 Try 10000223
•  » » » » » » » » » 2 months ago, # ^ |   0 Yeah, i got it thanks :).
•  » » » » » » 2 months ago, # ^ |   0 what a person should focus on if the person can solve A,B,C(sometimes) in contest. Upsolve C,D ? or something else
•  » » » » » » » 2 months ago, # ^ |   0 If you're high pupil/specialist and solve ABC, at that point you should start learning some very basic algorithms, maybe about graphs (not above DFS and BFS!) and dp (again, nothing too complicated). Always upsolve C and D (D might be a bit hard, but try to read the solution anyways). If you're solving ABC and you're not at least high pupil, you should still follow the last plan and practice more coding.
•  » » » » » » » »