Video solution of Div2-D/Div1-B

It seems that we cannot view the solution?

"You are not allowed to view the requested page"

Why does my submission for DIV2 D give memory limit exceeded? 77834554

Also I_love_myself can this be solved using memoisation somehow. Thanks.

Excellent round and excellent editorial. Just edit the submissions link please.

Can anyone explain Div2-C/Div1-A .please

In my opinion, solution of div1F with SQRT decomposition is significantly easier and faster to code. One can check out my code if interested.

In D1E, I think it is incorrect that Nastya will go to meet some bee. If graph is big cycle of squares ("cycled ladder"), than, if all bees will start in one half of cycle and will use your algorithm, than Nastya can escape forever. Read also this comment.

If I understand the proof for E correctly, there are some gaps in the proof:

So suppose Nastya (N) starts at vertex V with neighbours A,B,C. Also suppose that bees 1,2,3 have paths to A,B,C respectively.

Q1: What are the properties of a path? Can they self-intersect? Can they go through V? Must they be shortest paths in some sense?

Assume that N moves to A and that the cycle through V-A also goes through B.

The proof as written does:

• The 1->A' path decreases length by 1, where A' is the vertex on 1->A before A.
• The 3->C' path increases length by 1, because C'=V.(Assuming that the 2nd last vertex on 3->C wasn't V already.) This assumes that A' != V, i.e. the 1->A path doesn't go through V, or else we'd have A'=C'.
• We reroute the 2->V path to 2->B', where B' is the 3rd neighbour of N=A (the one not equal to A' and V). This increases the length by at most 3-1=2. This assumes that the cycle through AV (and VB) doesn't go through A', or else we'd have A'=B'.

I don't think the proof can easily be fixed. Also, the counter example of a cyclic ladder graph (as explained in https://codeforces.com/blog/entry/76348?#comment-609545) still holds I think. The only way to potentially fix that would be to change the paths to be completely disjoint, but that might not be easy.

I tried to find three disjoint paths (if possible) in E and kept getting TLE. Why were limits so tight? Most of accepted solutions exceed half of TL. Did you try to fail some slightly-too-slow solution? $$$n \leq 5000$$$ is quite a lot for $$$O(n^2)$$$ intended solution in a graph problem, especially if one might need like $$$3 \cdot n$$$ BFS's.

Help needed in Div2D/Div1B!
My solution for Div2D/Div1B gives the correct answer for the 5th test case locally but fails when I submit the same code.
77871440
I've already commented the use of each variable in the code. In case of any doubt in the code please ask.

Does anyone know the reason why the code shows such strange behaviour?

Test case on which the code fails
10 10
0101111
0000000
1111011
1011011
1011011
1111011
0010010
1010010
1101111
0000000

This test/hack seems to break the validator for problem Div 1B. I've submitted it as a hack for a few different solutions now and they all give 'Unexpected Verdict':

2 2
1110111
1011101

(nb: this is an anti-greedy case; the input is 02 and k=2, so the correct solution is 08.)

I had a shorter solution for Div2C

It checks for each element a[i], if there is no number smaller than it, for all indices < i.

https://codeforces.com/contest/1341/submission/77830430

A shorter simplified solution for problem 1341C - Nastya and Strange Generator: 77840978

I have a slightly different solution for Div2-E, Div1-C.

First, lets assume we find matrix $$$G$$$ where $$$G_{ij}$$$ is set if we can start from i-th island at green light and stop at j-th at red light. We can fill this matrix in $$$m$$$ dfs over matrix $$$m*g$$$, each dfs is $$$O(mg)$$$ so in total $$$O(gm^2)$$$, and then, find how many cycles (green & red light) we need to reach each island using bfs over matrix $$$G$$$ in $$$O(m*m)$$$ time.

Key insight: if we were able to reach island $$$i$$$ in time $$$t$$$ from starting island $$$s$$$, and then during next dfs from $$$s'$$$ we also were able to reach island $$$i$$$ from $$$s'$$$ it means, that we have some common subset of G for $$$s$$$ and $$$s'$$$ that is reachable from island $$$i$$$ and time $$$t$$$. This means, if we run bfs over G and fill rows of G in order of queue of bfs and disable clearing of visit matrix of dfs, we will find solution in $$$O(mg)$$$. Why? Well, if dfs from $$$i$$$ has reached some island $$$j$$$ from island $$$i$$$ it will set $$$G_{ij}$$$, and thus we push $$$j$$$ in queue. Also, we know that it's shortest path to island $$$j$$$, because it's how bfs works. If during some of next dfs we reach already visited island $$$i$$$ at time $$$t$$$ because we didn't clear visit flags — this means that we already pushed into queue all islands reachable from current one, and all of them already has shortest cycles (green & red light) determined.

Source: 77903961

Another solution for Div2-D/Div1-B 77915468

include

include

include<math.h>

using namespace std;

int main(){ int t; cin>>t; while(t--){ long n,a,b,c,d; cin>>n>>a>>b>>c>>d;

long p=a-b; long q=a+b; long x=c-d; long y=c+d; long flag=0;

for(int i=p;i<=q;i++){
 if(n*i<=y&&n*i>=x){
  cout<<"YES\n";
  flag=1;
  break;
 }
}

if(flag==0) cout<<"NO\n"; } return 0; }

what's wrong in this, it's giving error on 2nd testcase please answer.

For Div2 C, My solution was

For any i, from 0 to n-1,

if a[i+1] — a[i] > 1 then "No"

If there is no such i, answer will be "Yes"

Can anyone prove why this is correct?

I could only think that If after number "I" we put "I+2" or more, means that we had already put "I+1", but the vacant place with max count after putting "I" must be the place next to it (which is vacant as we put "I+2" later) So, we can't have a permutation with a[i+1] — a[i] > 1.

Actually, in Div.1 F the persistent treap is not needed. It's enough for us to query the prefix part if we only maintain the length and hash value. See this code.

Can anyone explain Div 2E/1C nastya and unexpected guest?

what is testcase 7 for div 2 D problem

Could anyone give me a proof of the correction of 0/1BFS? I learned to use that just now but cannot understand :)

The questions were good. But I personally think that some problem statements were too big.

Problem Div1D Nastya and Time Machine is very beautiful!

Мне кажется, доказательство по div1 E неверное. После перестройки пути 2, он может заканчиваться тем же ребром что и путь 1, то есть инвариант не будет выполняться.

Could someone kindly explain the $$$O(n\log^2n)$$$ solution for d1F? I neither understood the definition of "exactly not CBS" nor what the segment tree is storing in the editorial.

Can anyone help me for finding error in my code for problem DIV2Chere. It is giving WA at tc 10. Thanks in advance.

In DIV-2 B i m not getting where my code in not working, please tell me which test case is missing??

O(n) solution for div2-D : solution

Could someone explain why the tutorial's method for div2 D is O(10nd)? For my understanding, it should be O(10nk).

My code for Div 2 B works on my vs code but is showing wrong answer on cf. Can someone please help? Link to code https://codeforces.com/contest/1341/submission/77953400

for 1341C — Nastya and Strange Generator, I have a better approach. https://codeforces.com/contest/1341/submission/77968416

#include<bits/stdc++.h>
#define DEBUG(x) cout << '>' << #x << ':' << x << endl
#define f(i,n) for(int i=0;i<(n);i++)
#define fa(i,a,b) for(int i=(a);i<(b);i++)
#define far(i,a,b) for(int i=(a);i>(b);i--)
#define vect_i vector <int>
#define pb push_back
#define pf push_front
#define ff first
#define ss second
#define T int t; cin>>t; while(t--)
#define ll long long int
#define ull unsigned long long int
#define ld long double
#define FIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define mod 1000000007
using namespace std;
int main()
{
    FIO;
    T{
        int n;
        cin>>n;
        int a[n];
        f(i,n){cin>>a[i];}
        bool possi = true;
        f(i,n-1){
            if(a[i+1]-a[i]>1){
                possi = false;
                break;
            }
        }
        cout<<(possi? "YES\n": "NO\n");
    }
    return 0;
}

Div2 D is such a beautiful problem to sharp your backtracking skills.

I am just learning DFS, BFS... Tried to solve Div2 D by using DFS and got a TLE verdict. Can anyone please tell me why? 77981220

I couldn't understand what problem C meant. the language felt complicated and twisted

A compact version of Div2D: https://codeforces.com/contest/1341/submission/77998256

Can someone tell why solution with Dijkstra doesn't work in Div2E: 77912522?

Hi, can you reopen the original Editorial for Problem E? It is still make sense since there are lots of dicussion about it.

Can someone tell me why my code is giving tle on test case 7... in spite of using dp with memoization.

Code for D div 2 #637

https://codeforces.com/contest/1341/submission/78051371

Would anyone like to talk about how to maintain each prefix in a treap? Thanks!

Help needed in Div2D/Div1B!

My submission is exceeding time limit on test case 22 although it has passed all other tests having n=2000 and k=2000.

I have used recursion with same logic as per tutorial to get O(10*n*k) time complexity. Can anyone please help me understand why is it still exceeding time limit?

This is my submission. I have already commented the use of necessary variables and functions used.

I am only able to understand editorial for 1341F — Nastya and Time Machine partially. Can anyone explain it in more detail..

Hi, can someone tag problems that have a similar DP approach as that of D. Nastya and Scoreboard problem of this contest. I am facing a hard time with such DP problems. So for practice, if anyone has some similar problems, please tag or mention them. I came across one such on CodeChef XORSUB — XOR with Subset. Thanks!

1341A — Nastya and Rice solution failing attest 2 but working at test 1 ,please help

include <stdio.h>

int main() { int t; scanf("%d",&t); for(int i=1;i<=t;i++) { int n=0,a=0,b=0,c=0,d=0,total=0,flag=0; scanf("%d%d%d%d%d",&n,&a,&b,&c,&d); for(int j=a-b;j<=a+b;j++) {

total=n*j;
        if(total<=(c+d) && total>=(c-d))
        {
        flag++;
        break;
        }

    }
    if(flag==1)
        printf("Yes\n");
    else
        printf("No\n");
}
return 0;

}

Can somebody please explain why in Div2 question D answer to test case 5 is is 8993391761 instead of 8999991760 which is greater and also feasible.

Nastya and Time Machine

For case 2: If u has been in states (u, t+1), (u, t+2)......(u,T). How can u be in (u, t+k) in the end? Also how to calculate t'?

[Deleted] because I am stupid.

Editorial of Div2D is bad. Next time just don't write anything.

I thought Problem D is really Tough.

Until I saw its editorial.

And realized the editorial is tougher than the problem itself! :/ xD

EASY EDITORIAL OF D AND PERSONAL THOUGHTS AS WHY THIS EDITORIAL SUCKS!

Approach for Problem D:

1. Create dist[n][10] , where dist[i][j] represents the distance/sticks so that ith string/digit could be converted into jth digit.(0<=j<=9)

2. Create dp[n][k] , where dp[i][j] means if its possible to use all i...n strings by using exactly k sticks. Here,

   dp[i][k]=-1 , means already explored from here, cant go further, ith string and above don't have a solution using exactly k sticks , so Go Back!

   dp[i][k]=0, means Not Yet explored this option. Go Ahead, and mark this =1 if you found answer or -1 if not.

   dp[i][k]=1 Means found ans. Keep returning back, You just need the maximum digit(0-9) from all strings, so no need to check further!

3 Now here we use Dp in Recursion, To avoid Repetition. Ex. Firstly For the 0th string we check if we can use the digit d=9 and use up all k sticks. But How we did That ? By passing the next in recursion i.e. Pass along (i+1,k-dist[0][9]) which means that now we are 1st string, and we have k-dist[0][9] units remaining. Again we start checking for d=9...1 for our 1st string.

And so the recursion keeps going...

Now , Observe that without dp we would be re-calculating these values, that weather it is possible or not to form ith string (and ahead) using exactly (whatever k value was at that point).

If at any point the Recursion gave you -1, mark it , dp[i][whatever k value was at that point)]=-1,means that its impossible to go further from here. So that if you ever happen to reach here again, Simply Say "NO" because you already have visited here once.

Also , when we find the answer (i.e. we reached nth string index and k==0) , we start adding that digit(0-9) in our answer, and return 1.

Then simply reverse the String and Print!

My Simple Yet Not So Simple Code

I tried Dijkstra on DIV2E/DIV1C and get TLE on test 76