Hello Codeforces!

On Dec/01/2021 17:35 (Moscow time) Educational Codeforces Round 118 (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 Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov, Roman Roms Glazov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

**UPD:** Editorial is out

Educational rounds are the best always good problems with good ideas

Good luck everyone and happy solving

Bro why aren't the ratings yet updated?

When will they update ratings?

I guess we need to make some sacrifice to codeforces god for updating ratings

The codeforces god was not pleased with your sacrifice so even the previous ratings are rolled back

-40 and -30, i am okay with that

they will take as they require to analyze the plag situation.

When will the Codeforces rating update?

Kindly Update Ratings I Want To Become Pupil

jal gai bichare newbies ki

I always had a question, How do you prepare educational contests so fast? Because creating new problems in one week is so difficult! awoo BledDest

They have a lot of experience

I know they are so experienced, But creating a new problem (actually a new hard problem which has standards of CF) is difficult, and I appreciate them for their hard work, Good job !

They must have unlimited problem generator AI...

Hoping to become specialist after this :)

Hoping not to become a newbie again.

All the best vro

Peeps on cf downvoting anything ಠ_ಠ, a genuine wish ¯(°_o)/¯

A long wait of almost 10 days after this contest : ( Waiting for this contest to be awesome and welcoming the fellow coders to have great competition : )

its for sure we wont have to wait for 10 days for nxt contest , some contest will surely show up in a dAY OR TWO bcz its cf :>

Harbour.Space University always have good problems. Hope every can enjoy this contest.

I hope the topic can be shorter

Last week's competition(educational codeforces round) had good problems. Wish you luck!!!

Educational rounds don't charge penalty points for wrong submissions??

Maybe read the blog?

Love edu rounds! Good luck to everyone))

As a Romanian, it's pretty cool to participate in a Codeforces round on the National Day of Romania (which is today, December the 1st)!

Light-hearted memeShare and subscribe.

I Wish To be Pupil I Love you Codeforces

♥...

Why codeforces has become speedforces from past 2 — 3 contests.

Okay fine D is the best problem I have ever seen, like enough already

why?

because you didn't solve it?

Just one question... Monocarp is some type of reference or the name of a famous person? I have also seen Polycarp

Maybe carp means something that I don't know in english

Carp is a large fish that lives in lakes and rivers

The name Polycarp (which is a usual Russian name, though an uncommon one) was very commonly used in contests made by authors from Saratov State University, namely MikeMirzayanov and his students. The name Monocarp (which is NOT a usual Russian name) was originally used as a one-time joke for one of the ICPC qualification stages in our region (as a reference to Polycarp), but later on, we chose to make Monocarp the main character of most our problems.

Oh, what a story! I really didn't expected that.

Actually this name is of Greek origin, and it was the name of an early Christian martyr and saint. The name used to be common among Russian Orthodox Christians. It is indeed uncommon now.

Was that inspired by Monogon? :)

The first contest with Monocarp was in 2018, so, actually, Monogon was inspired by Monocarp.

I used to read it as PolyCRAP and MonoCRAP

The difficulty gap between C and D is just too much. C is too easy for its position and D is too hard...

Also I found B to be easier than A

same

Just try E

how to solve E? i was trying bfs from lab vertex is that correct ?

yes. You then just have to check that you don't have more than 1 dot as neighbour.

i am doing that ,though getting wa on test 3.

What you are doing seems quite complicated, I believe it's you trying to debug your code.

my code should show that the approach works and is quite readable (just don't ask me why I converted chars to int to convert it back at the end!)

thanks ,i got the mistake ,it was in the implementation.yeah it was very difficult to debug it ,thats why i was doing multiple submissions

Comment partly deleted to reduceit's size since intimidator found his issue. not much value in it anymore and it took plenty of space in the thread

realized it just after the contest...

I had one approach like, mark all the free cell

`+`

except the cells that helps in forming a cycle within a matrix. Because, robot just not follow the command and will move in cycle infinitely.Is this a right approach ?

Also you don't need to mark as

`+`

vertices that don't have a path to L. And finding all vertices that are on a cycle doesn't look like a very easy task.Please list out the 7 sequences for sample test 4 in quest D

4

0 1 2 3

which satisfy

I wasn't able to find them either

[0], [0, 1], [1], [0, 2], [0, 1, 2], [0, 1, 3], [0, 1, 2, 3]

how [0,1,2] is valid?

we have b = [0,1,2]

i = 1 -> mex(b[1]) — b[1] = mex(0) — b[1] = 1 — 0 = 1 <= 1

i = 2 -> mex(b[1],b[2]) — b[2] = mex(0,1) — b[1] = 2 — 1 = 1 <= 1

i = 3 -> mex(b[1],b[2],b[3]) — b[3] = mex(0,1,2) — b[1] = 3 — 2 = 1 <= 1

Don't forget that mex(x1,x2,...xk) = smallest element that no appear in that sequence, mex != max!

Ahhh, Got It,

Thanks

mex(0) = 1; |0 — 1| = 1

mex(0, 1) = 2; |1 — 2| = 1

mex(0, 1, 2) = 3; |2 — 3| = 1

0 1 01 02 012 0123 013

Same Doubt

0

0, 1

0, 1, 2

0, 1, 2, 3

0, 1, 3

0, 2

1

Wasn't it stated in problem description that here you can take any sequence? edit: nvm

1) [0]

2) [0,1]

3) [0,1,2]

4) [0,1,2,3]

5) [0,1,3]

6) [0,2]

7) [1]

How to solve F?

Let's solve it by inclusion exclusion principle, let's denote $$$f(x)$$$ as the number of permutations with

at least$$$x$$$ edges such that $$$c_{child} = c_{parent} + 1$$$. The answer to the problem is $$$f(0) - f(1) + f(2) - f(3) + f(4)$$$... up to n.To compute $$$f(x)$$$ for some fixed $$$x$$$, $$$x$$$ nodes should have exactly one child with their value minus one (it is impossible to have more than one since it is a permutation).

Let $$$g(x)$$$ will be the number of ways to select $$$x$$$ edges such that there are no two edges with the same parent node, this can be reduced to a knapsack problem, with the degrees as items, all $$$g(x)$$$ can be solved in $$$O(n\log^2{n})$$$ with divide and conquer and fft since the sum of all items is up to n.

Finally, $$$f(x) = g(x) \cdot (n-x)!$$$ since $$$x$$$ numbers are equal to the number of their parents minus one, so there are $$$(n-x)!$$$ possible permutations.

Thank you, can you please clarify a bit more on reducing the problem of selecting X egdes to knapsack problem? And how you can find all g(i) in O(n Log^2n) ?

For each node, 1) you choose a child that has their value minus one (select one edge) 2) not choose any child (no edge selected) There are (number of child) ways to choose 1). By multiplying (x + number of child) for every node, we can get a polynomial which the coefficient of x^i represents g(N-i). Multiplying N linear polynomial can be done in O(Nlog^2N) using FFT and divide and conquer.

Beautiful, thank you!

How to proof f(x)=g(x)⋅(n−x)!, I just can't notice that...

Also took me a bit of time to understand this. I think the proof below works.

You need to prove that there is a bijection between a valid configuration (i.e. values that satisfy the parent-child constraint for each of the $$$x$$$ selected edges) and the relative ordering of non-child nodes (there are $$$(n - x)!$$$ relative orderings). Note: with child nodes I mean the children of the $$$x$$$ selected edges.

If there is a bijection it means that both sets are of equal size, and therefore there are $$$(n - x)!$$$ valid configurations.

To prove that it is a bijection we need to prove that

thanks!!

how to solve b?

x mod y always gives values between [0,y-1] if we choose y as smallest element of the array then it is obvious that our requirements are met (given in the question)

Ah wow, how did I not realize this.... :(

take the smallest number as y in all pairs. since x % y < y it satisfies the conditions

Just take y as smallest element in array so that remainder is [0 , y-1] which doesnt exists in the array

I forgot to read the line

`Note that some x or y can belong to multiple pairs.`

What is test 2 of D ? I cannot figure out the edge case i am missing.

I have failed on this one:

Is the answer 6?

It's 9

[0] [0] [0 0] [0 2] [0 2] [0 2 2]

Can you point out the other 3?

Don't forget that you can also put '0' after '2' and get another 3 combinations.

It should be $$$9$$$.

These are possible combinations. $$$0$$$ can be placed after $$$2$$$.

Ah right! Thanks

Thanks! It helps a lot

same here

Wasted a lot of time in D , could have done E instead.

Figured out E 3 mins after contest :/

For me, A > B and D > E. In other words, I felt E was easier than D and B was easier than A. Although A was easy too, just some bit of implementation.

It was very easy to lose yourself into the implementation details of A and this is why I also felt like A was (much) harder than B.

I guess much of A's implementation can be made easier if you consider x1 and x2 as strings rather than integers!

That's actually what I did, as I struggled a lot with x1 and x2 implemented as ints, and then I thought: "screw it, I'm gonna do this cheap string trick"

Don't say you were trying to work with 1000000 length integers!

Or you can just subtract min(p1, p2) from p1 and p2, and then if min(p1, p2) + 8 < max(p1, p2), number who has bigger p is bigger, else you can just multiply x1 with 10^p1 and x2 with 10^p2, and check them like usual numbers.

Right. And then represent it as a pair of length of x plus p and x with the rightmost 0s trimmed.

Who thought that E was that hard and even harder than D man, that problem can be even a harder div2C, it's just a bfs.

I love the problem D, the solution is beautiful and it has two of my favorite subjects, combinatorics and DP!

Once again!!

I found C easier than B , and i think my solution to B is terrible, because i used brute force and depended on the case (f[1]!=0) 137676564

i saw that coming :D (hacked) 137676564

Bro C was just binary search. It was easier than most Cs we see in div2. I was surprised at how direct it was actually

My purpose is to tell how hard D is compare to A,B,C :> i'm not telling that C is hard.

Oh i get it now, that's true, i can't even understand the solution of D

You can solve it without binary search.

Question C could be solved with iterative binary search (https://codeforces.com/contest/1613/submission/137689165) but was giving TLE(at test case 5) with recursive binary search (https://codeforces.com/contest/1613/submission/137672043). This cost me 3 wrong submissions and a lot of time!

My recursive binary search solution passed (https://codeforces.com/contest/1613/submission/137671370).

Its not recursive is it. You are using while(s<=e) { } The binary search is iterative.

The issue is that you added an extra min operation to your recursive function which caused it to keep around a lot of unnecessary info on the stack- your solution passes if you just remove the min

https://codeforces.com/contest/1613/submission/137709365

Such a small change and it changes the result. Great debugging!

Reason why he is purple :_:

This is my first time attending cf contest!

Just curious that if I'm currently unrated, would this contest be rated for me?

It was also my seceond one :) The ratings won't appear immediately I think . For the first time I participated , I could see my rating a few hours later . But don't worry you will see it soon

Yes.

The rating takes a bit of time to be updated, partly becasue of the hacking phase. If you want an idea of your future rating, you can check cf predictor

Edit : As beginners, since I am one too, I believe we shouldn't focus too much on ratings. Just start solving problems, enjoy and check where we land in a couple month =D

how much time it takes to get first rating points after this contest?

How to solve D?

Use dynamic programming. You can get that there are only some types in mex correct sequence. First of all, Thre are a sequence which starts with 0 and looks like 0 0 0 .. 0 1 1 1 .. 1 2 2 .. 2 ...(from 3 to n-1) n n .. n n n. In this case, you can expand this sequence with adding n, n+1, or n+2. Also, there is another type of sequence. which also starts with 0 and like 0 0 0 .... (from 1 to n-1) ... n n n ... n+2 n n+2 n+2 n n n (don't have to alternative, just after all, you should add either n or n+2) In this case, you can exapnd this sequence with adding n or n+2 Finally, you can think about this kind of sequence: which is composed with only 1, like 1 1 1... 1. count first two kinds of sequences with dynamic programming with dp[i][j]=number of sequence which ends with i and type is j(either first or second) and count last one with just counting the number of 1. number of last kind of sequence is 2^cnt-1

I found this observation during contest but couldn't figure out how to implement in dp.Anyway I will now learn, thanks for help

Once you get that observation, then I think checking with some cases(which are on the above)will be helpful to you. I also struggled with some wrong cases at first.

1 1 1... 1 sequence could be a special case of 0 0 0 .... (from 1 to n-1) ... n n n ... n+2 n n+2 n+2 n n n . So there is only two types of sequences: MEX n with max n — 1, MEX n with max n + 1.

any idea why this is wrong? this is problem C, I did binary search and pretty sure it is correct, but it gives wrong answer, ;_;

like I dont even get why 456 is not a correct solution for the last test case of sample tests? I am getting 456 as my answer to binary search and 456<470 (given answer) Help! please

maybe you should use this: min((i+1<n?a[i+1] — a[i]:(int)2e18-a[i]),mid)

Man, you are right!! Thanks a lot!!!! But what is the difference between the two? ;_; I dont think I would have ever been able to debug this.

maybe you read the wrong question，the poison affect is refesh, not stack. And the time to kill dragon may bigger than 1e18

Can you explain how the answer can be bigger than 1e18. I wanted to hack a solution because of this but could not come up with a case that has ans > 1e18.

I mean the time to kill dragon may bigger than 1e18, not the ans. ans <= 1e18. if n = 1 and h = 1e18 and a[1] = 1e9, than the answer is 1e18 but you will kill the dragon at the moment of 1e18 + 1e9 — 1 which is bigger than 1e18

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

?Also

`(int)1e18`

will overflow. Use`long long`

.Nice problemset, I enjoyed solving A-E! Looks like I'll also learn a lot from F once the editorial is published.

[Deleted]

why??

everyone knows that endl is slower than "\n"

but not like more than 3 times slower

actually, it's more than 10 times I guess. After I read this I changed my code from using endl to "\n", and the 2000ms tl become 217ms AC. Really learn a lesson in this problem.

You learnt something new! What I would do after something like this, is try to find out

whythis happens. I would recommend you to do the same ;)Thanks to this contest that I realise "cout << endl" will get TLE for the first time137704588 137708870That particular test case you are flushing the console 10^6 times hence TLE

Is there any idea to solve F? I enjoyed A to E but I couldn't get some idea to solve F. I think there should be some combinatorical good theory to solve.

Link to my comment above

Thanks a lot!

Does anyone knows why my submission for A is getting WA? As far as I know, it's mathematically correct but I can't figure out a test case that breaks it, thanks a lot. (The idea behind the solution is to represent both numbers as x+(10^p) and then take it log10 to reduce its size and compute the number) (also note that lli is defined as double)

you use a and b as length, but then when you compare them, if you have a = b, you print equality, although this is equality of lengths, not numbers

Nope, a and b is the log10(x*(10^p)) (log of the whole number represented in the problem) and with log properties, you rewrite it as log10(x)+(p*log10(10))

Issue 1: You are assigning answer of

`log10`

to`int`

type which is incorrect. You should use`double`

instead.Issue 2: Even if you use

`double`

data type, it fails in case of`=`

cause of`==`

between`double`

s. you cannot compare floating points with`==`

stably. See your modified code hereI solved it using lexicographic string comparison.

Thanks!! lli was defined as double, but the precision was the true issue :( thanks, it'll be an unforgettable lesson :c

For those struggling with TLE at test case 16 in E , when printing out the grid change from $$$endl$$$ to \$$$n$$$ and TLE will be gone

Your AC code scared me

At the cost of increasing your endurance to solve hard problems

You are a beast for coming up with a solution, no matter the cost! Congratz!

GAWD LEVEL

Wow I wish i could have endurance like you during contest :).

Can someone help me better in understanding what i could have done better to avoid wrong answer for problem C?

Here is my solution -> https://codeforces.com/contest/1613/submission/137670768

In check function value will get overflow when n = 100

not really.He has added n+1-th element too.See in the main function

My bad

v.pb(1e12);

Here,because h can up to 1e18..that's why you are getting wrong answer

v.pb(1e12) and h = 1e18 => ans maybe > 1e12

"wrong answer 1st numbers differ — expected: '433940482775969078', found: '1'"

Add 1e18 to your array instead of 1e12.

Adding just 1e18 to the array wouldn't be enough, see https://codeforces.com/contest/1613/hacks/773649

This contest offered so many amazing hacking opportunities. Weak pretests made the hacking stage very entertaining. And it's still not over, because the incoming system test (with all hacks included) is likely to claim even more victims.

E. 2000ms for 1e6 input == Downvote

I solved C in less than 10 mins after I have started the contest. But got WA for both A and B. Then after contest solved both in less than 15 mins... For me C < max(A, B) :)

I am not a detective, but this group of contestants looks sus fifijonil nexoxogoc ybgbsydvh ouhtek robot_bobot

as well as these two submissions 137693885 137674037

Could someone explain why my submission to A fails?

I am converting both numbers to scientific notation and then comparing the numbers. Does it have something to do with errors regarding precision?

Update: Well I did not know about such precision issues. But it turns out the error in my program is actually in the while loops because I was not converting numbers to scientific notation. In my old solution, I have > 10 when it is should be >= 10. Here is an accepted solution of converting the numbers to scientific notation.

tldr: converting to scientific notation seems to be a valid solution to A.

Indeed it has

eg. if I run this code

double x = 0.1;

cout << (x * 3 == 0.3) << endl;

result is 0 (false) for me

Yes, you guessed it right. To check to doubles/floats are equal or not do the following

why getting wa in 2nd tc?

you can't compare numbers after mod operation, order is lost.

`(7 mod 5) > (10 mod 5)`

, but`7 < 10`

but when i use simple pow function still same probem .

Is there any standard concept for solving problems like C?

Binary search on answer.

It's Binary search on answer. You can learn about it from 'EDU' section present on this website.

As this is a DIV 2 contest, why does nothing change, when ticking the box "show unoffical". Do I miss something?

Div1 participants also appear in the standings table

I cannot understand why my solution to A was rejected? See https://codeforces.com/contest/1613/submission/137639790. It looks very similar to others?

you will get a time limit exceed because your comapartor operator will traverse max 10^12 to check which string is greater or lesser

What comparator operator? The if else statements are based on ints and the x's and p's are mapped immediately to ints when they are read in

yaa than the ints will get overflowed it would be 10^12 then and max size of any type is 10^9

Any hints for dp states of problem D?

Spoilerdp[x][2]

dp[x][0] -> no of subsequences ending at x — 1, such that mex is x

dp[x][1] -> no of subsequences ending at x + 1, such that mex is x

Edit: For thorough explanation: See my video explanation

Video Editorial of A,B,C

It was a great round, was able to solve 3 problems for first time in div 2 contest!!! Just had a confusion while solving A by generating the two numbers using

function and usingpowtype , why did I getlong long integer? Why did it fail, am I missing something?wrong answer on test case 2long long int is USUALLY (it depends on the compiler) coded on 64bit which means it's in a range -9e18 +9e18. To get the real limits, you should read <limits.h>.

Anyway, in A, the exponent can be up to 10^6 so you will get numbers up to 1e1000006 which will overflow by a LOOOOOOOT,

Oh okay thanks

How does https://codeforces.com/contest/1613/submission/137705083 work but https://codeforces.com/contest/1613/submission/137689153 WA on Test 10? Is this a thing with Python, or specifically with the math module in Python?

h can be up to 10^18. Numbers above 2^53 cannot all be represented exactly by floats, so you lose precision.

E was pretty easy compared to D..the setters should try to place problems at the right place.A good contest btw

The heart is too anxious to miss green name. Too many penalties。 But the experience is better

Why don't you let $$$O(n\sqrt n\log n)$$$ pass F?

upd: I try my best to make it $$$O(n\sqrt n)$$$ and it finally passed.

[deleted]

But the solution maybe in $$$\sf O(n\log n)$$$ or $$$\sf O(n\log^2 n)$$$. I think maybe I can solve this problem in $$$\sf O(n\log^2 n)$$$.

Hope not to be heacked……

Maybe it is "hacked", not "heacked".

I'm poor in English……

Where are the editorial for the problems?

Just wait

Still waiting

Need help in question E.

Getting WA.

My approach was as follows.

1)Start BFS from Lab

3)While traversing push the co-ordinates of the cell which is free, only if at max there are 2 direction in which you can go(one of which will lead to lab).

Please tell what is wrong with my approach

try this testcase:

All the . should be + in answer.

Not max 2 but max 1, you should replace '.' with '+' after each steps to reduce it down to 1 (if possible)

I love problems like F. It requires unique ideas and has simple implementation(if you have the code for FFT).

I'm surprised that everyone uses BFS for problem E.

Why? Looks like it's obvious solution

I use DFS actually, I thought everybody did so, but no.

why my java code is giving tle for 'D' problem, it's giving AC in c++ 137748948

Just a small question, DFS on E gives runtime error while BFS passes. So in c++, cant we make 1 million nested function calls ? Does anyone know approx. what is the maximum number ?

You can get passed with DFS on E, check my submission: 137662230

O(NlogN) for N<=100 solution C instead of expected O(Nlog10^18) https://codeforces.com/contest/1613/submission/137680384

Update: Ok it got hacked

inputoutputThats what I thought but appearently this is not included in the test cases, it will get hacked soon then

how about not just 30 times but do infinite loop until there is no change

I think it would get TLE then. because it would be O(N*N*M*M) in the worst case

During contest time I've submitted this code 137682943 and it got ac. And after system test I've resubmitted the same code 137752171 and it got TLE in 5th test case.

This is a really good contest, especially problem D, what a amazing problem! Hope to do a contest like this again!

My code ran into TLE 3 times for problem A.

Sad life.

When will we get editorials?

I guess it will be similar to past educational rounds? I don't get why people who have already participated in educational rounds keep asking the same sort of questions again and again? Do y'all run some script which posts some preset comments on recent blogs?

you should learn how not to overreact on things unnecessarily

I agree, maybe I could have stated my point a tad bit more politely. However, I am still curious as to why you posted the comment you did. Were you hoping for early editorials this time? If yes, then why? If no, then why the comment?

every person in the world has rudeness hidden inside them but you don't express it everywhere + everything you write don't have to be extremely pre-thought that whether it will have any affect or not.Suppose if a round gets delayed by 10 minutes, does a comment of some people make the round held earlier???No,but it is human instinct to write comments at that time, why delayed!!!And it would be foolish to react on those sorts of comments

Not as foolish like you who only knows to spam comments and expects to become LGM in 3 years

So when are the ratings coming?

Have patience bro and do upsolving because hope you was not able to solve all the problem.

Here are the video Solutions to the first

5Problems in case you are interested.First Submission

Second Submission

Submitted problem D twice, the only difference was in one line (I commented out "cerr << ..." in the second submission). Got idleness limit exceeded in the first submission. Can anyone tell me why this happened? And why did the idleness limit exceed on test 2, not test 1? Should it maybe be rejudged?

Even though cerr output is not interpreted as the answer and does not get rejected as WA, it still causes a significant slowdown. The only mystery is why was this failed submission reported as "Idleness limit exceeded" instead of TLE?

Why aren't the ratings still updated?

My submission

can anyone find the flaw in my idea for problem D it passes 2 test cases and give WA on 3rd

my idea I used dp

the required sequence can be only of three types 0->0,1,2,3(consecutive) 1->0,1,3 (one skipped) 2->0,1,3,1,3,1,.....(alternating after one skipped)

so i created a dp[n+1][3] where first state corresponds to ending number of a sequence and second corresponds to type of sequence my transitions

can anyone explain why this is wrong

And what is the result? sum of all dp[][] values?

yes

There is one main thing you are missing in this transition in $$$i==0$$$ case,

$$$dp[0][2]=(dp[0][2]+dp[0][2]+dp[2][1]+dp[2][2])$$$

Now, $$$dp[2][2]$$$ will store count of sequences ending at 2 and which are of the alternating form. There are two such sequences,

1. 0 2 0 2 0 2....

2. 0 1 2 4 2 4 2....

But, you can append 0 to only the first type not to the second one by the definition of Mex-Correct sequence.

You will have to change these transitions in $$$i>0$$$ cases as well because of this logic.

One thing you can do is to make 2 separate $$$dp$$$ arrays(or increase the second dimension) to store these two types of alternating sequences.

ohh now i understood what i was missing thanks for your reply Enigma20:).

UPD:

Finally got AC by using another dp2[n+1][2] this is to calculate alternating sequences of type 3.

where first is the ending number of sequence and second specifies whether the ending number is increasing number of alternating sequence or decreasing number of alternating sequence.

for example 1. 0 2 0 2 0 2.... 2. 0 1 2 4 2 4 2....

here 2 is increasing number in alternation for sequence of type 1 and 2 is decreasing number in alternation for sequence of type 2

Finally AC

How to solve E?

EDIT: I tried it to some extent but couldn't end up with a correct solution.

My main observation was that a cell will be only + if there are only two or one way to exit this cell for example x,y is a free cell and x+1,y is blocked and x-1,y is blocked so this cell can be a '+' provided it leads to the labso I ran a bfs starting from the lab. I enter only those cell which has only two ways or 1 way to exit it and I turn it into '+'.

But this solution is giving WA!

is my observation flawed or am I missing anything?

you should compare the number of neighbors that is '+' or 'L' with the number of exit this cell, not just check the number of exit this, e.g.

#..

.L.

...

although a[2][3] has three exit directions, it is '+'

Thank you for the reply but can you please tell me what should be the comparison?

I mean if the number of exits is x and the number of neighbors that is '+' or 'L' is y then when should be the cell converted to +?

can anybody help me? In problem D I have a solution based on dp[i][j] the number of sub sequece that i is the last number of Mex-correct subsequece and j is a type of Mex-correct (if j = 0 then mex of subsequece must be i — 1 otherwise of j = 1 then mex shuld be i + 1).

thus we have dp[i][0] = 2 * dp[i][0] + dp[i-2][1] and dp[i][1] = 2 * dp[i][1] + dp[i-1][1] + dp[i+2][0] but I got WA.

here is code

check sequence "0 2 0" answer should be 5

ok it's 5

Why Ratings are still not updated?

Cause sys tests were still pending

I think it's the most late rating update ever

I wish to learn the art of problem making?

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).Today is 2021，1202, which is a palindrome. we should celebrate it. wait for 20：21 in your time zone and see what will happen.(maybe a rating update)

Well it's 22:21 actually

What has happened to Codeforces? The system testing is not over yet?

During contest time I submitted my code and it was accepted on the second attempt. But after system testing I found WA because of TLE in the 7th test case. I found no reason behind it. Plz help me. Here is my submission link https://codeforces.com/contest/1613/submission/137660678

Your code only passed weak pretests during the contest time. Then there was a 12 hours long hacking stage and people could freely submit their own stronger testcases (also known as hacks) to exploit various bugs and vulnerabilities in incorrect solutions. The final system test included all these extra testcases. Your solution failed to pass them.

I suggest to look at the input data of the 7th test case and try to figure out what exactly killed your solution.

Okay, thanks for your informative suggestion.

Imagine a test case of $$$t = 10^4$$$ and in each case $$$p1 = 1, p2 = 1000000$$$. In this case your code will run $$$10^6 . 10^4 = 10^{10}$$$

Yes,you are right. But I was not much aware of the hacking process. I think that as my submission was accepted once it will never turn around.

Ok so carrot is predicting +79 and i need +81 rating for cm. I dont think my copium can handle this.

What is carrot? I also want to predict my rating

its an extention, check your prefered browser's extension store and search for it

Oh Thanks!! I wasn't aware of such thing

In this dire moment, I have nothing to say to you, except

hello.carrot was predicting +35 for you(before this thing)

:D

Lol, both you and Naman got it)) Congrats

Will anyone please help me that why my solution for the question is getting tle in the 16th testcase. First I thought that in my code there is some infinite loop. So, to check it I changed my code specifically for case 1)m=1 2)n=1 and since, in this we only have to go in both directions from 'L'= lab until we encounter '#' or we have reached to the end of string. So I Directly use the while loop for that and still, I am getting tle. Its not clear to me whats the problem is. Link to my code.

Just use '\n' instead of $$$endl$$$.

And a good advice for the future, use $$$endl$$$ only in the case you want a flush, otherwise use \n

yuppp! Thanks for your help.

Is this Rated?Rating is not updated yet. Moreover, previous contest ratings also has been rolled back. What's going on?

Maybe someone in the headquarters was sleepy and instead of clicking on rating update he clicked on rating roll back . ( Not trying to disrespect anyone )

You have been around long enough to know the drill. The only missing thing is a banner at the top of the site with a notification about temporary rating rollbacks.

Looks like the plagiarism checks for the earlier Deltix round are almost complete and the scoreboard will be finalized soon with recalculated ratings. And then preliminary rating updates for the current round will become available too (followed by a rollback and finalization at a later date).

Rating ??

Why there is no rating changes yet?

Kindly Update Ratings

Mike: and I took it personally.

WTF Even GM's Rating have been changed for this round

Div. 1 participants got a delta rating as well xD

Educational Codeforces Round [Rated for Div1 + Div2]

It was a glitch . :)

Hurray! new rating!

Yeah Current 1298 but max 1277 Looks like max function taking time to compute xD

I guess there's something wrong with rating changes cause I should've got +147 delta according to cf-predictor but only got +71

as you said , it is "predictor"

looks like this trouble is not only mine so I believe predictor works fine with possible plus minus 15 delta diff

Is

Mikehigh today?He just pressed some wrong buttons ig. Come on, everyone loves to play with buttons

Finally, he played with right buttons

So cheaters are no longer removed from codeforces?? all the cheaters from this round is still rated.

ybgbsydvh nexoxogoc ouhtek robot_bobot

SpoilerWhy aren't the problems still allotted to their difficulty rating ?