Very fast editorial! Thanks!

I was too scared that $$$O(2^n \cdot n^2)$$$ is too slow for E so I ended up figuring it out in $$$O(2^n \cdot n)$$$ with $$$O(2^n)$$$ memory.

Can't solve D :(

How to improve solving greed problems

Damn! Editorials are out even before the system test. Coolest round ever!(for me)

Why my approach to problem C is wrong?

We need for every $$$1 \le f \le p$$$ to check if:

We end up checking the value of $$$f ^ 2 + f$$$ (mod $$$n$$$), which is equivalent to checking $$$m ^ 2 + m$$$ whereas $$$m \equiv f \mod n$$$.

From the previous reasoning, it is enough to check all possible values, $$$1 \le f \le \min(p, n)$$$.

The vague part is going from $$$f$$$ to $$$m$$$. Why isn't it correct?

You're given 3 problems and two hours to solve them

I have trouble understanding the additional question at the end of the tutorial for problem c:

"Question, can you build the test that required Vesper to use $$$x$$$ more than $$$100k$$$?"

Can somebody explain the question please? (not the solution though, I wanna solve it ^^')

why it will be tle ? i only use upper_bound get AC 197098569

it is logically very obvious that

 (2n*(2n+1)/2)%n=0

So, logically it is obvious that if we try out values from 1 to 2*n and do not get answer then we would not get answer after that too. But can anyone prove it mathematically though? Still cannot convince myself about the 2*n thing.

Why is my submission failing for B

Easiest div2 d I've ever seen, I wish I registered for the contest

I think in task F you have used about 150 cpu-days

Why is this giving the wrong answer for the maximum value in problem D?

:( Came home 1 hour late so couldn't join. Sad thing is I knew how to solve F because I did it in an approximation algorithms course before.

F actually highlights something that is missing from Polygon (or maybe some online judges in general): the ability to declare that "this is the correct output file" without having it be generated by the model solution. In contrast, CMS (e.g. at IOI) treats the output files as the true ones and doesn't care if you didn't generate them using the model solution.

This is a niche usage of course, but it would be nice to give approximation problems without hacks like "the last line is an encoded version of the true answer". Approximation algorithms aren't really the CP meta right now, but e.g. for one task in an ICPC-style contest, why not? Compute the correct answers using some slow brute force or a commercial ILP/SAT solver and the checker can just check the approximation factor.

Randomised solution for E:

DFS going deep for 2 random child every time. If you get loop — check if union of neighbours in it covers everything. If it does, then we found required loop in editorial. Repeat until you have spent almost 2 seconds. Print "No" otherwise. Not sure how to estimate probabilty of failure though.

Btw, fun fact about problem F.

There is a paper that proves that under SETH it is impossible to solve problem F in $$$O(m^{1-\varepsilon})$$$ time per query if we would need to answer queries online, there were also edge deletions, and we had to provide a $$$2-\delta$$$ approximation (here $$$f$$$-factor approximation means that we should provide an answer that is not smaller than the actual answer and at most $$$f$$$ times larger; I am not sure whether this theorem can be generalized to the notion of approximation that is used in problem F).

In problem D it should be $$$T2=max(0,m4−∑yi=0⌊l′i2⌋)$$$ not $$$T2=min(0,m4−∑yi=0⌊l′i2⌋)$$$

The system test of E is weak. My brute force solution (with special check for cut-edges) passed it.

By the way, there is another solution for F.

Instead of running a binary search, you can just start bfs with updated vertexes and existing distances, not from scratch. This is too slow, but we can not run bfs each time, but only when sum of immediate increases (differences between end and start of added edges -1) is half of the current answer.

This is correct because this sum is the upper bound of the answer decrease.

The more tricky question why it is fast.

1. After distance is less than $$$O(\sqrt(n))$$$, it is $$$O(nsqrt(n))$$$ even if we run bfs each time
2. While difference is big, each edge is decreasing distance by at least factor 3/4 for at least $$$O(\sqrt(n))$$$ vertices.

This looks like very rough bound, probably in practice it's better.

what is the specific test in C? (last sentence in editorial)

Problem C has a brilliant name. No thinking, just pull your luck ))

In Problem C, I was shocked. I write AC code but I thought it was WA. Because I thought the loop needed p time every test case. if I loop run P time then I got TLE. That's why I didn't submit my code. but after finishing the contest I submit my code and it was an AC code.

void solve()
{
    ll n, x, p;
    cin >> n >> x >> p;

    ll rem = n - x, sum = 0;
    if( x == 0 ) rem = 0;
    vector< int > v;
    for( ll i =  1 ; i <= n * 2 ; i++ )
    {
        
        sum += i; 

        if( sum % n == rem )
        {
            cout << "YES" <<  endl;
            return;
        } 
        if( i == p) break;
    } 
    cout << "NO" << endl;
}

Bonus question, can you guess the total number of cpu-days we have used to compute all the answers? Post you version in the comments!

To find the diameter of a general graph, we will need $$$n$$$ BFS, and each takes $$$O(n+m)$$$ time, overall $$$O(n*(n+m))$$$ per query. $$$O(n*q*(n+m+q))$$$ per testcase.

This problem has 80 testcases, assuming worst case $$$n=m=q=10^5$$$, its $$$80*10^5*10^5*(3*10^5) = 2.4*10^{17}$$$, assuming $$$10^8$$$ operations per second, on the normal computer we need $$$2.4*10^9$$$ seconds = ~3e5 days.

I was expecting the answer for generating testcases to be < 100s, using 1e5 parallel cpus.

Bonus question, can you guess the total number of cpu-days we have used to compute all the answers? Post you version in the comments!

7

How to solve A using DFS?

Is there a ")" missing here for D?

and isn't max?

thank you for fast editorial

Why my solution got TLE even if it is O(nlogn).

My Solution: https://codeforces.com/contest/1804/submission/197105822 Can someone help me, please?

can someone explain why we are counting "at least one dark window segment" in problem D rather than one dark window segment .

In D, in last line, I think it should be max not min.

F is a beautiful problem with a very scary statement

cool way to get the correct answers in cool problem F

Problem E: I was blown by the idea of using the first set bit to represent start of the circle. Very clever.

In problem D, my approach for finding the maximum value is to, first calculate "01" or "10", then "00" and at last "11", and assign this as two widowed rooms, and the remaining ones are single windowed. Can anyone point out my mistake? submission

What I do in C is, I run a loop from i = 1 to 1e5 and checking if i*n-x exist as sum of p natural number in logP overall time complexity is O(n*logP) but still it got TLE Why?

https://codeforces.com/contest/1804/submission/197293170

I have received a mail that my solution of C problem in Nebius Welcome Round is coinciding with Somebody else . In mail it was written , to post about the evidence .

C Problem was not too difficult for a person with average coding skills . The only trick in C was to get a control over the loop . I have seen many tutorials of past contests and in C problem , I used that for controlling the loop as the most common approach in these types get solved in nlog(n) or n root(n) . So I did it for n root(n) and then the code was simple a Brute force logic . It took me a number of contest and practice to reach specialist . Please reply me if i need to submit any supporting proof and what else can i upload . Please help GlebsHP , MikeMirzayanov . please do reply.

For Problem C.. I want to understand the repetitive behavior of the function (sum_from_1_to_2n % n), Please mention a mathematical or intuitive (better :) reasoning..

F is really fascinating.

Can anyone give me any hint for problem H? Is the problem approachable with bitmask dp and meet in the middle?

There is a formula mistake in tutorial of problem F.

Having the correct value of $$$c_(G_i)(v)$$$ we can use the binary search ...

That should be: Having the correct value of $$$c_{G_i}(v)$$$ we can use the binary search ...

Auto comment: topic has been updated by GlebsHP (previous revision, new revision, compare).

Simple DP for D... why is the editorial so complicated?

Auto comment: topic has been updated by GlebsHP (previous revision, new revision, compare).

I am very curious how the data of problem F was made, LOL

It is a really interesting problem, lots of thanks to the problem provider!

Question, can you build the test that required Vesper to use $$$x$$$ more than $$$100k$$$? There is exactly one such test.

Can someone tell me what this testcase is?

Also how do you come up with this conclusion and prove this to yourself.

Like I'm just not convinced how the solution in the editorial won't give TLE (even though I wrote the code for it and it didn't, but still in my head I feel it shouldn't work). Like what if this was a testcase

2
1e5 a 1e9
1e5 a 1e9

So here min(2n, p) will be $$$2e5$$$ and let's say I choose $$$a$$$ such that the answer is $$$No$$$ or it goes more 1e5 to say $$$Yes$$$. So shouldn't this cause TLE.

For the editorial of problem C, can you prove the following line?

"The remainders of x of modulo n will repeat after 2n steps".

In other words, How can you prove that, sums of all integers from 1 to i (1 <= i <= 2*n) will generate all the remainders from 0 to n-1, when diving by n?

Question, can you build the test that required Vesper to use x more than 100k ? There is exactly one such test.

This is from the tutorial of solution Of C(PULL YOUR LUCK) Could someone please help me to understand that case

Great problem C! Would like to share my approach. I observed a fairly obvious thing, for f=1, you will land on (x+1)%n [obviously], after that you can keep adding i (2<=i<=n) to the latest number. Eg: For n=5, x=2: 2 (+1)-> 3 (+2)-> 0 (+3)-> 3 (+4)-> 2 (+5)-> 2 , so now you again reached your starting point (2 in this case). This will hold for any odd n, as n*(n+1)/2 will by k*n which is congruent to 0 (mod n). So after n such steps you will always reach the starting x. After that the pattern pretty much loops, so we don't need to add more elements. For even n, this will not be true! (Reason: n*(n+1)/2 and n=2k => k*(2k+1) which need not give remainder 0 with 2k), but what will hold now is the same pattern twice! For eg: n=4, x=2: 2 (+1)-> 3 (+2)->1 (+3)->0 (+4)->0 (+1)->1 (+2)->3 (+3)->2 (+4)->2 !! (see how after one chain we reached 0 and not 2, but after 2 such operations we reached 2 again, proof is pretty simple, now as n=2k => 2n = 4k, so 4k*(4k+1)/2 = 2k*(4k+1) which is congruent to 0 (mod n=2k).

After that you can store the n values (for odd case) and 2n values (for even case), and find the minimum index of 0. If there is no 0, that means for any p, you cant ever win. Else if p>= min_index : yes Else: no Here is my code for reference. Hope this explains well!