Vovuh's blog

By Vovuh, history, 2 months ago, In English,

All ideas belong to MikeMirzayanov

1203A - Circle of Students

Tutorial
Solution

1203B - Equal Rectangles

Tutorial
Solution

1203C - Common Divisors

Tutorial
Solution

1203D1 - Remove the Substring (easy version)

Tutorial
Solution

1203D2 - Remove the Substring (hard version)

Tutorial
Solution

1203E - Boxers

Tutorial
Solution

1203F1 - Complete the Projects (easy version)

Tutorial
Solution

1203F2 - Complete the Projects (hard version)

Tutorial
Solution
 
 
 
 
  • Vote: I like it
  • +57
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it +27 Vote: I do not like it

Thanks for the great editorial ! The tutorial for the problem F2 seems to be unavailable for me. I get the following error "Unable to parse markup [type=CF_MATHJAX]".

»
2 months ago, # |
  Vote: I like it -13 Vote: I do not like it

Thanks for fast editorial

»
2 months ago, # |
  Vote: I like it +12 Vote: I do not like it

Can someone elaborate how to handle case when b_i is negative in problem F. Why are we setting a_i = max(a_i,-b_i). Why sorting in the order of a_i+b_i works?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    a_i = max(a_i, -b_i) — u delete variants, when yours current rating plus b_i < 0. For example: r = 10, a_0 = 9, b_0 = -20. U can take this project, but yours rating will be negative. And I don’t know, why the sort a_i + b_i works.

  • »
    »
    2 months ago, # ^ |
    Rev. 3   Vote: I like it +6 Vote: I do not like it

    First, let me tell you why we are setting ai = max(ai, -bi):let's talk both the situations: ai >= -bi and ai < -bi , if ai >= -bi, that means ai doesn't change, when ai < -bi, the problem let us ensure r > 0, when we do this project i, r will be r + bi(bi if negative), so it's obviously why we let ai be max(ai, -bi), we must ensure r+bi > 0, that means we let ai = -bi(the case 2), we can decrease the judgement.Second, why sorting in the order of ai + bi can work? This problem trouble me for a long time at first, when we let ai be max(ai, -bi), we can ensure ai >= -bi, that means ai + bi is not negative, but it can be zero, if we can't do project i, for j (aj + bj < ai + bi) we must can't do all of this, too.That is because aj is greater than ai or not, if aj >= bi , we can't do project j, if aj is smaller than ai, and aj + bj < ai + bi, we can't do project i that means r < ai, when we do the left thing, r will be smaller, that means we can't do project i, either. So this can work.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I think that you should think about this array like “how much rating I need, to make i-th order”.

  • »
    »
    2 months ago, # ^ |
    Rev. 10   Vote: I like it +54 Vote: I do not like it

    Let's try to determine the optimal order to complete all the projects.

    Let's first focus on two adjacent projects $$$i$$$,$$$j$$$ in the current arrangement (supposing $$$j=i+1$$$), and see when we should swap them.(Obviously, the swap will not affect other projects.) That's to say, we should see which way will make completing both projects "easier".

    $$$I.$$$ If we can take both of them by taking $$$i$$$ first, that means our initial rating $$$r$$$ satisfies both $$$r \ge a_i$$$ & $$$r + b_i \ge a_j$$$, which is equivalent to $$$r \ge max(a_i , a_j - b_i)$$$.

    $$$II.$$$ If we can to take both of them by taking $$$j$$$ first, that means our initial rating $$$r$$$ satisfies both $$$r \ge a_j$$$ & $$$r + b_j \ge a_i$$$, which is equivalent to $$$r \ge max(a_j , a_i - b_j)$$$.

    We wonder which constraint is weaker. We already have $$$a_j - b_i > a_j , a_i - b_j > a_i$$$, so we just need to compare $$$I.$$$ $$$a_j - b_i$$$ and $$$II.$$$ $$$a_i - b_j$$$. The smaller, the weaker. Note that $$$I. < II.$$$ <=> $$$a_j - b_i < a_i - b_j$$$ <=> $$$a_i + b_i > a_j + b_j$$$. So, for every pair of adjacent projects, we should determine whether to swap them or not by the value $$$a_i + b_i$$$. In other words, we have the sequence sorted in the order of $$$a_i + b_i$$$.

    (I hope thinking this way can inspire and help you.)

    (Thank Bekh for better formatting! I'm new to writing comments, but I'll keep trying.)

    (Looking forward to others' better, shorter, clearer answers!)

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it +10 Vote: I do not like it

    Why sorting in the order of $$$a_i+b_i$$$ works?

    Assume there are two projects:$$$X$$$,$$$Y$$$, with $$$a_x+b_x>a_y+b_y$$$, and our remaining rating is $$$r$$$. If we can't complete $$$Y$$$ after finishing $$$X$$$, that means $$$r+b_x<a_y$$$. Using $$$a_x+b_x>a_y+b_y$$$ and $$$r+b_x<a_y$$$ we can conclude that $$$r+b_y<a_x$$$. This means we can't change the order so as to finish both the projects.

»
2 months ago, # |
Rev. 14   Vote: I like it +34 Vote: I do not like it

For problem F2,I have a solution in complexity: $$$O(n^2)$$$ .

My solution is similar to the writer's.The only difference is that I let $$$dp[i][j]$$$ be after you choose j in the first i tasks , the maximum rating you have.Then we can simply solve this problem using dynamic programming and the complexity is $$$O(n^2)$$$ .
Here is my code.

Sorry for my poor English.

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I also thought of that optimization; code to compare

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you please elaborate? From your definition of dp state, if you initialise dp[0][0] as rating obtained from the positive part, the dp won't be updated as maximum rating possible is the case where you do not take any negative rating change elements.

    • »
      »
      »
      2 months ago, # ^ |
      Rev. 5   Vote: I like it +9 Vote: I do not like it

      It can be updated for sure.

      We can do these transitions :
      $$$dp[i][j]=dp[i-1][j]$$$
      and if $$$j>=1$$$ && $$$dp[i-1][j-1]>=a_i$$$ && $$$dp[i-1][j-1]+b_i>=0$$$ then $$$dp[i][j]=max(dp[i][j],dp[i-1][j-1]+b_i)$$$
      At last,we just need to find the maximum number $$$i$$$ that satisfy $$$dp[n][i]>=0$$$

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thanks for the elaboration. I understand it now. Dp[i][j] is the max rating you can have considering first i tasks and must taking j of them. Once you force to take j tasks the updates become clear.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please help me to understand the problem E? I dont understand the problem for a while. It would be really helpfull. Thanks in advance. :) sorry for my poor english.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    In simple words we have to maximize number of distinct elements in an array either by keeping the element as it is or increasing it by 1 or decreasing it by 1.

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can you please check my submission 58732857 for problem C. It is the same as editorial but it timed out. Is using python such a big problem ?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can see many participants use Python with AC

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Your code looks fine..I guess it might be due to python not sure

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Hello. I got AC with ur code when use Python 3. https://codeforces.com/contest/1203/submission/58817204

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Try using PyPy3, which is an alternative implementation of Python3. It generally runs much faster.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I actually submitted on PyPy3 and it still errored out but it is getting accepted in Python 3. This doesn't seem right.

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        There are some changes in the "fractions" module implementation of PyPy3. It's slower. Try the same solution, but import gcd from "math" module rather than "fractions".

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        fractions.gcd() is deprecated since version 3.5. Use math.gcd()

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

why the problem F2 Tutorial is

Unable to parse markup [type=CF_MATHJAX]

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I use a different cmp function for sort in problem f1: look at my cmp2 in the solution https://codeforces.com/contest/1203/submission/58799244

»
2 months ago, # |
Rev. 2   Vote: I like it +4 Vote: I do not like it

why do we sort by a + b in decreasing order for negative value in F1

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me with problem D1 code. Where am i going wrong logically? It's giving me WA on test case 5.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    We are in the same boat friend :( Can someone plzz elaborate what to do for passing testcase 5.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Try out this example test: s="caab" t="ab".
    Your code matches first "a" (c a a b) and your answer is 1 (either remove "c" or remove "a").
    The right answer should be 2 because you could remove "ca" subsegment (c a a b).

    I hope this will help.

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    Your code only takes into consideration the case of matching s2 with s1 as early as possible. You also have to this from the back side of the string s2. than you will have to consider all the possible breaking point of the string s2(break s2 into two parts) find the max difference(no. of characters between them).Here is my code 58800190. I hope this will clear your doubt.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Another interesting example is "aabb" and "ab".
    Your code matches as ( a a b b ) and returns 1.
    It is possible to match as ( a a b b ) and the answer is 2.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hi, my code does give the right output for both of your examples, still I am getting WA on test 5.

      Code

      • »
        »
        »
        »
        2 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        Hello, I tested your code. It does actually fail on "aabb ab" test case (your answer is 1, expected is 2).

        # printf '%s\n' caab ab | python3 submission-58760040.py
        2
        # printf '%s\n' aabb ab | python3 submission-58760040.py
        1
        # sha1sum --binary -- *.py
        dd3a55e8764ad494ff75e96ba7c9b25927e518f2 *submission-58760040.py
        ```
        
        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thanks for the help, yes it does not give the right answer.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    #include <bits/stdc++.h>
    using namespace std;
    void computeLPSArray(string pat, int M, int* lps);
    vector<int> KMPSearch(string pat, string txt) 
    { 
        int M = pat.length(); 
        int N = txt.length(); 
        int lps[M]; 
      
        computeLPSArray(pat, M, lps);
        vector<int>v;  
        int i = 0; 
        int j = 0; 
        while (i < N) { 
            if (pat[j] == txt[i]) { 
                j++; 
                i++; 
            } 
      
            if (j == M) { 
                v.push_back(i-j); 
                j = lps[j - 1]; 
            } 
      
            else if (i < N && pat[j] != txt[i]) { 
                if (j != 0) 
                    j = lps[j - 1]; 
                else
                    i = i + 1; 
            } 
        } 
        return v;
    } 
      
    void computeLPSArray(string pat, int M, int* lps) 
    {
        int len = 0; 
      
        lps[0] = 0;
        int i = 1; 
        while (i < M) { 
            if (pat[i] == pat[len]) { 
                len++; 
                lps[i] = len; 
                i++; 
            } 
            else 
            { 
                if (len != 0) { 
                    len = lps[len - 1];
                } 
                else
                { 
                    lps[i] = 0; 
                    i++; 
                } 
            } 
        } 
    }
    int main() {
    	string s,t;
    	cin>>s>>t;
    	int sl=s.length();
    	int tl=t.length();
    	vector<int>v;
    	v=KMPSearch(t,s);
    	int n=v.size();
    	int ans=0;
    	for(int i=0;i<n;i++){
    		int x=v[i];
    		int y=sl-(v[i]+tl);
    		int temp=max(x,y);
    		ans=max(temp,ans);
    	}
    	cout<<ans;
    }
    

    I am getting wrong answer on test case 5 but I think it should work correctly. I have used KMP for pattern searching. Can anybody help please?

»
2 months ago, # |
Rev. 6   Vote: I like it 0 Vote: I do not like it

Do your tester program check if participant find solution though jury can't find it?58820595
There is just comparator and my solution find order though author's answer is NO.
I could check it by myself but I can't see full test case. Where is my mistake?

P.S. Found mistake. Too late to delete this comment.
P.P.S. 58821318 Maybe not found. At each step I checking if r >= ai and r >= 0 after each step. So I think that in test #11 I found correct order to take all projects.
P.P.P.S. Sorry now I really found mistake.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

i can't prove gcd(...(gcd(gcd(a[1],a[2]),a[3],)...)a[n])=gcd(a[1],a[2],...a[n]) in problem C

  • »
    »
    2 months ago, # ^ |
    Rev. 3   Vote: I like it +6 Vote: I do not like it

    We have $$$a, b, c$$$ let's denote $$$gcd(a, b, c) = g$$$ and $$$gcd(a, b) = z$$$ for convenience
    We want to prove that $$$gcd(gcd(a, b), c) = gcd(a, b, c)$$$
    After substituting some terms you get $$$gcd(z, c) = g$$$

    $$$x|y$$$ reads x divides y and means $$$y\%x = 0$$$ or in english $$$x$$$ is a divisor of $$$y$$$

    $$$g|z$$$ and $$$z|a$$$ then $$$g|a$$$
    Same way $$$g|z$$$ and $$$z|b$$$ then $$$g|b$$$
    and $$$g|c$$$ is true anyway so $$$g|a$$$ and $$$g|b$$$ and $$$g|c$$$ are true

    That's for the divisibility. How do you know that it's the greatest?
    Assume $$$gcd(a, b, c) = g$$$ and $$$g > z$$$. Since $$$g|a$$$ and $$$g|b$$$. $$$gcd(a, b)$$$ would've given $$$g$$$ not $$$z$$$ which is the greater divisor.
    In other words $$$gcd(a, b, c)$$$ is either gonna be $$$gcd(a, b)$$$ or one of its divisors.

    and you can keep doing the same to generalize to more then three numbers... prove $$$gcd(a, b, c, d) = gcd(gcd(a, b), c, d) = gcd(z, c, d) = gcd(gcd(z, c), d) ...$$$ and so on.

    If something is not clear, please ask.
    There are more formal proofs out there on the internet too.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it
  • »
    »
    2 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    How would one go about solving the task u mentioned? I mean the constraints are high, and creating dp array for knapsack would go out of memory.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Two ideas:

      • In the code in the editorial the first dimension of dp is neg.size() + 1. This simplifies the code, but actually it only uses dp[i] to calculate dp[i+1], so one only ever needs to store two dp rows at a time.

      • The rows of the dp array will have many repeated values, one might be able to reduce storage by just storing the start and end indexes of each group of repeated values.

      Note that I have not tried writing code using either of these ideas.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell me why problem B,s case 2 output is YES and why case -3 output is NO. Thanks in advance. :)

  • »
    »
    2 months ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    T.C — 2 : -> 10 5 2 10 1 1 2 5

    ->R1 — sides a1 = 10,b1 = 1 and there is extra 10,1 also possible for opposite sides. ->R2 — sides a2 = 5, b2 = 2 and similar here

    as a1.b1 == a2.b2 .Hence Yes.

    T.C — 3:

    -> 10 5 1 10 5 1 1 1

    -> R1 — sides a1 = 10,b1 = 1 and there is extra 10,1 also possible for opposite sides. ->R2 — sides a2 = 5, b2 = 1 and similar here

    as a1.b1 != a2.b2 .Hence No.

»
2 months ago, # |
  Vote: I like it +14 Vote: I do not like it

I have another solution for problem F1(cannot contribute to problem F2, but has a more obvious correctness). First, deal with the projects with positive b values greedily.

Then, calculate the rating after all projects are completed. If it's negative, terminate the program. Otherwise, consider to process the projects in a reversed order, beginning with the calculated "final" rating R. Each time we choose a project i such that R — b_i >= a_i, and update R by R — b_i. So the rating R will be increasing during the reversed process. Then it's easy to determine if it's possible to complete all the tasks.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

orz xk

»
2 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Hi, I tried solving the question D1, but I was getting WA on test 5. Editorial also suggest the use of brute force. I am not able to figure out if I have missed some boundary condition.

In short, what am I doing: I am calculating all possible indexes for a substring in the main string. After getting all possible indexes, I am just finding the case which removes the most characters from the main string.

The code:

def checker(mainstr, substr, index):
    pos=[]
    for i in substr:
        temp = mainstr.find(i,index)
        if(temp == -1):
            return []
        else:
            pos.append(temp)
            index = temp+1
    return [pos[0], pos[-1]]

def logicmain(mainstr, substr):
    size = len(mainstr)-1
    index = 0
    allpos=[]
    while(True):
        first = checker(mainstr, substr, index)
        if(len(first) == 0):
            break
        else:
            allpos.append(first)
            index = first[0]+1
    
    maxdrop=0
    for i in allpos:
        val = max(i[0], size-i[1])
        maxdrop = max(maxdrop, val)
    return maxdrop

def main():
    mainstr= input()
    substr = input()

    ans = logicmain(mainstr, substr)
    print(ans)

if __name__ == "__main__":
    main()
»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Hi, I just want to know what 1ll in the solution of the 1st problem ?

  • »
    »
    2 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    1ll is the number 1 but of type long long not int. It is used to avoid overflow. because the result of the multiplication will be of type int since the array a is an array of int, and therefore it could overflow. Using 1ll makes the result of the multiplication of type long long rather than int.

»
2 months ago, # |
Rev. 2   Vote: I like it +14 Vote: I do not like it

Proof for F1: Take array of the projects with negative $$$b_i$$$ (sorted as given in the tutorial). Let’s complete the projects in this order. If we get stuck at index $$$k$$$ , then:

$$$ r + \sum_{i<k}b_i < a_k $$$

Let’s assume we have a good order of projects in range $$$[0,k]$$$ so that all of them can be completed. Let the project completed last of this set , the one with index $$$p$$$. ($$$p ≠ k$$$ because of the starting inequality).

$$$a_p+b_p ≥a_k+b_k $$$ ,so $$$ a_p+b_p-b_k≥a_k$$$ (because we ordered them so).

Then after we complete everything except the $$$p^{th}:$$$ $$$r+\sum_{i<k}b_i-b_p+b_k ≥a_p$$$.

After reorder: $$$r+\sum_{i<k}b_i ≥a_p+b_p-b_k≥a_k$$$. That is in contradiction to the one in the beginning.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem B i stored the number and occurrence in a map . If the occurrence of any number is odd then this Case would be "NO" else i check from i from 1 to n that a[i]*a[n] and then i++ and n-- . if all the area is equal then it's "YES" . I don't know what is problem it's getting wa. this is my submission 58846470 And sorry for bad english :)

  • »
    »
    2 months ago, # ^ |
    Rev. 3   Vote: I like it +1 Vote: I do not like it

    Try out this test case [1,2,2,2,3,3,3,6]. Your algo would return yes but answer is no ans there are no 2 1s or 2 6s to make a rectangle. Just wnsure that the value occurs in pairs. It should pass. Hope it helps!

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In B: I get a WA on test case 8 here is my code

can someone please elaborates how to do :(

»
2 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

For problem B, I tought that if we sort the array and check that if for every i (1 to (n*2)-1) (i use v[0]*v[n-1] for checking) is equal to v[0]*v[n-1]. Where is my wrong? I couldn't find it. Please help. (I got wrong in 8th test.)

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You should check, whether the number of sticks of the same length is even, and in for(ll i=1;i<(n/2)-1;i++) , you should write i<=(n/2)-1, because you would miss a pair. This way, your solution works.

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    first, you have to check whether it is posible to create a rectangle or not. your algorithm will not work for following test case: 1 1 2 5 10

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell me why my java solution for problem c exceeding time limit?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    int overflow in this loop:

     for(int i=1;i*i<=c;i++) {
    

    eventually i*i will overflow before getting to c

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone give me an intuition for the D2 problem? Why are we creating a prefix and a suffix array? What is the purpose of that?

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

why is sorting by $$$a_i + b_i$$$ is optimal for negative projects in F1?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey. I have a problem with problem C : https://codeforces.com/contest/1203/submission/58879853

https://codeforces.com/contest/1203/submission/58879873

I get time limit. I've seen that i have the same idea with some users and also with the tutorial. i have seen some codes and I don't find the mistake. Cand you help me?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Regarding problem C solution provided in the editorial ;

please consider the expression/condition in the following IF block(the following is as given in the solution);

i.e if (i != g / i) { ++ans; } .

Now when I tried using if ((i*i) != g ) { ++ans; } in my solution ; I received a Wrong Answer Verdict.

Can someone please help me out where am i going wrong.?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    because if ((i*i) != g ) { ++ans; } could be overflow because i is integer, change it to if ((i*1ll*i) != g ) { ++ans; } and you will get AC

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help find out why the hell am i getting runtime error,(problem F1) my submisssion https://codeforces.com/contest/1203/submission/58887999

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please explain editorial of problem D2 ?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Let me try to explain my approach. Consider these examples first:

    • $$$s=efgcbaec$$$
      $$$t=bac$$$
    • $$$s=beaac$$$
      $$$t=bac$$$
    • $$$s=beaafgc$$$
      $$$t=bac$$$
    • I guess it must be clear till now that our longest substring in $$$s$$$ can lie between any $$$2$$$ characters of $$$t$$$. Hence, to maximize this we will store first and last occurrence of each character of $$$t$$$ in $$$s$$$(which can be done easily by iterating $$$s$$$ and $$$t$$$ from left to right and vice-versa).

      Now we will do $$$ans=max(max,last[i]-first[i-1])$$$ for $$$i \in [1,|t|]$$$.

      Link to Code

    • »
      »
      »
      2 months ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      let s = baabca

      t = bac

      for each character of t:

      {"b": {first_occurence: 1, last_occurence: 4},
      
        "a": {first_occurence: 2, last_occurence: 6},
      
        "c": {first_occurence: 5, last_occurence: 5}
       }

      according to you answer is maximum distance between adjacent characters of t:

      max_dist = last_occurence["a"] — first_occurence["b"]

      (i.e. 6 — 1 = 5) which is wrong in this case, correct answer is 2

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        If you take last occurrence of $$$b$$$ as 4 then you won't be able to make $$$t$$$. The occurrences should be valid as well.

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          for s = "abcdefg"

          t = "def"

          I guess your code is handling all the cases, but your comment ??

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In D2 Input

Input

The first line of the input contains one string s consisting of at least 1 and at most $$$2 \times 10^5$$$ lowercase Latin letters.

The first line of the input contains one string t consisting of at least 1 and at most $$$2 \times 10^5$$$ lowercase Latin letters.

maybe the second " First " shouble be "Second" ?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the great editorial!

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you very much!

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone explain the 1203D1 solution clearly.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I am getting TLE on 1203D2. Can someone help me out?
My python code

Also, I cant understand the terminology used in the editorial. What does t[i;|t|] mean?

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Q- D1 and D2 I am getting wrong answer on test case 5 but I think it should work correctly. I have used KMP for pattern searching. Can anybody help please?

#include <bits/stdc++.h>
using namespace std;
void computeLPSArray(string pat, int M, int* lps);
vector<int> KMPSearch(string pat, string txt) 
{ 
    int M = pat.length(); 
    int N = txt.length(); 
    int lps[M]; 
  
    computeLPSArray(pat, M, lps);
    vector<int>v;  
    int i = 0; 
    int j = 0; 
    while (i < N) { 
        if (pat[j] == txt[i]) { 
            j++; 
            i++; 
        } 
  
        if (j == M) { 
            v.push_back(i-j); 
            j = lps[j - 1]; 
        } 
  
        else if (i < N && pat[j] != txt[i]) { 
            if (j != 0) 
                j = lps[j - 1]; 
            else
                i = i + 1; 
        } 
    } 
    return v;
} 
  
void computeLPSArray(string pat, int M, int* lps) 
{
    int len = 0; 
  
    lps[0] = 0;
    int i = 1; 
    while (i < M) { 
        if (pat[i] == pat[len]) { 
            len++; 
            lps[i] = len; 
            i++; 
        } 
        else 
        { 
            if (len != 0) { 
                len = lps[len - 1];
            } 
            else
            { 
                lps[i] = 0; 
                i++; 
            } 
        } 
    } 
}
int main() {
	string s,t;
	cin>>s>>t;
	int sl=s.length();
	int tl=t.length();
	vector<int>v;
	v=KMPSearch(t,s);
	int n=v.size();
	int ans=0;
	for(int i=0;i<n;i++){
		int x=v[i];
		int y=sl-(v[i]+tl);
		int temp=max(x,y);
		ans=max(temp,ans);
	}
	cout<<ans;
}
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hey, your program is not checking for max substring to be dropped between the characters.

    For example for input:
    aabb
    ab

    output should be 2, but your program would give output as 1
    finding ab in string: a a b b

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hey, thanks man you just saved my day.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem E, Can someone pls explain how the answer is 10 for below TC and not 8? Can the weight of a boxer be changed more than once? (it is not mentioned so in the question). 8 9 4 9 6 10 8 2 7 1 — 10 boxers' weights.

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    According to editorial, we have to first sort the array and then for each weight(w) in the array first try to take w-1 (if possible) then w, then w+1. In this particular TC after sorting we get:

    weights given :1 2 4 6 7 8 8 9 10

    weights taken :1 2 3 5 6 7 8 9 10

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    We can convert

    8 9 4 9 6 10 8 2 7 1 to->

    9 10 3 8 5 11 7 2 6 1

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

WHY NOT SIMPLY THIS IN PROBLEM "E" CAN SOMEBODY EXPLAIN EDITORIAL

for(int i=1;i<=150002;i++)
{
    if(a[i-1]>0) a[i-1]--,cn[i]=1;
    else if(a[i]>0) a[i]--,cn[i]=1;
    else if(a[i+1]>0) a[i+1]--,cn[i]=1;
}
//cout<<(count(cn));
int ans=0;
for(auto k:cn) if(k==1) ans++;
cout<<ans;
 
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

the common divisors problem code is still saying that time limit exceeded on test case 3 here is the code below... if any one could find the solutions please tell me why its giving time limit exceeded..... thanks in advance .....

include <bits/stdc++.h>

using namespace std; long long int gcd(long long int a,long long int b) { if(a == b) return a; else if(a>b) return gcd(a-b,b); else if(b>a) return gcd(a,b-a); } int main() { long long int count = 0; long long int n; cin >> n; long long int a[n]; long long int i; for(i = 0;i<n;i++) cin >> a[i]; long long int GCD = a[0]; for(i = 0;i<n;i++) { GCD = gcd(GCD,a[i]); } for(i = 1;i*i<=GCD;i++) { if(GCD % i == 0) { count++; if(GCD/i != i) { count++; } } } cout << count << endl; return 0; }

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Instead of going from gcd(a,b) to gcd(a-b,b), try gcd(a%b,b). It is the same thing, essentially, just faster, because if a is much larger than b, you can skip many a-b-b-b...-b by doing a%b.

    Imagine if a = $$$10^{12}$$$ and b = $$$1$$$, your gcd(a,b) will have to make $$$10^{12}$$$ recursive calls!

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain me solution to D2 that How are the iterators i and pos working? I did the easy version but don't have a clue how to optimize it. The editorial seems harder than the problem itself

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    well what i did is

    1. find all the position of each letter of t string from the left of string s.
    2. now reverse the t string.
    3. find all the position of each letter of t string from the right of string s.
    4. try all the possibilities (like if i construct the t string by taking the first letter from the left and other letter from the right, how much letter that a get rid of?) keep repeating this for all possibilities :D
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can the problem b be solved using xor??pls. help

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain why i need DP for F2 in the negative case. Am i not sorting greedily, so i can pick max elements only if i start from the beginning (in the sorted sequence) and take as much as i can . Why do i need DP here if someone could explain with example . Thanks :)

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I can't understand why my solution is giving wrong answer for D2(testcase 6).

Can someone help me?

int main(){
    string s,t;
    cin>>s>>t;
    int I=0,J=SZ(s)-1;
    REV(i,SZ(t)){
        while(s[J]!=t[i]) J--;
        J--;
    }
    int ans=++J;
    int id=0;
    REP(i,SZ(t)){
        while(s[id]!=t[i]) id++;
        id++;
    }
    uax(ans,SZ(s)-id);
    REP(i,id){
        if(s[i]==t[I]){
            I++;
            J++;
            while(J<SZ(s) && s[J]!=t[I]) J++;
        }
        uax(ans,J-i-1);
    }
    pd(ans);
    return 0;
}
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Someone could explain why problem B actually work with the editorial solution?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the inner if check for in problem C? __ if (g % i == 0) { _ ++ans;_ _ if (i != g / i) {_ _ ++ans;_ _ }_ _ }_

»
6 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

F2 is solvable in O(N log N) as it's equivalent to the deadlines and durations scheduling problem: https://cp-algorithms.com/schedules/schedule-with-completion-duration.html

Code: https://codeforces.com/contest/1203/submission/60304846