Hello Codeforces!

On Jan/29/2021 17:35 (Moscow time) Educational Codeforces Round 103 (Rated for Div. 2) will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be **rated for the participants with rating lower than 2100**. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given **6 or 7 problems** and **2 hours** to solve them.

The problems were invented and prepared by Roman Roms Glazov, Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

Congratulations to the winners:

Rank | Competitor | Problems Solved | Penalty |
---|---|---|---|

1 | sometimesnaive | 6 | 176 |

2 | SSRS_ | 6 | 184 |

3 | flowerletter | 6 | 251 |

4 | hank55663 | 6 | 255 |

5 | Strigon-12 | 6 | 276 |

Congratulations to the best hackers:

Rank | Competitor | Hack Count |
---|---|---|

1 | stdmultiset | 133:-79 |

2 | Tsovak | 98:-10 |

3 | dapingguo8 | 68:-6 |

4 | MohamedAboOkail | 65:-3 |

5 | peti1234 | 60:-1 |

And finally people who were the first to solve each problem:

Problem | Competitor | Penalty |
---|---|---|

A | Warawreh | 0:01 |

B | MysteryGuy2 | 0:04 |

C | WZYYN | 0:10 |

D | peti1234 | 0:09 |

E | CoderAnshu | 0:06 |

F | - | - |

G | iaNTU | 0:57 |

**UPD:** Editorial is out

Please please please don't make it as hard as today's contest :/

Please don't do that, don't give me hope :)

:(

As a ......

Do you want to get more contribution?say "as a"?

i think u mean negative

He couldn't complete his sentence. Perhaps some big stone fell on him while he was typing. Sad.

Your ideas are ...

Did a stone fell on you too OR .....

And a small pebble fell on the "." key?

Let the comments with "as a" begin

I am new to Competitive programming, codeforces made me fall in love with it! Thanks to you all amazing people!

yes same

i tried everything to find my interests and nothing felt like i enjoy doing them

as i started CP on codeforces 2 months back i feel like this is all i want to do for the next large amount of my time :) really thankful to the best internet community

Same brother, initially I thought to first finish all Data Structures and Algorithms and then start CP, but doing it simultaneously is much better and helps retain concepts easily. Every new coder should start doing CP. (PS: Only if you don't mind your ratings dropping and you trust yourself enough, that one day, you'll make it.)

so Madara Uchiha saved you, huh.

I killed him!

But I think you were there to bring him back to life!!

I killed OrochiMaru, Itachi

no you didn't foolish kid.

As a participant of today's contest kindly make the problems easier...

I hope it will be a good round

Hope for the nice contest!

Lunch time is 30th right So no clash

I will die if there will be adhoc problems in this contest too.

Hahahhah did you also get burned by today's contest?

educational=(4problems or more)*adhoc XD

That's a pretty bad equation, not gonna lie.

what is adhoc?

adhoc problems usually ask you to construct or to build something. Usually those problems can be solved without knowledge of algorithms. For example, you can check problem F from codeforces Round 640 div4. This is an example of ad-hoc problem.

would adhoc be considered to be general-thinking problems?

The problems on which you die thinking which algorithm to use while contest and then after looking at the editorial think .. "wait ... thats it ?"

You mean, the less you know, the better off you are?

Hope,I will enjoy this round as today!

My current rating is 401 will I be rated in this contest?

cout << "YES\n";

Bro I am new to codeforces, please tell me based on my rating which all contest can I participate and be rated ?( Like div 1,2,3)

Div 2,3,Educational,Div1+Div2(combined rounds).

Thanks bro

cout << (401 < 2100 ? "YES" : "NO") << '\n';

Yes

I am a newbie, it really made me happy that I could solve few problems. Looking forward to upcoming contests!

those who dont want jobs out of it will loose hope soon

Well not getting a job when you are working hard is depressing but you have to believe in yourself, it can do miracles

well, recently a newbie girl I know received an offer from FAANG.

I am neither a newbie nor a girl, darkness awaits me.

alright master man help me with my code please.. SEQ SPOJ i am getting WA i have spent the whole day trying to do this. doesn't work. any help is much appreciated. here is my code http://pastie.org/p/5RMR3nVahDVmrvyAUTIonz. nvm i solved it.

I'm in high school and do CP. And there are many others who don't want a job out of it. Problem-solving using DSA is fun!

well i am 2 nd year electrical engineer i do it to keep my brain sharp but our job is decided by such factors we tend to target on this site it all connects.and if u cant get anything out of it u will decay soon thats what i meant

Depends on how you define 'anything'. For many people, there are more things in life apart from getting a job.

well u can eat sometimes without being hundry good for you

don't tell u have never eaten something even tho u were full? CP is a sport. Many people play football or any other sport without wanting to play for a club or a country.

what would u call the release of serotonin when u win and the thrill when u loose ,u can eat but when u loose its the hunger that make u move forward ,ofcourse i am speaking on avg not on individual level but thats a fact

Why are you so cute :')

I hope i will become expert today..

hope i remain specialist today:)

hope i will become master one day:)

hope

Hope to become specialist today

Are you planning to cheat?

no i am not like you

Hope the tasks aren't too hard, hope everyone can get a rating which can satisfy you :)

There should be a third button IMO XD

There was but it got deprecated: HackForces. Now it's only present on Topcoder with name TopHacker.

Doesn't look like it.

I meant for usual div 2 rounds. Usually educational rounds have more hacks because of longer and separate hacking phase.

MathForces!

Oh just saw you already said it thanks a lot! Can we be friends?

And a forth: MathForces...

I hope i can solve first 2 problems quickly :)

come on!

Writing educational contests is really good way to develop. Thank you for this contest and good luck to everyone!

Hey Legend tell me how can i improve my skill on number theory ? in previous contest after lot of observation still i am not able to solve 3 and 4th problem

hoping it to be a hard contest (and not containing math only ;-;)

(

This feels deep. You have my upvote sir

Hello LostCow!!!

Happened yesterday :) ...

Hope this does not happen to me today .

This is the most relatable meme I've seen on codeforces. Especially after yesterday's contest and today's.

Couldn't relate more!

Lose, not loose.

Waiting for the contest which would take me to specialist :)

time to become green (hopefully)

It will be a wonderful contest. Best wishes!

My chance for specialist.

As a contestant I wish you ALL THE BEST

please help me to find error in this https://codeforces.com/contest/1478/submission/105847952

Hoping for a good contest!!

Giving a contest after long time today ! Fingers Crossed..

Best of luck to all :)

A and B kinda sucked ngl

before contest i was confident that i will be successfull in protecting my specialist badge. after contest i am confident i will be successfull in getting demotion to pupil

My condition is also the same Brother.

Yeah, but I thought C and D made up for it!

Fu**ing B costed me 7 WA because of floats.

That is why you should always work in integers if possible, if you are comparing $$$\frac{a}{b}\ge{\frac{c}{d}}$$$, compare $$${ad\ge{bc}}$$$ instead. Watch some people like Errichto and you will pick up these things, it helps a lot.

the idiot tottered happily towards grey coder againIt's me I'm the idiot :)

is educational contest rated for all or only for div2?

only for div2

B — balanced

I wasted literary 1 hour on problem C because I forgot typing else... GG I will always be silver...

How to solve C?

I solved C considering three cases:

If we are at index 0, we only have one option, i.e. to start a cycle from here.

If we are at the last index, we only have one option, i.e. to end the current cycle.

If we are at an index in the middle: We check if b[index+1] == a[index+1].

`Number_of_vertices[index] - 1 - (b[index+1] - a[index+1])`

.`b[index+1] - a[index+1]`

.`Number_of_vertices[index] - 1`

.Link to code: https://codeforces.com/contest/1476/submission/105933562

Fixed. I didn't handle the 6th case well.

I did same still got WA on test case 3, Can you help? The code is easy enough to understand.

Here's my code see if that helps.

Firsty, I think that you have messed up the implementation in the if-else condition.

`1 - a[i+1] + c[i] - b[i+1]`

which should actually be`c[i] - 1 - b[i+1] + a[i+1]`

.Link to the submission: https://codeforces.com/contest/1476/submission/105949955

Hope it helps!

You can use some dp to store maximum length cycle including all vertices of a[i] as ans[i].

See my solution:https://codeforces.com/contest/1476/submission/105907608

It can be solved by dp; firstly, let

`dp[i]`

denote the longest length at`i`

th chain, "the longest length" means the longest length you can get before the cycle is formed, so we can get`dp[i]=max(dp[i-1]+c[i]-1-abs(a[i+1]-b[i+1])+2,abs(a[i+1]-b[i+1]))`

, then we update the answer by`dp[i-1]+c[i]+1`

. one thing to be noticed is that when`a[i+1]=b[i+1]`

,`dp[i]`

should set to`0`

.I just realized my approach wasn't greedy at all. It's just DP without a DP array. Yeah, I solved it btw.

Was I the only one who went into C and D thinking that they are graph problems, but both of them turned out to be dp ones? :P

I thought so, but after seeing that the length of the chain can be 1e9, I knew it wasn't a graph problem.

Yes, C isn't greedy.

There might be a greedy algorithm to it, but I solved it by trying all possibilities using dp

I think it's greedy I got AC using greedy.

Nice, I also did greedy but it failed on testcase 3.

I failed on testcase 3 also in 1st attempt , you're probably missing the edge case.

can you tell the edge case your code failed the first time? I can't understand the logic of why you put the cur=max(cur,y-x+1); in your passed attempt.

See this link

Thank you. For some reason, I thought that this case is covered on ans=max(ans,cur+c[i-1]); this part of your code. Thank you

Yeah, I need to learn to write clean code ;), I put so many max conditions that were not necessary at all xd.

there is not much difference between greedy and dp in this problem because you are accessing only the values from the previous index.

I solved it using greedy.

Could you tell me your approach?

You can refer to this comment: https://codeforces.com/blog/entry/87282?#comment-755104

How to solve D?

Note that the structure of the graph only depends on the parity of time elapsed. Therefore, we can use $$$(node, parity)$$$ as stage and use DSU to maintain the reach-ability between stages and the sizes of connected components.

Make a left_c and a right_c array which represents the maximum number of cities city i can traverse that lie strictly on it's left and it's right respectively.

Then, notice that if there lies a path b/w city i and city i-2, then city i can traverse all those different cities that city i-2 can because at time t and time t+2, all paths are exactly the same. If there just exists a path b/w city city i, and city i-1, then increment one to the left_c array for the city i. And, do similar things for right_c.

Answer for the i_th city is left_c[i]+right_c[i]+1

You can check my submission

Okay,understood! Thanks for the explanation!

What means "b/w city"?

between city*

My idea was the same. You can check my implementation with regex (with eval-groups inside) — 105956225.

How to solve A? I'm new here...

take range of get the smallest number x with x*n >= k

or if n > k : x*n >= ceil(n/k)*k

How to think for such solutions?

"disclaim: It took long time for me :("

-the first observation is that the smallest value for n positions is : 1n,2n,3n,4n, ...

say you have n = 3 and k = 11 => 1,6,9,12 , 15,... you can get 11 by replacing 4 by three 4,4,4,3.

-so you can get any lower values of x*n by replacing on or more x by lower value

you should take into account n > k

Comment section is filled with amazing people! It's motivating :)

watch the stream, it's very helpful

nope.

Lets consider two cases:

`n >= k`

. if`n`

is divisible by`k`

, you simply set everything to 1. otherwise, you set some of the numbers to 1, some others to 2, so that in effect you have added "enough 1s to make`n`

divisible by`k`

.`n < k`

. There is no point in making the sum any bigger than`k`

and by pigeon hole principal, at least one of the numbers will be`ceil(k / n)`

. As`(ceil(k / n) * n) >= k`

, it suffices to subtract some amount from some of the numbers to make the sum equal to`k`

.Does

`nope`

mean that I did it wrong?`n >= k`

then`k = ceil(n/k)*k`

and do the same thing.Basically the idea is take 2 coditions- 1-if n<=k Here of course ans is n/k if(n%k)==0 and n/k+1 if it is not equal to zero because imagine sum consisting of 1,1,1... and then remaining will be added acc from first. 2-if n>k Basic idea is as n>k, bring k multiple as close as possible to the smallest number greater than n so that is eventually again satisfies the first condition and then proceed as if it is now a case 1.Hope u get the idea Here's the sample for case 2-

SpoilerHere's some one liner code for ya

`(k - n % k + n - 1) / n + (n % k != 0)`

Any hint for A?

find nearest integer >=n which is divisible by k say x, ans=ceil(x/n)

Omg -141 delta for me

Question D is far more simpler to me compared to question B and C :/

I had a terrible day too!

At least some previous contests had interesting problems I could not solve and I got negative delta, but this one was Painfully pointless to me :(

my contest in 1 photo :

the division with 1 huh? Yes it took me some time as well. But no worries mate I lost 1 hour on C not because I could not find the solution but just because I forgot a simple 'else' statement. Look at my submissions on C if you don't believe. Like what separates the successful from the unsuccessful I believe is just the ability of removing the blindness effect that I don't even know what casts it upon us. It's like we are in a MOBA arena and we have a passive ability of getting blinded for 1 hour randomly. We can be blind friends together hit me up if you ever want us to do a Virtual Contest together and then laugh at our blindness.

Not really. First I tried binary search and now i am wondering what was wrong on that solution, after i found some interative solution but i used the wrong formula :) .

Ah sorry I just realized you stuck on B and not A. My bad. Anw I solved B without binary search I would be very interested to see how it is solved with binary search.

first you have to observe that the solution is to add some number just to p0. Now ,let x be the solution and you can find it with binary search. For each x, check if can be a solution. If not, have to increase x, otherwise ,decrease it. The article in EDU about binary search is very nice, I ve learned a lot from that one.

Oh this is smart but it requires more complexity than the linear solution. Still very smart nevertheless. 105884577

I just read you solution. It is linear as well. Oh I can see where it got hard maybe when you where trying to calculate how much to add. I just did a max there since the maximum is what you need. Damn I could rank up so much in this round had I been a little more careful.

my binary search solution : CODE

Yes so it is O(nlogn). It just instead of doing the division and checking for the modulo that I was doing you do the BS to find the correct value.

Bro how did multiplying by 100LL instead of 100 get the answer in B ?

because your variables are int, and 100*1e9 = 1e11 and this value for int is overflow

If all variables and array are taken as long long. Will it still overflow ?

nope, should work fine.

Don't you think the copying during contests is increasing day by day?Also there are many smurfs account in the contest. Affects rating of a lot of people

Who is copying?

AkashRamjyothi1 see his solutions

105874881 : A

105895241 : B

105915359 : C

105929955 : D

while(true)

{ int abc = 0;

He is using these lines to save his code.

awoo, MikeMirzayanov please look into it

In order to check if a program is a copy of another one, can't the program be subjected to run on a set of deliberately faulty test cases during system testing? Programs whose behaviors, that is, the errors/exceptions they throw, the current values of all present variables, and the variable names in use, are the same for all test cases can then be weeded out...

You are asked to rearrange the patterns in such a way that the first pattern the j-th string matches is p[mtj].This is ambiguous. I thought it meant the rearranged patterns index mtj, causing me to write completely wrong code.

Same here

E was really nice. for each string s, for all the patterns that matches it, I put a directed edge from the first pattern it should match (mt for that string) to every other pattern that matches it and the answer is YES if the graph formed is a DAG?

I thought the same but dismissed it quickly because how is that not TLE? Each string can match to potentially all $$$m$$$ patterns. So $$$O(m^2)$$$ sized graph (or DAG) right there? The only explanation I can think of is that maybe because of the contraint that each pattern is distinct this bound can be tightened? Do you have the proof?

EDIT: Oh got it.

smh. Each string can only match to atmost 16 patterns (because of distinctness constraint) so size of graph is bounded $$$O(m)$$$.According to the question, all patterns are distinct. For a string s, given its maximum length is 4, we can have at most 2^4 + 1 patterns that match it (for all binary numbers from 0 to 2^4, if $$$ith$$$ bit is 1 then keep s[i] as it is, else replace it with '_').

A string can match with at most 2^k patterns. Let's take an example string "abc". Which patterns can it be matched with? "abc", "a_c", "ab_", "a__", "_bc", "__c", "_b_", "___" So, for each position of a string, we can either keep the original letter as it is, or replace it with '_'. so, for this reason a string can match with at most 2^k patterns.

Yes, and the answer is the topological sort of the DAG.

.

Can someone please tell me why is my code failing, I did a 2 way kadane-ish dp and printed their sum. WA_CODE

The dp seems to be off by one, since the indices go up to $$$n$$$ (as there are $$$n + 1$$$ cities).

I think problem B needed more tests, although figured out how to get 99 on test 1 it doesn't seem like it for the other tests.

The most educational things I learnt from A and B is that don't forget to use ceiling when comparing

Yeah same, Costed me 7 WA for B ;)

The hardest part of E was understanding it. Nice problem set though, thank you!

I still didn't understand the problem. Can you explain it?

Let the initial arrangement of patterns be $$$P$$$. Your goal is to find an arrangement of patterns $$$P'$$$. $$$P'$$$ is such that, for each string $$$s_j$$$, the first pattern in $$$P'$$$ that matches with $$$s_j$$$ is $$$P[mt_j]$$$.

That how it should be written in the statement!

As for me, it was absolutely unclear that s[j] matches P[mt[j]], and P remains the same. Maybe I misread something, but it seems there is no contradiction if you understand that part of statement differently

Reading it again, I feel it was somewhat clear what they meant. In my hurry to read it, I misunderstood and wasted 45 minutes on solving a different problem. Perhaps the problem statement should have held your hand a bit to be completely clear (like I did in my statement). I can't complain too much though, it's my fault I didn't read it closely enough.

At least that other understanding doesn't pass samples. That was the point at which I figured out that something is wrong:

coding is done, I fail first sample, OK let's actually look at the samples now...Yeah I wouldn't understand if there were no sample testcases.

In

Q2multiplying by 100LL instead of 100 got me AC. Any reasons why ?Integer overflow

Any article or reference on the same ?

Costed me 6 WA.

$$$p_i$$$ can be up to $$$10^9$$$ so $$$p_i\times 100$$$ can be up to $$$10^{11}$$$. Max int is usually $$$2^{31}-1$$$, which is slightly above $$$2\times 10^9$$$.

Can you please tell me why I got an overflow even after taking the entire array as long long https://codeforces.com/contest/1476/submission/105897736

On changing 100 to 100LL I got AC.... Can't understand why!! Thanks In advance

you are getting overflow on your tmp variable

UPD: got AC hereYES GOT IT!!

imagining C graph cases gave me a headache but I liked this contest you have my upvote

F, I wasted 1+ hour on B because I completely forgot that division by int rounds down :(

How to solve G?

Mo's algorithm

Take a look of this problem and its solution.

https://codeforces.com/contest/700/problem/D

How can we see its solution?? Its editorial isn't available.

Well, you can find some solution of the contestants in the comments.

only $$$O(\sqrt n)$$$ different values in the cnt array, so then apply Mo's algorithm to it and use a list to maintain different values in cnt, and then for each query take out all values and brute force

total complexity is $$$O(m\sqrt n\log n+n^{5/3})$$$.

But i am unable to handle the updates. Please elaborate.

I'm assuming you know how to handle the problem without updates (using Mo's).

To handle updates, split the queries (type 1+2) into blocks. Now, within each block, run Mo's. When you start processing a block, make sure that all the updates in the preceding blocks have been applied. To account for the updates in this block for a query of type 1, you can naively iterate from the start of this block applying all applicable type 2 queries. Since you broke it down into sqrt(m) blocks initially, it is guaranteed that you'll only iterate block_size times at max even when doing updates naively for each type 1 query.

You might need to fiddle a bit to find the appropriate block size though.

You mean for every block run Mo's naively?? Then for every block it should be $$$O(N*sqrt(N))$$$. Please correct me if I am wrong.

Google "Mo's algorithm with update"

In C what does this mean that "First chain is skipped", does this mean we cannot take any node from first chain? I had initially set the ans to c[0]. That was the only reason I was not able to solve C and costed me wrong ans :)). First chain skipped means I thought I cannot connect any node to previous ones, otherwise I can taken some nodes from first chain.

your last nodes can be in first chain.It means your cycle can't go above it.

God I could have solved B if I had 30 more sec... I submitted right after the contest ended and got AC :( Spent 60+ mins to figure out why my solution got WA... I really get mad at myself

I believe we both made the same mistake :(, but I was able to submit it just before the contest finished.

Can Anybody Please give Me some counter test case i.e., Fail My Code

Question Link

Solution Link

I tried Everything but not able to find any counter case, Also did Stress testing, Still Not able to find it.

try to use multiplication instead of division in check, that can be a problem.

Yes got accepted after doing this, Thank-you so much brother

Why was my submission not uploading after 10 PM. Ugh I don't get it. Now my rating will decrease without any reason, man!

How to solve E?

Take a look at this comment

If there are multiple $$$p_i$$$s match the same $$$s_j$$$, then the specified constraint is basically implying the specified pattern exists before all other $$$p_i$$$s. Thus, we can keep track on the indices of patterns and build a dependency graph based on the constraints. For any specific $$$s_j$$$, there would be at most $$$2^k$$$ distinct patterns matching it. Thus, at most $$$2^k$$$ edges would be added to our dependency graph. Hence, the problem is reduced to check if a given directed graph with $$$n$$$ vertices and at most $$$m\times 2^k$$$ edges is acyclic, and if so, report any topological order. This can be solved by topological sort.

There are a few trivial cases to notice, like the specified pattern not matching the given string or different occurrences of the same string being matched by different patterns, you may refer to my submission 105914103 for implementation details.

I was unable to sove even Problem A, can some one say the intuition to problem A. I tried binary search for problem B, but it did not pass 3rd test case

Try 1 2 1 1 1000000000

For problem A: we are need minimum sum that can be divided by k. Let find that sum.

sum = ceil(n / k) * k;

After we know sum, we need to spread it to cells, that each element was minimum possible

answ = ceil(sum / n);

Increase the Max value.

Consider all array elements to be 1. We need to increase these numbers until the sum is divisable by k. So, first step is to find the next multiple of k bigger or equal to n. Second step is to find the max array element if the sum equals the number found in first step.

I learned this the hard way — 99% of the time you don't need this big code for problem A. You probably need to take a deep breath and think at more fundamental level what the question is really asking.

And my solution got hacked. To all the losers making hacking attempts, go fuck yourselves.

It would probably have failed system tests anyways so I don't think it matters.

Here's a tip for you

$$$\lceil \frac x y \rceil = \lfloor \frac {x + y - 1} y \rfloor$$$

simple dp for C . a is vector of heights , b and c are vector of endpoints connecting to previous. we have to recompute this dp between all the inclusive indices of where b[i+1]!=c[i+1]

dp[i]=abs(b[i+1]-c[i+1])+1 +max(a[i+1],dp[i+1]-1-abs(b[i+2]-c[i+2])+a[i+1]+1-abs(b[i+2]-c[i+2]));

simple code.

codeWere F and G intended to be that much hard??

I'm really surprised nobody solved F. I've been rechecking and stressing my solution for hours, and I'm still sure it is correct, but it's strange that nobody got this problem.

How to solve it? Is it dp(i, j) — farthest covered positon to the right if we have processed i first positions and j is the farthest to the left uncovered position, with segment tree? Or it is wrong?

$$$dp_i$$$ — the maximum prefix we can fully cover with $$$i$$$ first lanterns.

Let's look at how can we solve it in $$$O(n^2)$$$ with this kind of dynamic programming. First of all, let's write it forward. Which transitions from $$$dp_i$$$ do we have?

It is obviously $$$O(n^2)$$$, how can we optimize it? Let's write this dynamic programming backward. The second transition is changed to backward dp easily, what about the first one? Suppose we want to turn some lantern $$$i$$$ to the left. Let's iterate on the prefix $$$j$$$ that we will "connect" to it; for this prefix, $$$dp_j$$$ should be at least $$$i - p_i - 1$$$, and we update $$$dp_i$$$ with the maximum of $$$i - 1$$$ (since it is covered by lantern $$$i$$$) and the result of max query on $$$[j + 1, i - 1]$$$.

In fact, we need only one such prefix — the one with the minimum $$$j$$$ among those which have $$$dp_j >= i - p_i - 1$$$. So, we build a minimum segment tree where each pair $$$(i, dp_i)$$$ is interpreted as the value of $$$i$$$ in position $$$dp_i$$$, and with min query on the suffix from $$$i - p_i - 1$$$ we find this optimal prefix, from which we should update (and to update, we can use any DS that allows max queries on segment — in my solution, it's another segment tree).

Source code

I was able to upsolve using what I think is a different DP, with $$$O(n \log n)$$$ distinct transitions, so both solutions are probably correct. Yours is definitely a much easier idea to implement.

I reached my idea by supposing for some $$$i$$$ that every lantern in $$$[0, i]$$$ has had its direction chosen and lantern $$$i$$$ is the first unilluminated lantern. Then, there must be some lantern $$$j > i$$$ which is turned left to illuminate lantern $$$i$$$, after which the set of lit lanterns is a prefix, and every un-set illuminated lantern would thus be wasted unless turned right, which lets me greedily illuminate every lantern less than some value $$$k$$$. If $$$k = n$$$, that is a success; if $$$k = j$$$ then $$$k$$$ is facing left; otherwise $$$k$$$ may as well face right.

It then turns out that there are at most $$$1 + 3 \log_2 (n-i)$$$ meaningfully distinct choices for $$$j$$$, and these are "easy enough" to iterate over: If $$$j$$$ is not the farthest-right-reaching lamp in the $$$[i+1, k)$$$ interval, no other value of $$$j \in [i+1, k)$$$ can possibly get a better value of $$$k$$$. But $$$k$$$ is at least 2 times farther from $$$i$$$ than the previous usable value of $$$j$$$ was! So the worst-case progression looks something like $$$j_0$$$, then $$$j_1$$$ (furthest reach in $$$[i+1, k_1)$$$), then $$$j_2 < k_1$$$, and then $$$j_3 \geq k_1 > i + 2 * (j_0 - i)$$$.

Submission link: 105953208

I had the same idea after the contest. You can simplify the code by doing some observations:

With those observations, I managed to get my code size at a little below 100 lines.

Submission: 106013279

Fs in the chat for question F

When "vovuh" is one of the writer then contests are awesome!!! Thanks for another good contest :-))

can someone say y my solution failed? i am confident logic is somewat rite. solution logic: cross multiplying the equality a*100<=k*sum and checking if condition false, add differnce to overall sum

We have the same mistake

it should be

`(a[i]*100LL-k*s + k - 1) / k`

don't ask me why :(

can someone tourist vovuh BledDest Roms Neon ecnerwala jiangly Benq boboniu Petr Radewoosh maroonrk Monogon neal explain y?

dude don't do this

Hey, I understand that you want to make a point, but don't you think tagging is unnecessary? I believe noone likes to be tagged just to be asked to debug someone else's code.

you assume that

`a[i]*100LL-k*s`

==`a[i]*100LL/k - s`

You should add (difference/k) to the overall sum and ans.

try this you will understand why.

1

2 100

1 2

The authors should put a good sample cases, it's educational round not destroying round

bad people in math (like me) will not figure out the division when

`k = 1`

How can the answer of this case of problem C be 4?

3

3 3 3

-1 2 3

-1 2 3

Can anyone please explain what I am missing?

How many tests will problem A have? There're 1000+ hacks...

I think the authors should manually look at the hacks and form some set of new testcases which cover all the corner cases, otherwise system test will continue for eternity.

Finally a time for me to be on the "+11" side of a widespread hacking event :D

I am deeply sorry for the people who got hacked though, I've been hacked multiple times before and I know exactly how that feels.

No you are not sorry, so stop pretending ffs.

brilliant contest! Thank you

this is my code for 2nd question inflation can anyone help where is the problem## include<bits/stdc++.h>

using namespace std; int main() { int t;cin>>t; while(t--) {int n,k; cin>>n>>k; long long sum1=0;long long sum=0; long arr[n]; for(int i=0;i<n;i++) {cin>>arr[i]; sum1+=arr[i];

} sum=arr[0]; for(int i=1;i<n;i++) { if((arr[i]*100-k*sum)<=0) { int c=1; } else { long long d=arr[i]*100/k; sum+=d-sum; while((arr[i]*100-k*sum)>0) {sum++;} } sum+=arr[i];

}

In problem E, "You are asked to rearrange the patterns in such a way that the first pattern the j-th string matches is p[mtj]." doesn't clearly state that index mtj is referred for initial arrangement.It should have been stated clearly.

How to generate hack test cases? I am trying to hack A with highest constraint, i.e. T=1000, K=1, N= $$$10^9$$$, but still solution passes

bruh check for corner cases when k=1 in code.

C was harder than D

Problems were good, I liked how ABC needed more thinking than coding and more thinking speed than typing speed.

It was an interesting contest even tho problem D was a standard one LOL.

thank u guys for 'A's weak pretests... :'((((((((((((((

As a...... As a novice at code/algorithm， I like codeforces! It's amazing and I like the feel to try my best to solve the problem... also I can't solve D which made me sad

It was hard and my solution on GNU C++17 64 bits FAILED BUT SAME SOL. ON C++17 PASSED...LOL

My standard screencast, with the standard tradition of misreading at least one problem

Nice pretests for A, as an tradition of Educational Rounds.

Felt you

As well as all of the other educational rounds

is there any extra points for hacking in educational rounds ?

No, it's not

Arethere any ... ?there arenot.thanks for great contest (i have 51 hacking successful =)) )

Just one thing: was it really necessary to have a two-letter variable like $$$mt_{j}$$$? First I saw that there is an $$$m$$$ variable, so I immediately interpreted $$$mt_{j}$$$ as $$$m\cdot t_{j}$$$, and that didn't help at all. I mean, I would understand $$$match_{j}$$$, but $$$mt_{j}$$$?..

And they also didn't specify which p they are talking about, the changed one or original.

I thought p[mtj] is a pattern after permutation :(.

I have to congratulate the setter of problem G. My solution looks like something well known, but I've never did something like that before. Really nice one, I definitely learned new stuff today. Thank you!

What's your solution?

I used Mo's algorithm. I didn't know about the trick to handle updates. A brief explanation of my solution:

Keep track some stuff:

$$$cnt[x]=$$$ how many times number x appears in the range.

$$$tot[x]=$$$ how many numbers occurs x times in the range.

$$$vals=$$$ vector of distinct numbers in array cnt.

It's really easy to update $$$cnt$$$ and $$$tot$$$ when you add/remove an element. For $$$vals$$$, simply push all the values to the vector while moving Mo's pointers, and after that remove values the ones that are irrelevant (those for which tot[x]=0). Also, avoid pushing an element to $$$vals$$$ twice. It's easy to see that after doing that, $$$|vals|<=\sqrt{n}$$$, because all elements are distinct and their sum is $$$<=n$$$.

Using the fact that $$$|vals|$$$ is small, you can answer the query with two pointers over the array $$$vals$$$.

What is the complexity of this implementation? I can't understand the amortized analysis of the update part

when you use Mo's algorithm with updates, you have you use size of blocks $$$S=n^{2/3}$$$. In fact, i read somewhere that it's optimal to use $$$S=(2*n^2)^{1/3}$$$.

Time complexity for addittion/removal of elements and push/rollback of updates is $$$O(S*(n+q))$$$ amortized.

Time complexity for iterating elements and removing values form $$$vals$$$ is $$$O(S*(n+q))$$$ amortized, because each operation pushes at most one element to the vector.

Time complexity for answering queries after removing irrelevant elements from $$$vals$$$ is $$$O(q*sqrt(n)*log(sqrt(n)))$$$ because you need to sort the vector of unique values before using two pointers method.

So, total time complexity is $$$O((n+q)*(S+sqrt(n)*log(sqrt(n))))$$$. Please notice that this analysis uses the fact that $$$S \approx n^{2/3}$$$ (not $$$sqrt(n)$$$). In practice, the solution works a lot faster (my code runs in 1500 ms).

For those interested in the details about complexity of Mo's algorithm with updates, there is a really nice blog, written by Fype, that explains everything :)

Thank you for the explanation.

Great contest. Problems are interesting and educational. I enjoyed solving them.

I don't know why, but I feel like at least 1 of my 4 problems will fail system testing :(

For Problem C i've included all border cases , still I'm getting WA, can someone please tell me what's wrong or give a test case on which my code fails ??

my code : https://codeforces.com/contest/1476/submission/105940952

The penalty for each incorrect submission until the submission with a full solution is 10 minutescan someone explain what this 10 minutes penalty mean? and if we submit the correct solution after certain incorrect submissions there will be no penalty right?No. Penalty means that if you submit a correct solution, you get the time for that solution plus the penalty. That is 10 minutes per submission, buf the first submission is for free.

got it thank you

Will it system test later,or just announce the final standings after the hacking time?

Can someone please tell me what error is there in my logic for this. I check for all elements in reverse order if the increase coeeff <= k and if its not I increase p0 by a sufficient amount. Link to soln: https://codeforces.com/contest/1476/submission/105888794

Difference between right and wrong in Question A

double n,k;

cin>>n>>k;

if(k<n)

k=k*ceil(n/k);

ll val=ceil(k/n);

cout<<val<<" "<<ceil(k/n)<<" ";

Input: 1 1000000000

Output: 1000000000 1e9

Both ans are correct but due to different format ans1 will be considered right and ans2 will be considered wrong.

So do typecast your ans

click

Question B :Using greedy approach.The basic idea is to take the maxdifference from all differences bcuz anything less than that will be satisfied by all other differences also either u start from begining or end of loop.

Here is my code which got accepted 105878231

click

hi

I really need help therefore I really couldn't understand what is the problem with the code which outputs that kind of format in test 3 problem b(but in math the number is correct)

submission:105899297

and its not just only mine

another submission of another person:105852796

help please

In C++, when a really large double is divided by a small number, it changes into the scientific notation. To avoid this, explicitly convert the double to a long long int or int as required in the problem.

when you use double then if your ans is large it tend to represent ans in power of e

notation .So to avoid it you can name your variable as long long int

or when you are printing ans just

typecastthe ans i.e cout<<(long long int)ans<<" ".

for C problem, my code failed in 4th testcase.I am not able to figure out the testcase,if anyone has any idea about what the testcase could be. Link to the code — https://codeforces.com/contest/1476/submission/105951904 My approach was to calculate number of vertices of every chain that will be added if i take that chain as an intermediate chain, ending chain, starting chain. i stored these values and calculated the maximum answer.

1

7

16 2 12 2 7 18 8

-1 7 1 2 1 2 2

-1 10 2 12 2 3 12

Correct Answer — 38

Your Output — 37

CodeForce is a great programming site!I love it.It brings me a lot of fun.The change of rating again and again makes me feel very exciting!

Why so long for the editorial? Or is it normal? Sorry I am new, but my past contests had editorials almost in an hour

educational rounds usually have slow editorials and idk why

I really do not understand, why my code for A problem had hacked .. why ceill function returns a wrong value While N & K are long Please can someone expert help me to understand what is the problem here !

this is my submission

https://codeforces.com/contest/1476/submission/105923499 }

simply just don't use ceil, use (n+k-1)/k for ceil(1.0*n/k)

But why that happened !

floating numbers are just too dangerous when you need absolutely correct results like codeforces, this ceil problem is very well known

Thank you .. i did not know that before This mistake cost me a lot this round ☹️

I too used Ceil function, it got passed. In Java ceil returns double so have to typecast it into integer before printing the answer 105866315

For the test case

1

1 1000000000

Your code gives 1e+009 as output, because you are doing "cout<<ceil(1.0*k/n)<<"\n";" .

If you type cast into long long or int ("cout<<(long long)ceil(1.0*k/n)<<"\n";") it will give the correct result 1000000000