Thanks for the fast editorial :)

Blogewoosh #8 when?

Thanks for the interesting problems. Overall an awesome contest.Orz. Will make sure I don't miss your future rounds :)

Thanks for an amazing round and fast editorial:)

Awesome contest. Nice challenges! Thank you!

Can anyone explain how to do D1? I am not able to understand

Was O(N √N log(N) ) intended to fail on DIV2 D1?

I believe my submission: 126895459 had that complexity yet it tled on D1 or am I missing something? :(

Thank you for the editorial. In problem A (Simply Strange Sort), why do we have to start swapping odd indices first? Can't we start swapping even indices first? For instance, for this case, why should the answer be equal to 7?

7

6 4 5 3 2 7 1

if we start swapping odd initially. The answer is 7.

• 4 6 3 5 2 7 1
• 4 3 6 2 5 1 7
• 3 4 2 6 1 5 7
• 3 2 4 1 6 5 7
• 2 3 1 4 5 6 7
• 2 1 3 4 5 6 7
• 1 2 3 4 5 6 7

but if we start from even indices, the answer is 6.

• 6 4 5 2 3 1 7
• 4 6 2 5 1 3 7
• 4 2 6 1 5 3 7
• 2 4 1 6 3 5 7
• 2 1 4 3 6 5 7
• 1 2 3 4 5 6 7

Please, help. What am I missing?

I was surprised to see the $$$m \leq 2000$$$ requirement in E, as I have a very simple $$$\mathcal{O}(n^2 \log \max a_i)$$$ solution.

In every step, we try to find the path that

• starts from $$$0$$$
• loops back to itself
• doesn't contain only already beaten caves

that requires the minimum initial strength. Then, we merge nodes on that path with 0, and update the values of minimum initial strength and strength gained over initial strength. We repeat this until all nodes have been processed.

This is clearly correct, since taking the path looping back to itself with minimum required strength cannot hurt you: you end up in a cycle, so you can still go anywhere afterwards, and any solution to the problem has to have you travel a cycle.

To find this loop, we binary search the initial strength required to beat it, then do a DFS (or BFS, the order doesn't matter) of caves we can get to with that initial strength. We maintain for every cave the previous cave, and don't allow going back to it. Once we have two paths to some cave, we have found a cycle, as we could take the one that ends with greater strength in the forward-direction, and the other going back.

We can sort edges from vertices in increasing order of the strength of the monster on the cave on the other end, and break once the monster is too strong for the strength coming from our current cave. If we ever end up in the same cave multiple times, we are done, so every vertex gets handled at most once every step. Thus, we take $$$\mathcal{O}(n)$$$ time every step.

We might need to add $$$\mathcal{O}(n)$$$ loops, and do $$$\mathcal{O}(\log \max a_i)$$$ DFS's every time, each taking $$$\mathcal{O}(n)$$$ time, so the total time complexity is $$$\mathcal{O}(n^2 \log \max a_i)$$$.

Code: 126910619

I like how the same problem is the easiest and toughest in this round, just different constraints.

https://codeforces.me/contest/1561/submission/126865692 ---> TLE one https://codeforces.me/contest/1561/submission/126911328 ---> accepted (same code) my submissions of today A question both codes were same one at the time of contest this gave me tle on test case 11 in system testing but now after the system testing i submitted the same code again by removig some comments it got accepted .... with 31ms

can anyone explain why it happened......

I was quite right with my prediction...

Thanks for the editorial and the contest. It was great.

I think the editorial of 1561C — Deep Down Below meant to say $$$b_i=\max(\ldots)$$$ instead of $$$\min$$$, likewise for $$$p$$$.

What was the role of less space(128 mb) in Div2 D1. And how many iterations can be run in 6 sec time limit?

What's the reason behind stopping $$$O(N \log^2 N)$$$ solutions to pass in Div.2 D2? All the solutions utilizing factors rather than multiples already struggle with $$$10^6$$$ inputs and exceed the given 6 seconds, whereas $$$O(N \log^2 N)$$$ fenwick tree solutions take < 2 seconds on those tests.

The ordering for 1561C - Deep Down Below can be found with exchange argument too. Consider two sequence of monsters A(a1,a2,...,ap) and B(b1,b2,...,bq) now,

since from the editorial it is clear that, initial power level needs to be greater than max( a1 -0 , a2 - 1 , a3 -2 , ... , ap - (p-1) ) if we go through cave A we create two auxiliary sequence from the original sequence A_aux( ( a1 -0 , a2 - 1 , a3 -2 , ... , ap - (p-1) ) ) and B_aux( b1 - 0 , b2 - 1 , .... , bq - (q-1) )

if A is traversed before B the minimum initial power level in this case needs to be x1 = max( max(A_aux) , ( max(B_aux) - size(A_aux))) [ size(A_aux) is subtracted from the second part because before going to second cave power is incremented by size(A_aux) ]

if B is traversed before A the minimum initial power level in this case needs to be x2 = max( max(B_aux) , ( max(A_aux) - size(B_aux))) [ size(B_aux) is subtracted from the second part because before going to second cave power is incremented by size(B_aux) ]

now we need our initial power level to be small in case to A traversed before B , i.e x1 < x2 => max( max(A_aux) , ( max(B_aux) - size(A_aux))) < max( max(B_aux) , ( max(A_aux) - size(B_aux))) . this custom sort rules can be used to get the ordering of the caves.

problem D1 ,how to work sqrt(n) ,please anyone explain this...

In Problem C, I tried Binary Search on $$$x$$$ in my submission https://codeforces.me/contest/1561/submission/126887144, but was faced with the problem of which array to enter first. I tried implementing some sorting algorithm to sort the vectors according to the current power in the binary search, and if for two vectors $$$a$$$ and $$$b$$$, there exists $$$1 \le i \le min(a.\text{size}(), b.\text{size}())$$$ such that $$$\text{power} \le a[i]$$$ but $$$\text{power} > b[i]$$$, then $$$b$$$ has to come before $$$a$$$ in the order. (You can see other details in the cmp function) However, that solution doesn't pass. Any help?

I love how Div 1F and Div 2A are the same problem. I just glanced at 1F to see if I understood the problem (I usually don't), and it was a pleasant surprise.

I have a solution to div1E that does not involve binary searching the initial power and runs in $$$O(NM \log N)$$$. We start off with 1 power. We run Dijkstra on the graph several times, each time starting from the set of defeated caves so far, to find the shortest path to each unvisited cave that requires the least increase to the starting power. This requires keeping track of the power increase along the path. The dijkstra comparator breaks ties among two nodes $$$u$$$ and $$$v$$$ by preferring the one that grants the largest power up to that point.

Technically there are negative cycles, but we just ignore cycles altogether by not revisiting processed nodes. At the end we have a shortest path tree. We can find in this tree the "cheapest" (requiring least increase in starting power) node that has at least one non-tree edge adjacent to it, then "accept" the increase in starting power and visit the path + cycle from this non-tree edge. Each iteration takes $$$O(M \log N)$$$ or $$$O(N \log N + M)$$$ and there are at most $$$O(N)$$$ iterations until we visit all the caves, so $$$O(NM \log N)$$$ in total.

I had a slightly different approach for Div 2 D / Div 1 B.

Calculating the ways you can reach a number by subtracting was straightforward, but I used suffix sums to calculate the sum of ways you can reach a given number by dividing another number.

The code can be seen here.

Very Good Contest.

Can someone please explain the reccurence relation in 1558B- Up The Strip and why it’s time complexity is O(n^2) , Thank you in advance.

Can anyone share a way to find a "closed-form" solution in problem B. Charmed by the Game?

My solution for D has $$$O(M \sqrt{M})$$$ complexity, but doesn't require to roll back any changes. It got AC in 592 ms. I process insertions in the same order as they are given in the input, and use linked list data structure. Each element of the list contains some continuous range of positions that have already had some element inserted right before them.

Any insertion from the input can increase the size of the list by up to $$$2$$$. Each time the size of the list becomes greater than some constant around $$$\sqrt{M}$$$ (I chose $$$520$$$) we need to squeeze all the elements of the list into one range, so our list has only one element in it after that.

Such a shame that I wasn't able to solve Div 2 D1 yesterday since I was so close to the official tutorial.

I wasn't able to solve the floor function inequality, so I used binary search to find the upper and lower bound of $$$z$$$ instead, which makes my solution $$$O(N\sqrt{N}\log{N})$$$. That turned out too slow for the problem constraints though.

Moral of the story: Math is important. Here's my submission

This is my code for Question C, it's giving wrong answer and I can't understand where is the issue.Somebody please have a look and let me know what's wrong with my code.(I am using binary search approach here )

sort(cave.begin(),cave.end());
int ans = 100009;
int l = 0 , r = 100005;
while(l<=r)
{
    int mid = l + (r-l)/2;
    bool possible=true;
    int power = mid;

    for(int i=0;i<cave.size();i++)
    {
        for(int j=0;j<cave[i].second.size();j++)
        {
            if(cave[i].second[j]>power)
            {  cout<<cave[i].second[j]<<" ";
                possible=false;
                break;
            }
            else
            {
                power+=1;
            }
        }
        if(possible==false)break;
    }

    if(possible==false)
    l=mid+1;
    else
    {
        ans=min(ans,mid);
        r=mid-1;
    }

}

cout<<ans;

I was in awe for DIV2-D1, time limit was 6s and O(n^2) was not passing.

Can anyone explain more clearly problem D2div2/Bdiv1

Video Editorial for problem D1 and idea for D2

can anyone explain how to generate all divisors of n with it's prime factors ,div2/d2

in problem D, if i is divisor of x+1 why we need to replace i-1 to i ?

My solution to div2. D1/D2 or div1. B

Lets define dp[I] as number of ways to reach I from N, therefore dp[N] = 1.

We can calculate the value of dp[I] using the formula (iterating I from N — 1 to 1) :-

dp[I] = sum(dp[I + 1], dp[N]) + sum(dp[J * I], dp[min(J * I + J - 1, N)]); 

where J is [2, N / I]

The sum can be calculated with prefix sums in O(1) giving a time complexity of (N log N) where log N represent sum of harmonic series.

My submission: https://codeforces.me/contest/1561/submission/126890430

Why can't use greedy in Div. 2 C (I use greedy and I get AC.)

upd. Solution:

For each cave $$$i$$$, calculate

and then select the cave in the order of $$$p_i$$$ from small to large .

Why "Tutorial is not available" for 1558F

Excellent contest. Thanks very much. I ran my algorithm exactly the same as the tutorial of div2d1 with case 200000 on my own machine and got exactly 6s runtime... so I submitted but got 3.35s runtime... CF's CPU is so fast!

Thanks for the amazing problems as always

cheers

\(^o^)/

Is there a reason why the constraint of div2D1 had to be 200000 instead of 100000?

I keep getting TLE with python even though 150000 would have worked.

Did anyone manage to implement the sqrt complexity editorial solution for D1 with python?

In problem D1, can somebody explain why there is at most sqrt(n) different values of floor(n/x) for all x in [2,n]? is it just a well known thing?

For Problem D:

Can someone please elaborate a bit more on why will sqrt(n) we have no repetititon of the quotient.

For example for 19 If we print out 19/1,19/2 and so on i.e

19 9 6 4 3 3 2 2 2 1 1 1 1 1 1 1 1 1 1.

Why till 4 i.e sqrt(19) we dont have any repetition?

In editorial for Div2 D1,

Find the sum over all $$$z < sqrt(x)$$$ directly
is not correct ig. Let's say $$$x = 5$$$ & $$$z = 2$$$, then $$$z < sqrt(x)$$$ but $$$5 / 2 = 2$$$ which is less than $$$sqrt(5)$$$ and hence will be covered in loop for $$$c$$$ (refer the editorial).

so loop for $$$z$$$ should be $$$(x / z) > sqrt(x)$$$ or $$$z < floor(sqrt(x))$$$

correct me if I am wrong.

In problem 1558A — Charmed by the Game,In the 0<=x<=p and 0<=y<=q.I submitted the same solution but with relaxed constraints i.e 0<=x<=a and 0<=y<=b 126977218.I don't understand why this solution is also giving AC.We can clearly see the constraints we are imposing on x and y in the case of my solution isn't same.Your help is appreciated.

Why is there only a problem A code?

Video Editorial for Div 2 Problem E / Div 1 Problem C

Sorry for asking this, but can anyone please explain Div2-D2 in more detail? I looked at the others' solutions, but found it slightly hard to find the intuition behind their approach.

Can someone explain me how to do this part in the solution of 1558B?

We can achieve that by preparing a sieve of Eratosthenes, factorizing x and generating all its divisors.

When will the editorial for Div1F be available? Meanwhile, here is a sketch of my solution.

When can tourist update the Tutorial for Problem F?

Is there a more clever (sub $$$N^2$$$) solution for the first problem?

"For each i>1 that is a divisor of x+1, S(x+1) contains an occurrence of i that replaces an occurrence of i−1."

Could someone explain why this is true? (it is from the editorial of 1561D2)

In problem B: Up the Strip,

By definition of the floor function, c≤xz<c+1 . Solving this inequality, we get z∈[⌊xc+1⌋+1;⌊xc⌋]

Can anyone explain exactly how to deduce the range?