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:

- Aleks5d, for awesome coordination of my round.
- Benq, for extensive testing and contributions throughout the round, especially for 1548E - Gregor and the Two Painters.
- Monogon, for discussing problems and statements with me for hours on Discord.
- amgfrthsp, for translating statements into Russian.
- 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!

- Benq, hos.lyric, ecnerwala, Um_nik
- TadijaSebez, Monogon, galen_colin, Tlatoani, dorijanlendvaj, rqi
- emorgan5289, TheOneYouWant
- penguinhacker, ptd, AquaMoon
- ajpiano, arvindr9, ijxjdjd
- wxhtzdy, nnv-nick, alexwice, gupta_samarth
- MoonKnight., 4qqqq, gerzytet, growup974, NemanjaSo2005
- RobinPH, zyzzsama, SlavicG
- QuangBuiCP
- tdpencil

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)

## UPD: Editorial

## Winners

Congratulations to all our winners in the round!

#### Div1

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

#### Div2

#### Fastest Solves

- 1549A - Gregor and Cryptography: robivirt at 53 seconds!
- 1549B - Gregor and the Pawn Game: speedforces at 4 minutes!
- 1548A - Web of Lies: tourist at 3 minutes!
- 1548B - Integers Have Friends: tourist at 7 minutes!
- 1548C - The Three Little Pigs: gisp_zjz at 19 minutes!
- 1548D1 - Gregor and the Odd Cows (Easy): tourist at 20 minutes!
- 1548D2 - Gregor and the Odd Cows (Hard): tourist at 65 minutes!
- 1548E - Gregor and the Two Painters: mango_lassi at 80 minutes!

Thanks for the early score distribution!

Yeah no problem!

There's no reason to needlessly hide the score distribution.

2 hour 16 min

Newbie Testers Go Hereanyways I'm excited for this contest good luck to all those who are planning on participating

can newbies be testers?

Yes.

anyone can be a tester if he/she is a trustable friend of the author or the author himself asked someone for testing

I hope to be solved at least two problems...

Codeforces, sorry for my comment, I will not write comments like this anymore. :(

Div 2 Speedforces incoming

SpoilerAs a tester, let me participate officially

Spoilerupvote for +100 delta

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 :)

Discrimination of testers on the basis of colour :(

"#justice_for_testers" XD

tester lives matter

As a tester, problems are great!

`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...

As a VIP tester I recommend everyone to gain rating!

purplecrayon is purple :<

Spoilerpurplecrayon is actually a crayon :O

What about DioHERO?

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!

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

I miss u brother :(

Thanks for a great set of problems. I recommend everyone to participate and gain rating! OMG My first "As a tester..." comment

I recommend you to participate and be master again :P

Am I the Only One who Read

** OMG My first "As a tester..." comment**... In this comment?No

How to write an invisible text? (OMG My first "As a tester..." comment)

Use some html, I did

`<font color="white"> insert_text_here </font>`

Thanks

I hope to become specialist after this round

i want to do D nothing else matters, focus on action rather than outcome

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

Expectations: (see above) Reality: I solve contests to gain my rating (It's just a joke, don't be so serious <3)

lighthearted memei am at 1399 , i was hurt by this lighthearted meme

Good to see that Problem A is of 500 again

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?

There is no certainity about difficulty of a problem on the basis of a its score in the contest.

Thanks :) Hope to solve till C!!

Scoring distribution is a hint to how hard the problem is, but it doesn't necessarily signify difficulty.

is Div2 for people <1900 or <2100 ? in these rounds.

<1900

I don't know what's the benefit of ratings distribution. Problems will come and

~~ratings~~will go.Good job

You should provide model solution in python too .

You got "rainbow" of testers, but not "rainboy". That might have led to unusual round ;)

That unusual round might have a scoring distribution like :

`(2500 - 2000 ) -2500 - 2000 - 1250 - 750 - 500`

Now I wonder what will happen when the contest starts...

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

If so he can submit in div2 till pretest passed to avoid penalties in div1.

Well, I have seen a participant in situation like this, and he said 404 Error was displayed when contest started :D

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(

Thx for nice score distribution;)

Tester squad from Errichto's Discord!!

Hope the problems with the scoring distribution 2000 will be like in previous round(not educational)

ahahah that problem D in round 735?) yeah, it was to ooverrated, should be like 1000

Hope the Difficulty level will not be like last Codeforces Round #735

PS: Puplis Like Me need +ve Delta :)

i feel like i was at fault at that round , b wasn,t that hard i realise now

and thanks MikeMirzayanov for this amazing platform

You could have said it without tagging him :|

Umm... Lemme edit

Why so many downvotes people? He changed his comment :(

In this announcement

Total comments = 32

Tester's comments = 69

Going to participate from

beyond the wall.As a non-tester, I will participate this round!

Positive post

I would like to be a newbie tester.(and I will solve 0 problems)

2000 points for div1C OMG

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.

Hoping for a good round.

Again I will participate and not answer anything . Cause this one be !easy too ...

Hope the round will be interesting and i will cross 1350

![ ]()

rainbow follows VIBGYOR btw

Thanks for putting effort for this round! Also hint-based editorial is nice :)

`Newbie Testers Go Here`

POV: Newbie

contestants are testersfor future contests.I hope the problem statements are short and the pretests are strong.

Thank you, the pretests are strong!!

I hope I become specialist after this one.

Best of luck, you are near at specialist

Thank you so much!!

I Like Div2-735 round because of short statement and more interesting problem. Hope this round will be more interesting. );

dont bomb the contest

I don't bomb on innocent platform like (Codeforces). Cz, Everybody loves it. I also love it.

Is Codeforces halal, probably not

I think, you should focus on yourself brother. It is not debating site.);

bin laden is a terrotist there is no debating

I'm exiting about the round. Thank You.

I trust a Game of Thrones fan

SpoilerDid the newbie testers outperform the experts?

As a tester, I can confirm that this round has good problems and I hope that you will enjoy it

I am really excited about it. By the way, how can someone become a problem test. Just asking out of curiosity.

You can be a tester if you're a trusted friend of the author of the contest.

I hope I can solve the problem of 3 quickly

I hope i don't struggle with B again

First round in August! Excited!

https://millionaire.fandom.com/wiki/Shiva_Oswal

Agnimandur is it you? Amazing!

Agnimandur orz!

“regardless of your rating!”I hope so,but it keeps decreasing.T_T

so div1 has only one harder problem than div2? maybe it should have been div(1+2) in this case

Count again, for me it looks like the usual two.

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?

Ah, ok, I see.

good luck competitors.

Loved the testers section..

What with the rating of E, is it easier than D?

Better than contest with 750 as first problem :)

Oh f I just realised that you are shiva oswal ,champion of history bee tournament , see this, orz

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.

Well Balanced Round. Thank you writers and testers :)

First few minutes problem statements to me (In m2 and m3. not able to check m1.)Your text to link here...

I hate div 2 C.

///

thank god i got it finally, wish the same for you guys. But the contest was surely very well made.

+1 ( may be i am too bad to understand the statement (: )

problem D :( >>>> :) problem C

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!!

speedforces!!!!!!!!!!!!!!!!!!

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!

Go to problem set there you will find Ask a question ask there!

Hi, Thank you!

Statement of C was very confusing :(

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.

Thanks for such an amazing round!

Thanks for great round , solved upto C

RuntimeErrorForces

Getting wrong answer at pretest(5) for D

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.

it's giving 1

I created the difference array, computed the gcd of subsequent terms, but it's giving wrong answer at pretest(5)

Which terms did you take to compute gcd?

welp, I can't read.

It is guaranteed that all the numbers in a are distinct.

...

elements are distinct

.

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.

Does your code manage the case n=1? That was my problem.

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.

The second submission has been removed, thank you!

I have faced same problem like u

I fixed all such cases automatically.

Thank You so much for considering this❤️

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. :(

Submitted a problem 2 mins ago.. still in queue

cf predictor not showing results anyone has the same issue

+1

Congrats antontrygubO_o you'll be LGM for the first time!

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

How to solve D?

i think binary search can do it but my solution getting TLE

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 <n$$$. its clear to see now that $$$\text{gcd}(d_1, d_2, d_3, .. d_{n-1})$$$ will be a multiple of $$$m$$$. (Because all elements of d should be multiple of $$$m$$$ or $$$0$$$)

so we know if gcd of consecutive differences in array elements is $$$> 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. :(.

attempt1

complexity 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.

attempt2.

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.

Can u please check my solution, I have used segtree+sliding window+gcd. Here is my solution https://codeforces.com/contest/1549/my

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.

Error1you are passing

`vector<ll> diff`

to`build()`

by value.this will cause your program to copy all values of

`vector<ll> diff`

to another new`vector<ll> 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<ll> diff`

.this will cause to $$$2n^2$$$ unnecessary operations just to copy diff in every call.

you can avoid this by writing following code:

`&`

specifies that this argument is called by reference and not by value. so it will not copy you`vector<ll> 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.Error2here 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`

.Error4Here you are first checking if e < n-1 // size of diff array

and then incrementing it in first if condition

and 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.

Thanks for such a detailed error analysis. Finally, I was able to get AC in it.

you are welcome.

Computing the difference array and finding the gcd works (a-b)%m = 0 i.e a-b = k*m

Binary Search on answer + segment tree for range GCD. The segment tree gives TLE in Python so I used the Sparse table for that.

i realized it in last moment and couldn;t able to write whole code before time

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

I DID THAT, BUT GOT WA IN PRETEST(5)

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.

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:

CodeVideo Solution for D, this is how i did it!

I have written the same solution, still getting the tle on tc-3, can u please check https://codeforces.com/contest/1549/my

First contest where I was able to solve A, B and C. Maybe they were too easy but still.

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)$$$.

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.

TL was very tight :')

It seems like none of the testers spotted the easy solution of Div1D1.

What was the easy solution? I used pick's theorem for finding that number of boundary points should be multiple of 4.

HintAfter that you can split the points into groups based on the x coordinate and the y coordinate's remainders modulo 4.

I'm pretty sure that was one of the intended solutions for D1.

Then I don't know how it is harder than C...

C is such a troll problem.

That's exactly what I submitted in testing... (Infact, mod 2 after diving all coordinates by 2)

Time constraint on problem C is too tight I think. Just calculating factorials caused tle :(

A moment of silence for those who read the announcement about C after 1 hour from reading the problem including me

Edit : 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

Damn! I didn't read it and got WA on pretest 4.

same :( ...

Does anyone know what pretest5 was? Using 2 pointer approach. I did handle n=1 and 2 separately.

I used segment tree (for gcd) on differences and then binary search to find longest length.

I cried for 30 minutes but then I realised..

1 2 15 14

(hope this testcase helps you pass pretest 5 :)

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

Way too many points given to Div1D1/Div2F1 for its actual difficulty, in my opinion.

Idk why but problem D seems to be easier for me.

Same :-)

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

In my opinion, it was hard

please try to avoid useless implementation problems like C.... couldn't the problem setters find any better problem??

You found it hard doesn't mean the problem was bad. And you can't just bash problem setters for the same.

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

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...

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.

lmao, I was 7th person to solve D, yet I struggled to solve B for an hour. I sometimes hate myself. :(

i also struggled with B after solving d

Sorry guys, please don't downvote >_<

Div2 Problem C was elegant! Enjoyed solving it!

How to solve B?

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

thanks

also keep updating those pawns that have already reached the end line.

I used Graph with Adjacency list implemented using a vector of sets, was getting TLE on pretest 4, what could be wrong?

because adjacency list can go upto size of O(n^2).

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

At least MikeMirzayanov should look into it and update me.

Thanks MikeMirzayanov.Keep up the good work

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

I am 'newbie' I have solve 2 question from div2 do I will get rated ?

Yes for sure!! and welcome to codeforces

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)

Your profile pic is violating CF terms and conditions, consider changing it.

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

bro.. the answer is being printed... no errors. Just the answers don't match on cf compiler but matches on other compilers

Mine printed answers too. Just different ones.

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:

Div1 B is basically same as this problem

How to solve Div 2D? please write your solution in hints.

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

I did the same thing. It failed pretest 5. Any idea what it could be?

I was stuck at pretest 5 TLE because i bugged two pointers inequality

Maybe ?

Ans is 1 right? I did handle n=1 and n=2 separately.

not sure, I got two wrong answers because of that case :/

I love your problems <3.

E is #combinatorics

F 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!

Great Round! Thanks!

I HATE GCD

I LOVE GCD

How to solve C ? I couldn't even get a clue after 1.5 hours

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 0Oh.. Thanks a lot. I was doing something complicated unnecessarily

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.

CodeI 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.

Can anyone tell me, what's wrong in my code.

my codeGreat problems!

Great contest!

I really hope C task did not have any spoilers. T_T. Just started GOT. ><

i like the sentence "the wolf does not eat the little pigs, he only makes plans"

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

is fft possible for d1c somehow? i understand that modulo is bad, but maybe it's possible with some magic

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.

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.

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...

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.

Ah, of course! I was always using the trick that $$$(2n)^{-1} = 2^{-1} n^{-1}$$$.

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 )

This works in 764ms.

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 :)

Or if you are in the minority like me — use the sparse tables :P

I also used sparse tables. I still don't know how two pointers works

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.

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

Thanks for the contest.

Good questions, Good contest . Hope the pretests are strong !

Why aren't they allowing segment trees to pass in D. I didn't knew about sparse tables.. :((

Actually I passed the pretests using segment tree

depends on whether you used binary search or 2 pointers

Yeah, I totally get it.. I should have used 2 pointers

I have passed pretest(hopefully system test also) using binary search + segment tree

Pray for ACCEPTED ^)

Editorial has been released!

thanks for making a balanced contest. problems were really nice.

Thanks for a quick editorial!

why the system tests are so slow?

seem like OJ is lazy today :)

Seems like system testing stopped, does anyone now why?

Cool contest!

Is it just me or did the expected rating calculator break during contest?

Yeah, it was broken throughout the whole contest for me

Because the server banned the API for rating calculator during the contest,so everyone was affected.

Problem C- Web liesMy 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 :- 124601371paste your code and run it on (https://ideone.com/) and share the link . It is very difficult for anybody to read your code now.

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.

system testing is teasing now !

Come on guys, technical issues are unavoidable but at least you need to communicate. Or are we due for another donation campaign?

It was great to listening to

Light of the sevenwhile readingC.Web of Lies. that's why my fantasy drived me far away from the solution.I was getting constant GOT nostalgia while solving D2C.

Best editorials <3

when it is possible to virtually participate?

Anytime after a round is completely over.

Why is system testing slower than my learning rate?

I am waiting for hacking

Was someone as savage as me to submit a flow solution to div2B? XD

I believe no XD

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.

Yes, sure. With Max flow I meant the max matching approach.

I did XD

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.

Same. Not handling n=1 case. And got MLE. (╯︵╰,)

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.

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.

Time taken for system testing == Number of times the site crashed

You didn't even took part in the contest, what system testing are you waiting for?

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

As a newcomer it's really frustrating for me. I think CF CF team will consider my situation.Thank you

Apparently you can't resubmit your same code.

You literally copy-paste this comment and moreover, YOU FORGOT TO ERASE THE "→ Reply" text

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.

Come on, at least make an efford

Hehe nice, imitation is the sincerest form of flattery...

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?

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!

Thanks for your valuable suggestions❤️

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.

Try 10000223

Yeah, i got it thanks :).

what a person should focus on if the person can solve A,B,C(sometimes) in contest. Upsolve C,D ? or something else

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.

Yeah I need to learn DP. Thanks for guiding.