Hello Codeforces!

We are pleased to announce a new long-term partnership between Codeforces and Neapolis University Pafos. Now educational rounds will be supported by Neapolis University Pafos. Stay tuned and you will find out more soon.

On Mar/15/2024 17:35 (Moscow time) Educational Codeforces Round 163 (Rated for Div. 2) will start.

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, Ivan BledDest Androsov, Maksim Neon Mescheryakov, Roman Roms Glazov and me. Also, huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Big thanks to the testers shnirelman and Optoed for their valuable advice and suggestions! Special thanks to Vladosiya for his help with the round.

Good luck to all the participants!

**UPD**: Unfortunately, there were issues with the problem E judgement during the contest. There were only 18 participants affected by it, so the round stays rated. Rated participants whose verdict on problem E changed may request unrated participation (they have received the directions on how to change their participation to unrated). If you have not received any personal notifications about it in the contest dashboard, you have not been affected.

**UPD2**: Editorial is out

excited for A, B, C problems

you practice so hard and participate almost every contest in codeforces!

still pupil lol

just keep coding and you will make it!

You solve 600+ problem but most of there are 800 difficulty. solve more difficulty problem and also do virtual contest. It will help to improve your problem solving ability rapidly.

how to keep up and make time for everything disappoints a bit. But still its better than solving problems topic wise... I guess every new things we see here in the contests might be more than enough to get the general overview in enhancing the ability....

It's better to learn the "new things" beforehand. This might help

Such a short and clear announcement I hope problems statements be like this too!

Mathforces lessgo

Excited af

Excited as f

R.I.PIt's probably the other way around

Interested in solving these problems :D

just an fyi that codeforces no longer supports c++20 (true at the time of writing this comment), so hopefully no unpleasant surprises during the contest!

It's temporary and there is a very good reason for it (https://codeforces.com/blog/entry/126654).

i am already aware of that thread. It is true that there is something subtle going on (probably related to the Windows heap). What I take issue is that we're just banning c++20.

Whatever the problem may be, it is only affecting a small minority of all submissions. Straight up removing the compilers just creates larger inconveniences. We can make this issue known and those who are concerned may choose to use different compilers for c++.

Back when Java's Arrays.sort was quadratic time, we didn't just ban the language. We're not banning pypy for being slower python with Fraction either.

If submitting in C++20 is causing performance degradatinos for

otherusers' submissions, that's a separate discussion. Then I agree removing C++20 would make sense. However, such things should at least be properly announcedThis issue is different: - As far as I know, the scope of the issue is not well understood. The issue is with variable length allocation, which appears in many submissions. I don't think it's fair to say that it affects only a small minority of submissions--only that a small minority of submissions have been shown to be problematic.

The inconvenience created by removing a compiler is substantially less than the inconvenience created by removing a language.

We can expect contestants to be familiar with the language itself, so it's fine to penalize contestants who use slow APIs from the standard library. It's generally not expected for contestants to be familiar with the details of a compiler, and less so with the operating system internals (which is most probably where the error lies).

Unless this changes, and the build system is made completely public, it's actually the fault of the Codeforces platform for building on a system with this type of unexpected slowdown. So the correct thing to do is remove the compiler until the issue is resolved.

I agree with most of what you said. However, I don't think the logical conclusion is to remove the compiler (which happens to remove the language c++20 entirely). I agree that it is the fault of the Codeforces platform, but they could just keep c++20 and admit there is a fault in the system. Instead, they decide to hide it by removing the language. I see no issue with a caveat along the lines of "we tried, but use at your own risk because we run code on windows".

Hope to get my rating back

Good luck for everyone!

Oh yes!!! Another Div.2 contest!

Binary search forces ?

Will there be an interactive problem?

As !tester predicting yet another mathforce

Just curious, this support change will only affect the policy-related/financial/sponsoring aspect of the round series, not the setters, won't it?

lets go =D

Hi

I hope E not too easy like last 2 Edu rounds good luck everybody

lol

Who tested?

New sponsor, hoping for better rounds but i can't expect anything from edu ...

Educationals are too unpredictable. Scared to participate but gotta try :(

still have hope

in edu rounds you can submit as much right submissions as you want right? without any penalty?

No, 10 minutes penalty for each wrong submission.

i am asking for right submittions

I'm sorry, I read your question inattentively because the round was starting.

D seems to be easier this time

The problems in this contest are really bad

anyone can explain to me the test in problem C ? Now, i still can't understand it!

So, in first turn we move to (1,2) and than we have to move like an arrow on this cell, so this turn we end in cell (1,3). In second turn we move to (2,3) and again we have to move like an arrow, so from (2,3) we move to (2,4).

Thank, but why TEST 3 is no way to 2,4 ? I think we can go 1,1 -> 1,2 -> 1,3 -> 1,4 -> 2,4 ~~~~~

~~~~~

When we move like you said:

In first turn we will go to (1,2) than like arrow to (1,3). In second turn we will go to (1,4) than like arrow again to (1,3).

okay thanks, i was understand problem

Problems were too hard, I need to get good. :(

can any body tell me what's wrong with my dp solution for problem C : submission

I also tried DP, mine also failed on 787th test case in div2 c.. My submission:

Can someone pls help 251548692

AC Dp Solution: here

Mine also failed on 787th test case.251525227

Same here failed on 787th. 251614468

Here's my memoized dp solution for C with simple observation that diagonal elements must be '>' 251558857

G is a cute problem, thanks!

[Deleted]

orz

D felt better than C. C was a bit annoying

I wrote BFS for C and it's easy.

oh ya I should have done bfs, I did with 2 prefix arrays.I will try bfs thanks .

Can you explain your bfs approach? I wrote bruteforce and it took me a lot of time. Couldn't figure out how to write bfs for that.

For every cell check whether there exists a cell in the 4 directions, if yes see the direction inside the cell and move that way. Mark this new (final) cell as visited and add it to the queue, and continue.

My bruteforce is also like that. Maybe I did bfs without actually thinking about it.

checkout my solution (observation)

Nice Observation :).

Definitely sleep is the most important thing. My anxiety went under control and I broke two records today. I ran 2km in 10 min for the first time and solved A-E just a little more than an hour.

wow that's great!!

bros well rested and on crack too

Can someone please explain D to me?

If any index $$$i$$$ is part of the latter half of a tandem repeat of length $$$2j$$$, then $$$a_i = a_{i - j}$$$ (considering '?' as equal to anything) must hold, lets say $$$good_{i, j} = 1$$$ if this is satisfied for a given $$$(i, j)$$$ and $$$0$$$ otherwise. We can clearly calculate these values of $$$good_{i, j}$$$ in $$$O(n^2)$$$ time.

Then any index $$$i$$$ to be the start of the second half of a tandem repeat of length $$$2j$$$, $$$good_{k, j} = 1$$$ must hold for all $$$i \leq k \leq i + j - 1$$$. This can be checked in $$$O(1)$$$ by storing prefix sums of $$$good_{i, j}$$$ or in a total of $$$O(n)$$$ over all $$$i$$$ by just iterating in decreasing order of $$$i$$$ and keeping track of the most recent pos $$$p$$$ where $$$good_{p, j} = 0$$$.

So for each $$$1 \leq j \leq \lfloor \frac{n}{2} \rfloor$$$, we just iterate on $$$i$$$ in decreasing order and check all possible tandem repeats in $$$O(n^2)$$$ time.

Code — 251486634 ($$$i$$$ and $$$j$$$ are swapped compared to my notation here)

thanks broski

I did $$$n^2$$$ DP, where $$$dp[i][j]$$$ is the maximum length of repeat string we can get if the first half of the string starts from $$$i$$$ and the second half of the string starts from $$$j$$$

Can you explain your code briefly?

I think tourist's solution for problem D is simple and easy to understand. He did it in under a frickin minute.

Linear search on answer.

how to solve b ? I iterated over numbers and kept an array of pairs which holds the options available for the previous number which are leave it as it is or do the operation on it and based on this info I can decide for the current number what I can do for it but this was wrong

greedy thinking

Is the formula for F OEIS-able?

I have a feeling it is not, as it depends on 3 parameters, although I might be wrong

Well, still, it seems kind of standard

It is easily googleable https://math.stackexchange.com/questions/562119/difference-of-two-binomial-random-variables

C was very similar to "binary path" problem , which came in a recent contest

Why are constraints on E so low?

Yeah, it's a bit strange, since we could solve it in O(n). At first I thought it is some kind of DP problem after seeing the constraints.

Is the checker algorithm runs in $$$O(N^3)$$$? Lol I dunno

Is problem D a prefix sums problem? I have an approach that looks like it should work.

Simply check if the number of values that correspond with each other in some substring

s'is|s'|/2.My brute force solution for D got accepted. Please, can someone hack it, since I know it's not an intended solution

abc were easy but because i am slow and have skill issue i will lose rating xD

Applied BFS on Problem-C, Now I feel stupid after checking out other solutions

Actually I think BFS or DFS is the most straightforward solution to it

Ok so the thing is, I completely forgot that you have to keep a VISITED SET in BFS.

That was the reason for TLE.

Now with the visited set my sol. gets Accepted

Just your average newbie mistakes :)

[submission:251541342]Please tell me why my C is wrong

void solve() {

}

wow

><><><><is string algorithm required in problem D

It's not, only DS or algorithm you need is prefix sum or segment tree

@awoo Are you all right? If you have trouble making problems, please don't throw garbage around.

If you think the problems are really good, you can vote against me because it really saves time for all of us.

anyone solved C using DP?

Yes me

How?

https://codeforces.com/contest/1948/submission/251513695

Please share your idea.

So the idea is, we always move forward and never make a move backwards. So we take dp[i][[j][turn] which denotes we are at ith row and jth column and if it's our turn (1) to move or not. Then we check if the current turn is our turn then we can move right/down/up (we check all 3). If it's not our turn we check if the direction is forward or not if not we return false saying there is no way using this path

Thanks..It seems easy to think.

initialize dp[0][0] as 1. if there is a '>' you can go to the next coloumn from left or up or down.

Can you explain a little bit elaborately? I still can't get it!

Suppose you are at str[0][i] then you can go to str[0][i+2] if str[0][i+1]=='>' OR you can go to str[1][i+1] if str[1][i]=='>'. The same is applicable to str[1][i].

This is the basic concept.

And for the dp part -->

Initially you are at str[0][0] position, which is true. Now while traversing both row at the same time if you encounter '>' then you will check the dp value of previous coloumn of the same row and the same coloumn of other row. If any of these holds true, then you can go to the next coloumn of the current row.

I understood it now! Thank you so much!

G was a nice one)

Problem C can be solved using a very easy approach instead of graph algorithms or dynamic programming. 251492497

Can u explain the logic

You can see that you only have control over cells in positions either like (0, 2k) or (1, 2k + 1). So, you need to consider situations where you can't move to the cell on the right.

...<...

..<....

or

...<...

....<..

Let * be the cell in which you make 1st type of move. (i.e., you move in any four direction) it will not matter either '>' or '<' is in the '*' place.

Example string1:

Output1: YES

Example string2:

Output2: NO

if you are in the place '*'. then, there must be at least one '>' to the "right or down" or "right or up" from the current cell. if in both places '<' is there. then we can never move further from that cell.

So we checked for some '*' cells, from which we could never move further. if there are no such cells, we can always reach our destination.

what's the logic behind that ?

I found that the problems, up until E, weren't particularly interesting, they were more of implementation. I'm unsure if my solution for E was what was expected, I believe the constraints could have been tougher, since we can prove that no clique size can be greater than K and that there is a construction in which K size clique is possible.

problem C was similar to recent contest's problem "binary path"

not really imo

It's not that similar but while solving I remembered that problem.

The data range of problem E is so humorous that I stuck on it for 30 mins.

So I didnt even have time for the last problem. Sad.

Problem A,B Video Editorial (Audio : Hindi) If you are a Beginner, then You can refer to this video for explanation of problem A and B. I hope it's gonna help you if you weren't able to solve A or B during the contest !

YOUTUBE Editorial Link --Click Here

I can't believe how +3000 people come up with solution on D on time, cp too competitive 🙄

No ,I think there is a brute force type solution of O(n^2) that is working or as told by Pirate_King below the pretest cases were weak allowing O(n^3) fully brute forced solutions

Now for O(n^2) solution :-

SEE THE SOLUTION LINK BELOW YOU WILL UNDERSTAND EASILY

here we are brute forcing or looping for half length of tandem repeat hence we will make loop from i=1 to i=n/2 then for each length i of tandem repeat we will check with another loop from j=0 to i+j<n whether that length tandem repeat is present in string or not

By checking whether current_index and current_index+currlength of tandem repeat we are searching are equal or not if equal then we will take count of consecutive index which is satisfying this condition if this count becomes equal to currenttandemsearchlength then the current answer becomes equal to currenttandemsearchlength now will calculate this answer for every length iteration and at last will print the answer(which automatically stores max length)

254855666

Your approach is very nice (Never seen it before). Is that like a standard algorithm or based on something ? I was curious of how one could modify the 2nd inner loop had the question said that tandem repeat is even-lengthed string where 1st-half and 2nd-half are reverse of each other.

tanishgoyal16 My solution is updated kindly recheck

Look at the hacks bro. The testcases were weak so $$$O(n^3)$$$ solutions passed. Solve count gonna drop significantly after system testing

If I hack someone's submission successfully,does this hacking test be added to final tests?

Why do you ask?

I want to know if I having a false solution but no one hacked me.Others' hacking test could affect mine?

Yes, sadly

Did anyone else also find this observation in problem c (diagonals)

The meaning of passage C was too ambiguous.

Yes was confused between that robot have to reach last block(2,n) after performing both the operations OR robot have to just touch the last block

P.S. robot have to reach last block after performing both the actions is correct way for C

Actions

There is a robot that starts in a cell (1,1). Every second, the following two actions happen one after another:

Firstly, the robot moves left, right, down or up (it can't try to go outside the grid, and can't skip a move); then it moves along the arrow that is placed in the current cell (the cell it ends up after its move). Your task is to determine whether the robot can reach the cell (2,n)

Wow, i thought it just had to reach there and was having pain implementing, thanks for this

Is anybody aware of the reason 251440010 results in a compilation error?

Interesting -- apparently this is caused by a bug in the compiler. I also could reproduce the error with custom tests. Meanwhile I could avoid the error by moving the definition of

`vis`

to global (and initialize them appropriately).By C++ standard you can't declare an array of variable length. The size of it must be constant expression (known during compilation). However, there are compiler extensions that allow them, but anyways compiler is not obligated to have them. It seems that this particular version doesn't. Or it doesn't support boolean arrays of variable length explicitly. In any case this can't be considered a bug.

I tried resubmitting the same solution, replacing the array type from bool to int 251558731. Evidently, the type of the array does not seem to matter in this case. Later this contest I submitted 251491928, which also uses arrays of variable size, but doesn't get CE. Just curious what exactly causes the bug, because the compiler logs aren't very helpful

AFAIK that is a GCC extension and is supposed to compile.

It seems to me that it has to do with the ordering of the dimensions in terms of constants. Simply changing the definition from $$$vis[2][n]$$$ to $$$vis[n][2]$$$ resolved the issue

I get TLE for the problem C although the time complexity of my code is just 4 * n. I get TLE on test 1 but it runs fast in my computer. Help me please. https://codeforces.com/contest/1948/submission/251550212

You declared this array

`char a[2][maxn];`

Then below, you accessed at

`a[2][j - 1]`

(`a[2]`

is out of range, so it will cause an undefined behavior)thank u so much, I got AC. But why didn't I get complication error instead of TLE

Because your code is not complicated enough

I got fst in E when the contest was not over yet, haha!

Optimistically thinking, you are the first 18 people to solve this problem. It's enough to show that your programming level is really very high (maybe)

May be one day I will also be one top 18 people to get this problem (❁´◡`❁)

The checker did not checked if a is a permutation.

I got impacted too, but I don't think I was among first 18 people.

I was among first 18 people to get an AC without printing a permutation.

Below are The Few Submissions which was same in the today's contest. Please recheck it accordingly there may be more, and they should be penalized for it. It makes the competitive programming unfair.

- 251535056- 251535221- 251537839- 251533059- 251538840Also their solutions for B are extremely similar. In fact, both laxmiprasanna_ and sudhanshu_24 have the same code verbatim: -251532572 -251536131.

Or it's just a coincidence haha.

No..!! Not a Coincidence at this extent. The codes are Exactly same. MikeMirzayanov Please do something with this.

((Problem B: (Test: #2) wrong answer expected NO, found YES [452nd token]))

I want to see 452nd test case.. Can it possible???Code: 251557312

Thanks a lot...__ But how I find ithe 452nd test case?? Plz, tell me the process...

I can only get small testcase.

You can write

You can seperate the case with "*" but can't use space/enter.

When the testcase is not too large, you can find the testcase in Checker comment.

Wow!! Thanks for sharing the trick.

It's really helpful... I came to know that trick by you..

Thanks .....

Can someone explain the second testcase of problem E ? vertex 4 is a part of 2 cliques (1, 2, 4) & (3, 4, 5)

Presented arrangment of values really allows to relate 4th index for both cliques, but we don't need it to be in both cliques the same time (since we need splitting, not coverage of graph)

So we choose to relate it to first clique and leave second clique without it (which doesn't prevent the remnants of the second clique from still being a clique)

Thanks, got it.

I see we got an issue with the checker of E... but can we start hacking on it now? Open hack is not available for E yet.

There are

`40*80`

distinct testcases, and there are 5 test files (1 sample and 4 hidden).I believe system tests do cover all the distinct testcases.

The only hack possible should be TLEs by repeating the same test if someone is doing some bruteforces.

Yes, but I did find a solution that could possibly get hacked with TLE, that's why I want to try :)

This was last. No more educationals for me.

In problem B , my code 251556695 is failing on the 302nd token of test case 2. My code seems correct to me .Can any one point out my mistake ?

input:Expected answer is YES.

Thanks! It was just a careless mistake I did. I wrote

`ans.size()>1`

instead of`ans.size()>0`

:(For problem E, case n = 5 and k = 4, this assignment gets accepted:

a[1] = 2, a[2] = 1, a[3] = 4, a[4] = 3, a[5] = 5

c[1] = 1, c[2] = 1, c[3] = 1, c[4] = 1, c[5] = 2

even though the node 3 the is in both cliques (1, 2, 3, 4) and (3, 5).

I guess a pair is not counted as a clique, but the definition in the problem does not specify this.

It is not in both cliques. You define cliques by the array c. c[3] has exactly one value, thus it is in exactly one clique. The constraint is that the nodes you mark with the same id really form a clique, not that those are all the cliques in the graph.

Hack my solution for D (it's O(n^3)). https://codeforces.com/contest/1948/submission/251558115

It got hacked in Python, but the C++ one still hasn't got hacked.

For C, any specific reason that grid is limited to 2 * m instead of n * m?

Yeah, my approach was a tricky one: each diagonal of length 2 served as a barrier, and hence either one element in that diagonal has to be a right pointer. This approach makes sense on 2 rows and is apparently harder to extend to more rows. Other approaches are also possible for this problem though.

You may take a look here at my solution: https://www.youtube.com/watch?v=_12qOUDlWTE&ab_channel=DecipherAlgorithmswithSaptarshi

Hello !

I need help please for problem B , i couldn't see why my code is wrong .

it's giving me WA in test 2 (testcase 98th). This is my code 251574144

I think you're splitting a_i only if a_(i+1) is lesser. What you missed is, if you're splitting some element, all the previous elements must be splitter.

For {11, 11, 11, 12, 9}, I think your solution will only split 12 and eventually return false because 11 is greater than the 1 that came from 12.

I explained a pretty similar thing in my editorial here: https://www.youtube.com/watch?v=_12qOUDlWTE&ab_channel=DecipherAlgorithmswithSaptarshi

Thank you ❤️

Consider the following case:

Clearly, the answer is "YES", as the array breaks up into 1, 1, 1, 2, 6. However, the output is "NO", as your code only splits apart 12 (but not 11) after comparison with 6.

I only realized this after WA on the same testcase, and did the following:

SpoilerLet

ptrbe -1. Whenever v[i] > v[i+1], setptrto i. Then, go through i=0 toptrand break apart each such 2 digit number.Thank you ❤️

Folks interested may take a look at my explanations for problems A to E in this round! Tried to touch upon the intuitions that I used to solve those problems during the contest. https://www.youtube.com/watch?v=_12qOUDlWTE&ab_channel=DecipherAlgorithmswithSaptarshi

https://codeforces.com/problemset/submission/1948/251537282 Can someone please help me find error in this logic for Problem B

Link the cf submission or format your comment properly if you want people to be able to read your code...

https://codeforces.com/problemset/submission/1948/251537282

Problem G is so cool!

why TLE on problem C , using dp solution : submission

Maybe try using array for dp instead of vector

How to solve E ?

HintWhat is the biggest size of clique possible?

Answermin(K, N)

You can make a permutation of K elements such that "magic distance" for any pair of indices does not exceed K.

Example that might lead you to PatternFor K = 6 : (4 5 6 1 2 3)

For K = 7 : (5 6 7 1 2 3 4)

You have included 4 twice in k=7 example...

finding the edge case for a greedy solution is probably the hardest thing in the universe any one have any tip for this ?

https://www.youtube.com/live/6wd0ccbYgg0?si=Iq4ptF7Wa1ztl8Nm Someone was living streaming the contest

Their main account Antonio_Colapso_07

I believe it's not the main. For sure It's the same guy, It's just another alt of his. I was also looking for his main as he said in his stream is max rating is 1847.

(I don't know why i was obsessed for finding his main acc. I just didn't like how casually he's streaming and people are interacting in the chat. As if, They don’t understand that what he's doing is wrong to the community.)

Please can u write a separate blog so that the whole community can know how this guy is killing the whole spirit of competitive programming. I think his main account should immediately be blocked.

Oh no. I am one of the 18 people. But still will become master!

I couldn't understand one thing, official and unofficial standings are same,but since it was rated for <=2100 ,shouldn't they be different?plz correct/help

for div 3s and div 4s, only "trusted participants" are included in the official standings but it will be rated for <= 1600 and <= 1400 respectively. there's no such restriction for this one so everyone's included in the official standings but it will be only be rated for <= 2100

nice contest

ok great

you are bad speacialists

orz

yes

Nice

Is that contest increase rating

score??problem D can use a BF algorithm to solve it. Can it make the different from other people?

When will the ratings update

Has the system testing ended ?

Really nice observation in F, I enjoy solving it.

Problem D (Tandem Repeat) Video Editorial :

Audio : Hindi

YOUTUBE VIDEO LINK --Click Here

When will the ratings be released??

I'm waiting too, bro

Oh, and d can be n^3, is that what they meant? sad...

Pathetic time constraints given as O(n^3) solutions passed in problem D

What a great codeforces round,I get Expert in this round!

## Thanks!!!

Scratched my head debugging for a hash-based solution for D during the contest and WA3

When I found the correct solution only takes 25 lines of trivial code:

CodeC is a cute problem, thanks!

Dear Organizers,

I write to address the plagiarism accusation I received regarding my submission for Problem C — Arrow Path on Codeforces. It has been brought to my attention that my solution bears a resemblance to that of another user, Aditya_Sarthak/251536325. I wish to emphasize that any similarities between our submissions are coincidental, and I am perplexed by this discovery.

I would like to point out that my submission, under the user ID Shivam_0001/251506209, predates Aditya_Sarthak's submission by approximately 42 minutes, as verified by submission timestamps. Additionally, the coding template utilized in my solution remains consistent with my established coding style from previous submissions, further substantiating my claim of innocence.

I kindly urge you to thoroughly consider these facts before rendering any judgment. I trust that a fair assessment of the evidence will exonerate me from any wrongdoing.

Thank you for your attention to this matter. Shivam_0001