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]".

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?

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.

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.

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 ?

why the problem F2 Tutorial is

Unable to parse markup [type=CF_MATHJAX]

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

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

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

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.

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

Task F, isn`t unique: https://acmp.ru/index.asp?main=task&id_task=572

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

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.

orz xk

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()

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

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:

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.

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 :)

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

can someone please elaborates how to do :(

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.)

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

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?

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

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.?

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

Can anyone please explain editorial of problem D2 ?

Thanks for the great editorial!

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; }

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

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;
}

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

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.net/contest/1203/submission/60304846

Может кто нибудь решить F2 методом "Отжиг", если да, оставьте код

In problem E in test case 3:

Oh no，I applied preSum for question D2 and ignore the order of letters

my code:

import java.util.*;
import java.io.*;
import java.math.*;
import java.text.*;
public class Main{
    public static void main(String args[]) throws IOException {
        Read sc = new Read();
        String s = sc.next();
        String t = sc.next();
        List<Integer> list1=new ArrayList<>();
        List<Integer> list2=new ArrayList<>();
        for(int i=0,j=0;i<t.length();i++){
            while(s.charAt(j)!=t.charAt(i)){
                j++;
            }
            list1.add(j);
            j++;
        }
        for(int i=t.length()-1,j=s.length()-1;i>=0;i--){
            while(s.charAt(j)!=t.charAt(i)){
                j--;
            }
            list2.add(j);
            j--;
        }
        Collections.reverse(list2);
        int ans=Math.max(list2.get(0),s.length()-list1.get(t.length()-1)-1);
        //System.out.print(ans);
        for(int i=1;i<t.length();i++){
            ans=Math.max(ans,list2.get(i)-list1.get(i-1)-1);
        }
        sc.print(ans);
        sc.bw.flush();
    }
}
class Read{
    BufferedReader bf;
    StringTokenizer st;
    BufferedWriter bw;
    public Read(){
        bf=new BufferedReader(new InputStreamReader(System.in));
        st=new StringTokenizer("");
        bw=new BufferedWriter(new OutputStreamWriter(System.out));
    }
    public String nextLine() throws IOException{
        return bf.readLine();
    }
    public String next() throws IOException{
        while(!st.hasMoreTokens()){
            st=new StringTokenizer(bf.readLine());
        }
        return st.nextToken();
    }
    public char nextChar() throws IOException{
        return next().charAt(0);
    }
    public int nextInt() throws IOException{
        return Integer.parseInt(next());
    }
    public long nextLong() throws IOException{
        return Long.parseLong(next());
    }
    public double nextDouble() throws IOException{
        return Double.parseDouble(next());
    }
    public float nextFloat() throws IOException{
        return Float.parseFloat(next());
    }
    public byte nextByte() throws IOException{
        return Byte.parseByte(next());
    }
    public short nextShort() throws IOException{
        return Short.parseShort(next());
    }
    public BigInteger nextBigInteger() throws IOException{
        return new BigInteger(next());
    }
    public void println(int a) throws IOException{
        bw.write(String.valueOf(a));
        bw.newLine();
        return;
    }
    public void print(int a) throws IOException{
        bw.write(String.valueOf(a));
        return;
    }
    public void println(String a) throws IOException{
        bw.write(a);
        bw.newLine();
        return;
    }
    public void print(String a) throws IOException{
        bw.write(a);
        return;
    }
    public void println(long a) throws IOException{
        bw.write(String.valueOf(a));
        bw.newLine();
        return;
    }
    public void print(long a) throws IOException{
        bw.write(String.valueOf(a));
        return;
    }
    public void println(double a) throws IOException{
        bw.write(String.valueOf(a));
        bw.newLine();
        return;
    }
    public void print(double a) throws IOException{
        bw.write(String.valueOf(a));
        return;
    }
    public void print(BigInteger a) throws IOException{
        bw.write(a.toString());
        return;
    }
    public void print(char a) throws IOException{
        bw.write(String.valueOf(a));
        return;
    }
    public void println(char a) throws IOException{
        bw.write(String.valueOf(a));
        bw.newLine();
        return;
    }
}

For D2, you may want to consider this greedy trick I have seen a few times: left and right.

For each index i in t, get the leftmost index j of S where t[:i] is a subsequence of S[:j].

For each index i in t, get the rightmost index j of S where t[i:] is a subsequence of S[j:].

The answer can be:

1) the n-1-(leftmost index of S where t is a subsequence of S[:ans])

2) the rightmost index of S where t is a subsequence of S[ans:]

3) for some index of i from 0 to t.size()-2, take the rightmost index r of S where t[i+1:] is a subsequence of S[r:] and the leftmost index l of S where t[:i] is a subsequence of S[:l] the candidate can be r-l-1;

#include<bits/stdc++.h>
using namespace std;

int main() {
    string a, b; cin >> a >> b;
    int n = a.size(), m = b.size();
    vector<int> lb(m, 0), rb(m, 0);
    int tmpb = m-1;
    for(int i = n-1; i>=0; i--) {
        if(b[tmpb]==a[i]) {
            rb[tmpb--] = i;
        }
        if(tmpb<0) break;
    }
    tmpb = 0;
    for(int i = 0; i<n; i++) {
        if(b[tmpb] == a[i]) {
            lb[tmpb++] = i;
        }
        if(tmpb==m) break;
    }
    int ans = 0;
    ans = max(ans, n-1-lb[m-1]);
    ans = max(ans, rb[0]);
    for(int i = 0; i<m-1; i++) {
        ans = max(ans, rb[i+1]-lb[i]-1);
    }
    cout << ans << endl;
    return 0;
}

In F2, for the knapsack dp, you can use sliding dp and reduce memory to $$$O(r+n)$$$. Time complexity is still $$$O(rn)$$$ though.