Where are the time complexities?

I usually find understanding a solution easier when the time complexity is indicated with the solution.

Amazing contest, nonetheless.

Lost the entire interest after seeing problem statement of B1 :(

In Div1D, the time complexity is $$$O(nm)$$$, so the limits could have been higher as I think of it.

Was it intentional (so that one would think of it more as a $$$O(n^3)$$$, flow-like problem, for example)? Or possibly a change of mind -- maybe wrote a cubic solution, found the square one after?

Long statements + weak pretests

Devil I think you made undirected graph in solution of div2C :)

lost interest in this round due to B problem statement

Graph solution for problem div2 C (div1 A) is beautiful . Can some tell other approach without using graphs.

dcordb can you please you spoiler to display editorial (blogs), it will be more convenient like previous editorials.

Solution of div1C only gives the answer but doesn't really explain how one might come up with that in the first place, so I'll try.

First observation is having lots of letters in the first string is bad for us, so we want to join letters as much as possible. That is, suppose the solution does operations A->B, followed by A->C. We could have changed all As to Bs in the first operation to do A->B, B->C instead. B->A followed by C->A can also be replaced by B->C, C->A.

From this, we might intuit that the solution consists of one very long chain in which we have a "snowball" collecting all original letters into the same letter.

If the graph has no cycles, then such a snowball can simply follow the topological sort of the DAG (this is div1A). If there are cycles, then some vertices will be visited more than once. If you know that a vertex is going to be visited more than once anyway, you might as well put it as the first and last vertices in the order, since this guarantees that vertex can reach/is reachable by all others.

What about the vertices you only visit once? Clearly there cannot be any cycles between them, so they are a DAG (and as we know any DAG can be solved with the topological sort). So the solution looks like: visit some set of vertices S, do topological sort on the rest, visit S again. To minimize the number of operations we want the DAG to be the maximum possible.

Question : C2 Koa and the Beach
Can someone explain why the below test case below should have "NO" as a answer:
20 26 32
31 27 14 7 2 23 22 21 19 27 31 12 23 31 0 11 28 20 31 30

I don't like editorial of 1384B2 - Koa and the Beach (Hard Version) So I'll write my own. I think it should be easier.

Let s(p, t) is answer on question "is there way to reach position p at cycle of tide t?". I'll make numbering of tide cycle in following way [k, k-1, k-2..., 1, 0, 1, 2 ... k-1]. It will be much easier to understand later.

So, now obviously, if 0 is island, then s(0, t) is true for any t. Next, suppose some s(p, t) is true, then if we get this existing way to reach p at cycle time t and just standby there, eventually we can either drown or stay infinitely. Obviously, if we drown then it is because tide increased. This means that for all i up to some point x value of s(p, i) is also true, unless you can stand there forever. So either whole segment from i to x is true, or all s(p, t) is true for this p. Position p where you can stand forever lets call safe position similarly with editorial.

Now important part: we can drown only when tide increase, highest allowed tide is easy calculated. And that's why cycle of tide I defined in the way above, with increasing in the end. Because higher allowed tide — longer we can stay. And, this also means that cycle time with "bad" level of tide is in prefix and suffix of cycle. This all means that for any position p there is first (lowest) t for which s(p, t) is true. And, in this notation all possible cycle time for position p gives range from first time to the time when highest possible tide is reached during rise of tide. Thus, to solve the task we only need to find for each position p first t when s(p, t) is true.

Now, consider three cases:

• if you stand on safe position p, to get earliest t in cycle for next position p+1 you should move at fall, so you move to next position at fall of tide and highest allowed tide.
• if you stand on unsafe position p when tide is rising, you just need to move forward as soon as possible, because if now you can't move forward, then on next time you can't also move forward, but if you can right now — it's earliest moment in cycle you can reach next position.
• if you stand on unsafe position p when tide is falling you just need to wait until you can move forward and not drown on next position p+1.

So, for each position we just update earliest t, and total time complexity is O(n). 87931302

Next time please try to make smaller readable problems. Appreciated your efforts.

The largest directed acyclic graph can be computed using dynamic programming in n*2^n.

I remember a nice CF blog on this, could anyone point it out.

DP solution to B1:87940952. dp[i][j]--> Can we be at location i at time j? So, if any of dp[n][j] is true, we can reach the island.

EDIT: Got it!

My Code is Exactly like Editorial's.

Can anyone Please tell me why is gives wrong for this simple case, ALTHOUGH it's giving correct output in my local Compiler.

Tese Case: 1

3

ddd

ddd

My Local Output: 0

Cf Compiler: 1

I found the following trick to solve Div2 B with simple implementation. The idea is like sliding window and updating the initial interval of $$$(-k, k)$$$ that corresponds to decreasing tide $$$(-k, 0)$$$ and increasing tide $$$(0, k)$$$. This way of set up simplified the implementation so much, but unfortunately, I came up with this at the end of the contest. Here's my solution

Kudos to testers and those who arranged the problems in order of difficulty.

Solution videos for people who prefer to have things explained visually are available here.

Can B1 use array to memory state?

How is my idea for Div1A different from the editorial?

In Div2C.

For the testcase 1 4 aacb bcdd

The topological order is acbd But we can't select the each pair of consecutive nodes because c-->b is not possible.

Am i missing something?

Although the quality of problems is quite good, but the score distribute is not reasonable. Div2 B that cost me 1 hour time only values 500+750 score. Div2 C is quite easy, but values 1750. I solved 5 problems but get a lower rank than someone solved 4 problems because of this score distribute. Sad~

In the code of div1 E, the DP transition is

dp[i] = ((dist[i] <= dist.back()) + get(0) + get(dist[i] + 1)) % mod;

I understand get(0) and get(dist[i]+1) are the two cases in the editorial, but what does (dist[i] <= dist.back()) mean ?

I find that if s="0", the solution will RE because it visited nxt[dist[0]+1] (dist[0]+1=2) and the size of nxt is $$$2$$$ !

In Div1E/Div2C, what is the motivation for: "and the answer is $$$2⋅n−|LDAG|−1$$$"?

Why the simple greedy solution isn't mentioned in editorial for Div2C?

If you are keeping python as a submission language then please do some homework and check the comparative time it's gonna take in python or else change codeforces to cppforces.

Case: x%4 == 3 if y%2=1 the first player takes one 1 and the game now is exactly the previous case with the first player as the second player. I think the author means the first player takes first 0 and then the game is exactly the previous case . Previous Case: x%4 == 3 && y%2 == 0 Or Maybe i am too naive to understand the Author's logic :)

Can anyone explain how we can solve Div2C using DSU?

IMO in Div.2 only problem C and maybe D had somewhat of a proper score allotted to it. Rest all should have had a higher score allotted to them. Especially B2.

For String Transformation 1, I am really struggling to understand the answer after the 2nd sentence. I would like to understand this graph solution, could anyone please explain it in more detail?

This is how I solved Div2B

let h be an array where h[i] = l - d[i]

Then divide h into segments [L, R] where

h[L] >= k

h[R] >= k

h[i] < k (L < i < R)

For each segment check if exist 2 indices i and j such that i + h[i] < j - h[j] then there is no solution. Otherwise, a solution exists

for mask in 1..2^n-1
   for u in mask:
      is_dag[mask] |= is_dag[mask & (1 « u)] && ((mask & reach[u]) == 0))

Should it be:

for mask in 1..2^n-1
   for u in mask:
      is_dag[mask] |= is_dag[mask ^ (1 « u)] && ((mask & reach[u]) == 0))

For DIV2C/DIV1 A

For this sample input

1

7 dgdfjjk

lhejkkl

We can transform in just 5 steps,but author's solution is showing 6.

Operations 3-e

2-h

4-j

1,5,6 — k

1,7 — l

am I missing something?

Can someone please explain me the graph solution of problem 3. I am not able to understand it from the editorial.

div 2 C seems to be a standard ques!! if yes then can you plz tell me more about this type of question!

For C1 my approach seems to be different from what the comments are mentioning. (*I also don't seem to have a proper proof for it but it seems to work intuitively and would be nice if someone wants to look into this*)

I took characters of string B and sorted them in the increasing order. (Let's call the smallest value of such a sorted sequence as SML)

My claim is that if we try to change the characters of string A whose character in the corresponding same position in B is same as SML or once such character is found then every occurence of the same character in A will be changed to SML and the number of such distinct characters which were changed to SML will be added to our final answer.

Now first turn is over SML will pick the next smallest element and will redo the above again.

Finally all characters in A will be changed to the ones in B and the answer will be minimum.

I used set of pairs to implement it.

If there are any counters to the above explanation they are most welcome. (Since I am not sure why my approach actually works besides few samples I checked with pen and paper)

https://codeforces.net/contest/1384/submission/88045399

In Div.1F, the time limit seems so tight after some very strong hack testcases were added, and it's so difficult to pass them.

By the way, can anyone tell me how to get max flows quickly.

I have some questions on 1383B - GameGame : why we dont have to consider higher bits when we're processing the first bit that the number of ones is odd? (or : why we can turn these numbers into an array of $$$x$$$ ones and $$$y$$$ zeros? should we consider the influences of higher bits (though their number of ones is even) ?)

i'll appreciate it if you can explain these questions to me :)

In div 1 E editorial, I don't understand this part:

"if the $$$(j+1)$$$-th character in $$$w$$$ is 0, and we have $$$k$$$ zeros after the last 1 in $$$w$$$ find the next block of $$$k+1$$$ zeros in $$$s$$$, (ie first $$$i'>i$$$ such that for each ($$$0\le k'<k$$$) $$$s_{i'-k'}=0$$$)"

Why do we look for a block of $$$k+1$$$ zeros if we only need $$$k$$$ zeros? Also, the part in the parenthesis contradicts this because there $$$0\le k'<k$$$ is an interval with only $$$k$$$ numbers in it. However, the model implementation uses get(dist[i]+1) which is also $$$k+1$$$. So which one is it and why?

In the solution for b1 what does this code correspond to? function<bool(int, int, bool)> go I mean, I understand the meaning but I haven't seen this kind of syntax till now.......

Problem B1 : How the depth increased by time t = (t % 2k) ?? If so then the depth can be increased more than k which is not possible according to the statement. Help please...

include<bits/stdc++.h>

using namespace std;

typedef long long ll ;

set<tuple<ll, ll, bool>> mark ;

bool dfs(ll n, ll pos, ll &tide, bool &down , vector &d , ll k , ll l) {

if(pos > n) return true ;

if(mark.find({pos,tide,down}) != mark.end()){
    return false;
}

mark.insert({pos,tide,down}) ;

tide += down ? -1 : +1 ;

if(tide == 0) down = false ;
if(tide == k ) down = true ;

if(d[pos] + tide <= l && dfs(n , pos, tide , down , d, k , l)) return true ;
if(d[pos+1] + tide <= l && dfs(n , pos+1 , tide , down , d , k , l)) return true ;

return false;

}

int main(){ ll t ; cin>>t ; while(t--){

mark.clear() ;

    ll n  , k , l;

    cin>>n >> k >> l ;

    vector<int> d(n+2 , -k ) ; 

    for(int i=1 ; i<=n ; i++) {
        cin >> d[i] ;
    }

    ll tide = 0;
    bool down = false;

    if( dfs(n,0 , tide, down , d, k, l) ) cout<<"Yes"<<'\n' ;
    else cout<<"No" << '\n' ;   
}

return  0;

}

I am struggling why my code is showing wrong ans

my dp solution for B1 using 2 states — https://codeforces.net/contest/1384/submission/88165283

I want to verify time complexity — I think it should be n * k as for every index k times are possible i.e. earliest you could reach is i + 1 and latest you could reach is i + k

1383E - Strange Operation I think my understanding of DP is very good. But even I had trouble with editorial even thought I solved it in the first place! So, for those who want to learn all that magic few people understand, I'll try to explain it as much as I can.

s = 001010110001
t = 0101001
    0 1010 - what we was able to make

...100001...
      ^- we stand here

I might be too late to the party, but I am presenting my own solution for 1E anyway.

Let's solve the problem where the first and last character are both 1, because the beginning and ending zeros can be counted and multiplied into the final answer trivially.

Between any two consecutive 1's, let's count the number of 0's, and store it in an array a. So we can "compress" our string into $$$\texttt{1 } a_1 \texttt{ 1 } a_2 \texttt{ 1 ... 1 } a_k \texttt{ 1}$$$, where $$$a_i$$$ is the occurrence of 0's between the $$$i^{th}$$$ 1 character and the $$$(i + 1)^{th}$$$ 1 character. The problem can be then transformed into: for each element $$$a_i$$$, replace it with a value from $$$0$$$ to $$$a_i$$$, or remove the element from the array completely. Count the number of possible arrays that can be made this way.

I denote $$$dp_i$$$ to be the number of different arrays that end in the value $$$i$$$, and denote $$$tot$$$ to be the total number of different arrays. Clearly $$$tot$$$ would be our answer, and $$$tot = (\sum{dp_i}) + 1$$$. Let's maintain this $$$dp$$$ and $$$tot$$$.

Iterate over $$$a$$$. When we loop over $$$a_i$$$, clearly only $$$dp_j$$$ where $$$0 \leq j \leq a_i$$$ change, so let's see how they change. We have two cases of what to do with $$$a_i$$$:

1. Remove this element completely. $$$dp_j$$$ does not change.
2. Replace $$$a_i$$$ with $$$j$$$. We can make $$$tot - dp_j$$$ new arrays this way, since we create $$$tot$$$ arrays from appending $$$j$$$ to the previously existing arrays, but $$$dp_j$$$ of them has appeared before.

Therefore, $$$dp_j = dp_j + tot - dp_j = tot$$$. In other words, when we loop over $$$a_i$$$, we assign $$$dp_j = tot$$$ for all $$$0 \leq j \leq a_i$$$, then update our $$$tot$$$. The complexity would still be $$$O(|s|)$$$.

However, I think this solution is much more interesting because this can solve the problem if you are given the string in a compressed manner. When a block of $$$0$$$'s comes, update the $$$dp$$$ like mentioned. When a block of $$$1$$$'s comes, calculate what $$$dp_0$$$ would be after processing all the $$$1$$$'s. We can use a stack to implement this in $$$O(|compress(s)|)$$$.

Div 2 D/Div 1 B was beautiful, thanks

on the problem string transformation 1, I think the test is really week. My solution is o(n^2+nlogn) but still accepted.

What's with all those hacks in div1F?