Hello again Codeforces!

The Forethought Future Cup Final round will start on May 4th, 10:05am PDT. **This round will be rated for everyone**. There will be three separate rounds, one for onsite contestants, one for div1, and one for div2. Onsite and div1 will have the same problems. Each round will have 6 problems and be 2 hours long.

Here is a table of the onsite contestants.

The onsite round has cash prizes:

- 1st: $500
- 2nd: $250
- 3rd: $100
- 4th — 10th: $50

Thanks to ismagilov.code, mohammedehab2002, Jeel_Vaishnav, Learner99, 300iq, dojiboy9, fortune, y0105w49, KAN, arsijo for testing and coordination. Also, thanks to cyand1317 for one of the problems. Of course, thanks to MikeMirzayanov for Codeforces and Polygon, and for allowing us to host the round.

There might be some interactive problems again, so please read the interactive problem guide if you haven't before.

If you're still interested in applying, please fill out the form.

### Updates

**UPD 1** The scoring distribution will be:

- Div2:
**500-1000-1500-2000-2500-3000** - Div1:
**500-1000-1500-2000-2500-3250**

**UPD 2** Pictures from the onsite round: https://codeforces.com/blog/entry/66876

**UPD 3**: I'm sorry, but to prevent the leak of onsite results, we will postpone the start of system testing a bit. As soon as the closing ceremony finish at Forethought office, we will immediately start the system testing of the rounds. Until this time, the rounds will be hidden. But don't panic, this will only be temporary and we will return everything soon.

**UPD 4**: The results will be in around 90 minutes after the end of the competition.

**UPD 5**: Tutorial: https://codeforces.com/blog/entry/66878

**UPD 6**: Congratulations to the winners:

Onsite contest:

1 | scott_wu |

2 | ACRush |

3 | neal |

4 | xiaowuc1 |

5 | Svlad_Cjelli |

6 | Ra16bit |

7 | ll931110 |

8 | stevenkplus |

9 | yzyz |

10 | pmnox |

Div 1 contest:

1 | Benq |

2 | Petr |

3 | Errichto |

4 | aid |

5 | Endagorion |

Div 2 contest:

1 | Ezys |

2 | nitishk24 |

3 | gonP |

4 | trabbbart |

5 | Randl |

Auto comment: topic has been updated by Lewin (previous revision, new revision, compare).So excited ! Looking forward to see you guys !

tap_tapii, good luck ♥

I hope that there will be no issue like the last contest. :)

woohoo dinosaurs woohoo

Best of luck with your Forethought Future Cup — Final Round contest for onsite contestants. I hope that competition will be so higher.

good stuff Svlad_Cjelli very nice work

How many interactive problems do you guys expect? I think more than one will appear lol.

Best of luck ll931110

Good luck Emiso ❤️

I propose that round authors stop putting the interactive problem guide in any round announcement. Like 95% of the time all this does is tell the participants there are interactive problems. Interactive problems have been around for 3 years now; I think people know a thing or two about them. Nobody would say "This contest might have a DP problem, so familiarize yourself with arrays", so why should we do the same for interactive problems?

Not the best analogy though: "this is DP problem" would typically be a hint (and it is never written in problem statement), while "this is an interactive problem" is something that is written in problem statement and isn't secret information.

You're right, my analogy was not good. I think a better one would be announcing that "This contest might have GCD in the problem statement". It's a fairly common occurrence, and it does occur in problem statement, but you still wouldn't put this in a round announcement.

Seems like being in top 300 was enough to go to the onsite. I'm surprised it's that low — are so few competitive programmers there?

Not many people from the USA compete in Codeforces because of timezone difference.

Ok but onsite.

stop doing interactive problems!

The scoring distribution?

Contest on a weekend at 10:30 AM? Am I dreaming?

No, you are in the USA.

finally weekend contest.

Div2: 500-1000-1500-2000-2500-3000Div1: 500-1000-1500-2000-2500-3250Finally , we have a balanced scoring distribution.

OMG tourist is here...

In Problem C, how (2,1) can be a move in Sample 1, because in problem it's mentioned that for every

ionlyi and i+1are adjacent. So, for 2 how can 1 be it's adjacent??Edit:It's sorted now.How to solve B?

I took greedy approach, for a particular index (i,j) assigned a[i][j]=min(a[i][j],b[i][j]) and b[i][j]=max(a[i][j],b[i][j]). Then checked whether the new matrix a and b are increasing.

how did you come up with this solution ?

Not really a proof, but just an intuition:

Consider min_1, max_1, min_2, max_2, where min_1 < max_1, min_2 < max_2, min_1, max_1 are in the same cell and min_2, max_2 are in the same cell and min/max_2 goes after min/max_1. If min_2 <= min_1, then surely min_2 <= max_1 as well. Therefore, the best you can do is to put min_1 and min_2 in the same matrix.

Personally, I came up with this after realizing that since we don't care about minimizing the number of swaps and such, it is best to treat two matrices as not two separate matrices, but a matrix of pairs which needs to be broken down. I.e. conceptually, you create the answer matrices "from scratch", ignoring which matrix they came from originally. And so, if you reformulate the problem is "what's a neat way to construct needed matrices from the available values?", the answer comes naturally after trying a few ways.

Thank you for sharing your intuition , It is helping guys like you who make codeforces community so great.

Можно ли как-нибудь участвовать вне конкурса во время проведения раунда?

Thanos gonna snap solutions in the systests.

-: RIP :-Div2C has an

unintendedsolution, setting the time limit to 1s is too strict.I coded a $$$Nlog(N)$$$ solution, for $$$N=100000$$$ I don't think it's too strict.

Div2C can be solved in NlogN by using set, not strict at all.

I coded O(n)

Can you tell your approach?

solution, the solution is based on checking possible moves between question i and i+1: 3moves = {i+1,i}{i,i+1}{i,i}, 2moves = {i+1,i}{i,i+1} 1move = {i+1,i} or {i,i+1} if first occurence of i is greater than last occurence of i+1 and vice-versa.

For the people who are commenting, I know that the intended solution is O(N) or O(NlogN). I'm saying that there are an

unintendedsolution which was obvious to me, and it would run just over a second.how on earth do you solve B, i coded some BS random solution that probably fail system test 99% chance

It's enough to check rotations that are divisors of $$$N$$$.

But how do you check a rotation?

RollingHash

no pun intended xd

Or don't use hashes and just do it linearly each time. The complexity will be $$$O(n \cdot divisors)$$$ which should be small enough.

ok thanks

In fact, you only need to check the rotations that can be written as k=n/p for p = {any primes that divide n, including n itself}. If a smaller rotation exists, then it will be found by this method. For example, if k= n/2 is a valid solution, then k=n/4 will be as well since if you do 2 steps of k you will get to n/2.

I did hashing -> pi function.

You can observe that the

`k`

used to rotate the segments must be a divisor of`N`

. This means that there are at most $$$cbrt(N)$$$ candidates for`k`

, therefore we can simulate the process. We can see if some state is equivalent with the initial one in`O(N)`

, but I think that`O(N*log(N))`

is also goodWe can represent the circle as a string (the "characters" are vectors of distances to neighbors) and then use Z function to find the period of the "string". The answer is yes if and only if the string is periodic (at least, my solution relies on that :D).

I used this method as well.

Can you elaborate?

You can check the editorial for more info, it has this approach.

How To Solve D?

(UPD1 : Solved.)

Damn, almost finished E.

Benq stole a hack from me right when I was submitting the test. =(

You did the same to me. :P

But you are first so you have no right to complain.

What were your tests? Should I be worried about my solution?

How to solve Div2D/Div1B? I suppose it is some kind of gcd of sequences that forms lines with same length, right?

I believe you can iterate over proper factors of $$$n$$$ and brute force check them all.

How to solve Div2 E / Div1 C?

All I could think was if the number of 1s at your turn become greater than n/2 you lose. (i.e. if at any point you have to make any 1 to 0), the other person will just remove the rest and you are left with < n/2 non-empty stones.

That can be inducted to "if count of minimum number is greater than n/2 you lose."

Why you only lose on this case?

Otherwise, you can win by making the count of the minimum number greater than n/2.

Base of induction: if you have > n/2 zeros you lose. Otherwise if you have 1..n/2 zeros you win.

Induction step: suppose for every k=0..m-1. If smallest is > n/2 you win, otherwise you lose.

Suppose m is smallest value. If there're $$$> n/2$$$ of m, you will have to reduce at least one of them but no more than n/2, Your opponent will be in winning state for $$$min_v < m$$$. So $$$> n/2$$$ is losing state. If you have $$$1 <= cnt <= n/2$$$ values you can select $$$ n/2 $$$ bigger values and send opponent to losing state.

if more than half of the piles is zero. you lose. if there is at least one of the pile is zero (but less than n/2), in one move you can make half of the piles zero and you win.

if there is none of the piles is zero but there are more than half of the piles is one, in one move you will get at least 1 of the pile is zero, therefore you lose

if there is none of the piles is zero but there are less than half of the piles is one, in one move you can make half of the piles one and you win . . . and so on

Yeah, but how do you solve it from there :D, my DP skills are Div3. Nevermind I got baited by the constraints.

I just barely ran out of time before the contest ended, but I am pretty sure you need to use Sprague-Grundy Theory. If you have a piles with 1 stone and b piles with multiple stones, then nimber[a,b] (dp[a,b] if you prefer) = mex(childrenNimbers(a,b)) where the childrenNimbers are all all the nimbers of the states reachable from (a,b)

Nope, just check if the count of the minimum number if greater than n/2.

wait.. noo..... I had like 12 submissions and one of them was checking if the minimum is odd and the number of minimums is <= n/2 then you win. xd

How to solve div1 B? My idea was to consider segments of same length and constructing the difference array of their first end point. Now to find valid k, i.e, a cyclic shift coinciding with this one, I used prefix function. And in the end, took intersection of all k's. But what bugged me is the fact that a segment have two lengths. How to handle that? or how to solve it alternatively?

How can a segment have 2 lengths ?

(a, b) and (b, a) with lengths (b — a) and (n — (b — a)) (a < b)

You can take length as $$$min((n + a - b) \mod n, (n + b - a) \mod n)$$$.

doesn't work even for sample test case 1.

What I thought was to take the closer gaps for every segment (which will be less than $$$\frac{n}{2}$$$ and that makes more sense). But it depends totally on your implementation, I guess.

Nah! That solution is wrong, and you can always construct hacks for it depending on implementation. The reason being that suppose you have segments of length l ( < n/2), then there might be a case that these segments aren't cyclic for any k. But a partition of it into two sets is possible, such that for some k, both sets are cyclic.

Is this 53756944 similar to your idea?

Ha, ok I made a mistake :(

You have N points on the circle. For any rotation to be a correct rotation, it's increment has to be a divisor of N. As N <= 1e5, max divisors of N is 128.

Now, store your initial graph as an array of edges, and for each divisor of N between 1 and N-1, make a new graph by adding the increment (and handling the modulo of points between 1 and N) to the points in the old graph, and check if your new graph is the same as the old one.

Complexity = O((Number of divisors of N)*M*C), where C is a constant like logN, depending on how you store your graph.

I have an alternate solution, check for all clockwise and anticlockwise rotations of magnitude X (where X can be any divisor of N) . That should suffice

I used the prefix function as well. However, I first created an array d, where d[i] is the sorted list of clock-wise segments lengths of which i is an end point. For example, if n = 7 and node 1 is connected to nodes 2, 4, and 6, d[1] would be {1, 3, 5}. I then created an additional array d2, which was two instances of d concatenated together. The Knuth-Morris-Pratt algorithm was used to determine if there were more than two occurrences of d in d2.

Edit: My solution was accepted. https://codeforces.com/contest/1162/submission/53757920

Why a runtime error? Link

The fight for the first place was so random. Everybody in top4 has one successful hack and everybody would win with one more hack.

good contest!thanks! And thanks to the weak pretest of problem B .Hacked 2 solutions!!

Why weak? Can you leave your test case?

If you don't check the Matrix B still get the accepted in pretest. my test is: 2 1 5 9 9 9

Hey Bro, how to solve Div2 E and F? help me. Thanks for your help.

Did you use Sprague–Grundy theorem in Div2 E / Div1 C? If yes, how did you use it? Otherwise how did you solve it?

Did the contest just get deleted?

I think something wrong in the contest privacy system.

Probably not. I tried to reload the page and it said, that I am not allowed to view the page. I think it is because of the onsite contest.

But I think we are unable to view anyone else profile as well. https://codeforces.com/profile/misophonic

That should not be related to the onsite contest.

Maybe because they want to wait for the onsite results to be announced before anything else? Still stupid though.

Read update 3 of the post

How to solve Div2 С?

i know i am not very clear but could explain this much now

the contest disappeared O_Q

The page is temporarily blocked by administrator.

i have the same on my profile page o_o

Moreover, all users' profile page is also blocked.

where the contest gone?= =

I'm sorry, but to prevent the leak of onsite results, we will postpone the start of system testing a bit. As soon as the closing ceremony finish at Forethought office, we will immediately start the system testing of the rounds. Until this time, the rounds will be hidden. But don't panic, this will only be temporary and we will return everything soon.

ETA?

EDIT:

"UPD 4: The results will be in around 90 minutes after the end of the competition."Hopefully, not more than 90 minutes after the end.

can I find tasks somewhere now?

It seems it's impossible yet.

https://imgur.com/a/DbGP60G

(sorry, div2 only)

thank

~~nah I thought it's because of Thanos~~my Div2A didn't compile and checker log showed nothing, then i resubmitted the same code with

`//1`

and it passed pretests.53746942, 53747370In your opinion how long will this take?

Due to the statement of Thanos in Div2E/Div1C who snapped at the servers, this round disappeared

How to solve div 2 C?

for each i as starting ,you can take j = i,i+1,i-1 as ending only if starting position of i > last position of j..

Solve this problem separately for each cell. There are only three Alice moves for each cell 'i'. Alice moves the token from i to i+1, from i to i-1, or from i to i. The first and second are not valid if there is a Bob move from source to target cell. The last one is valid if there is no Bob move at that cell.

observe that there are total of (n*3)-2 pairs you can form, just iterate over all the queries asked by bob, when you are at a query, if bob asks x+1 in some question next, then the pair (x, x+1) is invalid. the same process goes for (x, x-1) pairs, also for each question, (x, x) pair is invalid. you can easily keep track of invalid pairs in

`set <int>`

the answer is total —`set.size()`

Thanks to all you guys!

For every

i, ifiis not present in sequence, then the scenario(i, i),(i, i + 1)[if i < n],(i, i — 1)[if i > 1] will always print "No".If

iis present in sequence, then, letposbe the minimum position wherex[pos]=i, we need to changeitoi + 1for scenario(i, i + 1)beforepos. Now, ifi + 1is not present in sequence after positionpos, then scenario(i, i + 1)will answer "No". Same goes for(i, i — 1).here is my test hack in B. too easy, pretest so weak 2 2 1 2 2 3 11 3 3 4

Is div2D KMP?

solve k as divisors of n -> after k units of rotation for each segment there should be one segment replacing it....

I passed pretests with KMP.

aryaman thanks, I have the idea correct, but I forgot some cases in my solution, I've already got AC with kmp

OMG I understood all problems But felt I am disabled man, just solved A I have to train more and more thanks problem setters for this contest

lol , you are not alone

Hope we will become so better soon it is all about time and smart work bro

Looks like thanos snapped the whole contest XD

can U give me scoreboard link please :)

https://codeforc.es/contest/1161

--> 403 Forbidden This site is set up only for users in China. You are blocked because GeoIP says your IP is not from China. Contact us if it's wrong. Menci's mirror for Codeforces

https://codeforces.com/blog/entry/66821?#comment-509597

Peace on you Can any one see that if my solution is true For problem B thanks very much for any one could help :) My solution

Ok... there was a contest round 557... then there is no contest... Can anyone explain what just happened? And why?

https://codeforces.com/blog/entry/66821?#comment-509597

Thank you for the info. O:)

Peace on you He blocked the testing phase to the finish onsite ceremony and he will resume our tests :)

UPD 3: I'm sorry, but to prevent the leak of onsite results, we will postpone the start of system testing a bit. As soon as the closing ceremony finish at Forethought office, we will immediately start the system testing of the rounds. Until this time, the rounds will be hidden. But don't panic, this will only be temporary and we will return everything soon.UPD 4: The results will be in around 90 minutes after the end of the competition.Can we see the closing ceremony at least?

can anyone please explain div2-C question and its approach ??

Do you mean results of all contests or only the onsite one? Because I don't think 90 minutes are enough for systests, and on the other hand, waiting 90 minutes for waiting for results sucks way worse than just waiting for results.

The system testing is started!

User shourov.sust submitted problem A after B within 40second. Is it possible?

Yep

I faced load shedding and submitted A after solving B.

No fastest solvers list :(

When you get +1 rating on AtCoder and +7 on Codeforces.

By the way, why the contest page of the user profile is still blocked?

(UPD1 : Now it can be accessed again.)

Hey, so I've received the message after the contest that the system would ignore my submissions for this contest, because of how similar my code in 1162A is with someone else's solution. It advised me to write here if it is some kind of a misunderstanding, so here I am. https://codeforces.com/contest/1162/submission/53748662 https://codeforces.com/contest/1162/submission/53746682

I can see how it is almost a 1:1 copy, but there are some differencies in spacing and naming. Plus the task didn't require writing a lot of code, so there was a chance two people would write almost the same thing. Can someone clear this up? Thanks in advance.

I've got a warning message about my solution 53749966 for problem A, it seems like someone else used my code during the contest (I used ideone, my bad), how can i avoid any penalties ! Thank you

"Bruteforces" :v

Hello Mike, the first and second place in my Room, the code of their D title can't pass the 65 test point, but they are AC.@MikeMirzayanov

@MikeMirzayanov

MikeMirzayanov

Hi bro, why the D problem's 65 test is not tested? Lewin

wubba lubba dub dub!! All the best guys!!