vovuh Can you check the editorial for F2, thanks

Has the problem been fixed yet? It works fine on my device.

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.

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.

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

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

Unable to parse markup [type=CF_MATHJAX]

Unable to parse markup [type=CF_MATHJAX]

$$$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!)

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.

I also thought of that optimization; code to compare

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.

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.

You can see many participants use Python with AC

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

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

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

because we want to do a project with high a and low b first before other project

I've tried to explain main idea behind it there

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

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.

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.

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.

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

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.

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.

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.

Very easy to understand the "obvious" correctness as you stated.

Thanks.

Upd:this solution can contribute to F2 in fact. We focus on the projects with negative b values only.

Assume we have finished processed all the projects we selected with a remaining final rating R0. Then consider to process the projects in a reversed order with R0 as the initial rating. We can process a project i iff R-b_i >= a_i, so we can store these available projects in a priority_queue and one by one greedily choose the project with the smallest -b_i(rating change) to process, thus yielding the minimum initial rating required to finish a certain number of projects with final rating R0. It's easy to maintain the available projects with the rating increasing in O(n), and priority_queue is O(nlogn). The final rating R0 ranges from 0 to the biggest a_i+b_i (a larger R0 doesn't make sense since this is sufficient for us to choose the projects freely at the reversed "beginning"), a O(r) range.

The above process doesn't require the real initial rating r, so with this approach we can also answer queries about multiple initial ratings efficiently.

Overall Complexity(single query): O(nrlogn)

Overall Complexity(multiple query): O(nrlogn + nq) (q:number of queries)

Woah. This is just amazing and doesn't even require a proof because it is just so obvious.

Even mine solution was same using bruteforce and got WA on tc-5. Can't figure out why.

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

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.

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!

At least your condition (n!=1) is problem

Try (it is impossible to create rectangle)

1

1

1 2 3 4

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.

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

int overflow in this loop:

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

eventually i*i will overflow before getting to c

you can imagine that for each letter "c" in the second array, you create the first[c] and the last[c] in the first array in the sense that A[last[c],lA] contains B[c..LB]. Then, you will try to find the largest interval [p,q] such that p>first[c] or q<last[c] for all c in the second array.

try to use "long long " replaces "int "

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

Comparison function must have strict weak ordering. I was doing the same mistake. For more info read here : https://stackoverflow.com/questions/34446443/segmentation-fault-because-of-comparison-function

Got it to pass your code till test case 36. This is your submission with correction. Now you can work on to remove the bug from your implementation.

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

I have written a blog on the solution to this problem. Here's the link

I hope it is of some help :)

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

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

We can convert

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

9 10 3 8 5 11 7 2 6 1

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!

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

Lets see the array in sorted order : 1 2 4 6 7 8 8 9 9 10 10

Um operations selection like this would conclude the answer to be 10 :

1 2 4 5(6 — 1) 6(7 — 1) 7(8 — 1) 8 9 10 11(10 + 1)

There maybe some other permutations for the same but hope this would clear ur query !

Problem E solution with simple explanation: https://www.youtube.com/watch?v=3untA4RsPxs

I think that would cost O(n*n*log(n))....

first you will need to calculate two vectors pref and suff of length n each. pref[i] will denote the length of prefix of string t that is a subsequence of string s[0...i]._ similarly suff[i] will store the length of suffix of string t that is a subsequence of string s[i...n-1] (here n is the length of string s). now perform binary search on the answer low=0, high= n . to check if removing a substring of length x is possible or not iterate over i=0 to i= n-x. and if for any i, pref[i-1] + suff[i+x] >= length of t holds true. then it is possible to remove substring of length x starting from index i. if no such i found then x length substring cannot be removed. here is my submission 129840232 sorry for poor english.