Can someone suggest some basic dp problems like E (same or little higher difficulty) please.

E: A different dynamic programming approach, with runtime O(n*h).

Let dp(i,j) be the maximum number of good sleeping times if Vova slept the i to n times with the starting time j. Then, the value dp(1,0) will be the answer. Initially, all dp(i,j) = 0.

Transitions (to be done from i = n to i = 1, with j being all possible values of time (0-h)):

Let t1 = (j + a_i) % h and t2 = (j + a_i - 1) % h

Then, dp(i,j) = max(good(t1) + dp(i+1, t1), good(t2) + dp(i+1, t2))

Simpler way to solve C is to calculate the longest contiguous sequence of L's and then output it plus one.

Alternate solution to task E:

Considering all times of the day modulo h, let dp[i][j] be the maximum number of good sleeping times assuming that Vova has slept the first i times and that the current time of day is j.

Also, let's maintain boolean array pos[i][j] such that pos[i][j] is true IFF it is possible to end up at time j after sleeping i times.

Now, transitions can be calculated by setting dp[i+1][(j+ai)%h] to max(dp[i+1][(j+ai)%h, dp[i][j] + ((j+ai)%h >= l && (j+ai)%h <= r ? 1 ; 0) and applying a similar transition for ai-1.

Now, the answer is just the max dp[i][j] such that i = n.

I noticed a comment denoting a similar solution although my submission was in-contest unlike the other comment.

Can anyone suggest where can we study and practice rerooting question like F. Thanks in advance : )

What was the case that wasn’t included for B? I got hacked and I just wanted to know what the case was.

@vovuh I tried to solve F using two DFS but kept failing test case 3 and I couldn't figure out why it fails on this test case. Can you help me point out my mistake? My submission is 73111564 and I've added comments to make it easy to read.

A can also be done by checking if difference of adjacent elements mod 2 equals 0 or not

Can somebody explain why the above solution for D works? Once we sort all Ci there is no track of their original indexes anymore.. so how is it correct?

When will the ratings get updated... Generally how much time it takes after the contest ends .?

Question D can be solved in O(n) after sorting also using two pointers, which seems a bit efficient.

Link to my solution

Can somebody explain palindrome problem? How does it check the palindrome by removing characters in between?

The solution given by vovuh for E is giving WA on tc 2. Any suggestions on what could be wrong in it?

this contest be like:

Can anyone explain O(N) solution for problem B ??!

Perhaps I am very poor at parity-trick questions, but problem A is very non-intuitive to me, and I was very shocked to see the number of submissions, problems B,C,D were much more straightforward for me.

I still don't think I understand problem A fully.

The answer is "YES" only if all $$$a_i$$$ have the same parity (i.e. all $$$a_i$$$ are odd or all $$$a_i$$$ are even). That's because placing the block doesn't change the parity of the element and the −1 operation changes the parity of all elements in the array.

OK, but this can prove that answer is "NO" when parity of any two numbers is different. But how do I prove that it has to be "YES" when all numbers have same parity?

It's somehow very non-intuitive to me :(

The solution provided for E is not running. I think the issue is that we are running inner loop from 0 to n which includes the case of dp(i,j) where j>i which is invalid. Please correct if I am wrong.

I have an interesting approach to question D,Time complexity: O(n).

You can define c[i] = a[i] — b[i],then sort them,finally while(l<r){ if(c[r]+c[l] > 0){ ans+=r-l; r--; } else { l++; } I think many people will use it to pass;

Where can I practice tree dp problems like https://codeforces.net/contest/1324/problem/F. Thnaks!

I never saw that kind of lengthy system testing. Did it happen like this before?

After 100% it went to 91% .WTH

My F question uses two DFS, the complexity should be no problem, why is it TLE?73153261

I tried the same approach with question D as given in tutorial, still i am getting a wrong ans. Can someone please spot where i might have gone wrong? It goes wrong in test case 12. Thanks in advance.

/* arr[i]= a[i]-b[i]; ->as in the tutorial

only that arr is sorted in DESCENDING order

and i have used a 2-pointer technique */

static int findPairs (Long arr[] , int n )

{ 
        int l = 0, r = n-1; 

        int result = 0; 

        while (l < r) 
        {                              
            if (arr[l] + arr[r] > 0L) 
            { 
                result += (r - l); 
                l++; 
            } 
            else
                r--; 
        } 
        return result; 
    }

I think problem E can be solved by greedy Did anyone solved it by greedy ? I have tried , but i failed

Can someone help me find the error in my solution of E https://codeforces.net/contest/1324/submission/73208155 It gives wrong answer verdict on test 40

Someone please explain me the rerooting technique used in problem F. I am unable to understand it's editorial. Please help.

someone plz drope solution for A by using eazy c++

Why is this code of 1324D — Pair of Topics getting TLE?

Idea of code in short :- BIT / Fenwick tree is implemented using unordered_map (C++) to query smaller values, of type (b[ j ] — a[ j ]), than (a[ i ] — b[ i ]) for all j < i.

Any suggestions to optimize this code using the same idea?

where does my code goes wrong for PROBLEM E link of solution:-

solution here...

.thank in advance:)

1 1 2 2 3 3 4 4 5 5 14 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 6 15 15

the checker is saying this is a palindrome. can anyone explain how? this is test 5,1st problem

Is there any other DP solving for E problem?(thanks in advance)

Can anyone explains why my solution for the Problem-F is giving TLE. According to me its complexiety should be O(2*(n+v)) in worst case?

vector mv[200005];

int a[200005];

int dfs(int x,int p)

{

int newcost=0;

for(int i=0;i<mv[x].size();i++)

if(mv[x][i].first!=p)

if(mv[x][i].second!=-2)

{

    if(mv[x][i].second>0)

    newcost+=mv[x][i].second;

}

else

{

    mv[x][i].second=dfs(mv[x][i].first,x);

    if(mv[x][i].second>0)

    newcost+=mv[x][i].second;

}

if(a[x])

newcost++;

else

newcost--;

return newcost;

}

void solve()

{

int n;

cin>>n;

int flag=0;
for(int i=1;i<=n;i++)
{
    cin>>a[i];
    if(a[i]==1)
    flag=1;
}

for(int i=0;i<n-1;i++)
{
    int u,v;
    cin>>u>>v;
    mv[u].push_back(mp(v,-2));
    mv[v].pb(mp(u,-2));


}

if(flag==0)
{
    for(int i=0;i<n;i++)
    cout<<"-1 ";
    return;
}

int i=1;
while(i<=n)
{
    if(mv[i].size()==1)
    break;
    i++;
}
mv[i][0].second=dfs(mv[i][0].first,i);
for(int i=1;i<=n;i++)
{
    int newcost=0;
    for(int j=0;j<mv[i].size();j++)
    {
        if(mv[i][j].second==-2)
        {
            mv[i][j].second=dfs(mv[i][j].first,i);

        }
        if(mv[i][j].second>0)
        newcost+=mv[i][j].second;

    }
    if(a[i])
    newcost++;
    else
    newcost--;
    cout<<newcost<<" ";
}

}

This gives TLE : * Used Arrays A,B,C and 2 loops to input A and B and form C * Sorted C * This finally used lowerbound thing https://pastebin.com/icGaeuH8

This doesn't give TLE : * Used vectors A,B,C and 3 loops to input these * Sorted *Lower bount thing https://pastebin.com/9fajyGEi

Can anyone help me out ?

Tutorial Question E :

loop 1: i=0;i<n;i++ loop 2: j=0;**j<=n**;j++

-> i is number of sleeps -> j is number of sleeps he goes one hour earlier

So j <= i for all j Thus, j<=i rather than j<=n.

can anybody explain to me that in problem d -c[i]+1 logic? I didn't get it

For problem D, I still can't understand why we can skip it when c[i]<=0? Can someone help me?

Question (B) says that we can solve it by $$$O(n^2)$$$ or by $$$O(n)$$$. I cannot understand the writer's explanation of how we will do it in $$$O(n)$$$. Can anyone please provide code for the same. Thank you.

In problem D, doesn't sorting the c[] array mean losing information about i < j?

iam not able to understand F problem please help

Also, what does this even mean? The subtree of the tree is the connected subgraph of the given tree.

I feel the english is bad and it should be: A subtree of the tree is a connected subgraph of the given tree.

can somebody explain why in problem F the dp[v] = a[v] + max(0,dp[to]) as in subtree all nodes are included so it should be dp[v] = a[v] + dp[to] why we are taking max over 0 . can somebody explain 1st testcase how for node 1 ans is 2.

In E can anyone please point the mistake in dp equation :

• if(j>i) dp[i][j]=0;
• if(j==0) dp[i][j]=dp[i-1][j]+is((sum[i]-j)%h,l,r);
• else dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+is((sum[i]-j)%h,l,r);
• Logic is that one can sleep j times in first i sleeps only if he either sleeps early j times in first i-1 sleeps and not sleeps earlier in ith sleep or if he sleeps early j-1 times in first i-1 sleeps and sleeps early this time.
• where dp[i][j] : maximum number of good sleeping times in first i sleeps, in which j were slept earlier
• sum[i] : sum of sleeping times till first i sleeps
• is(s,l,r) : returns true if s belongs in range [l,r]
• And final answer is maximum in array dp[n][1:n]
• If the logic is correct kindly help me debug my submission 78897404

Sorry to bother you vovuh, but it seems like problem B is broken. Validator is crashing and solutions are not being evaluated. "Denial of Judgment" is being shown on evaluator

Can anyone tell me why this submission is going wrong on TC 12 for problem D? Submission Link. Its very odd, I see that the Editorial solution isn't too far off from my method (It uses binsearch while I use a ptr method).

Can anyone explain me why he took max(0,dp[child]) everywhere?

Why does this solution for Problem F get timed out ..The Time complexity is O(n).. I guess its just traversing the tree 3 times... (https://codeforces.net/contest/1324/submission/86646387)

If someone comes across this, can you please tell why is this solution failing at case 50.

In problem B, it says an array A is a palindrome if A[i] = A[n — i — 1] for all values i from 1 — n. However it should be A[i] = A[n — i + 1].

The solution for the 1324C — Frog Jumps is the longest L continuous string plus 1, its not that complicate

include<bits/stdc++.h>

define lli long long int

define ll long long

using namespace std;

void solve(){ lli n; cin >> n; vector a(n), b(n); for (lli i = 0; i < n; i++) { cin >> a[i]; } for (lli i = 0; i < n; i++) { cin >> b[i]; }

lli left = 0;
lli right = n-1;
lli res = 0;
lli currentSumA=0;
lli currentSumB=0;

while (left < right) {
    currentSumA = a[left] + a[right];
    currentSumB = b[left] + b[right];
    if (currentSumA > currentSumB) {
        res++;
    }
    if (right == left + 1) {
        left++;
        right = n-1;
    } else {
        right--;
    }
}
cout << res;

}

int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); solve(); return 0; }

Why is this solution giving TLE at test case 12 although the time complexity is O(n)? почему это решение дает результат, несмотря на то, что оно большое o(n)?