As a cyan participant, I hope to be green again after this contest)

GL & HF

I hope to be purple.

As a Purple participant, I hope to stay Purple after the contest.

As a gray participant, I hope to be green after this contest)

GL & HF

I might become cyan by morning if not hacked.

As a gray participiant, I hope to be a LGM ever. GL & HF

That's so good.

i guess you wont become green and I wont remain green

bro wdym, you don't even need God to make it to green. I have full faith in you! :D

Good luck, God willing

Non rated participants always get rated if they participate. Which is why you should participate. GL! :D (Remember to bump)

Nice contest, but there's just one small problem with it: who tested? like genuinely who tested? who gave you the testing code? I'll tell you nobody did, nobody tested it. There are zero people who tested among us, look I invited everyone who tested to this party, and took a photo of everyone who tested, yo check out it's a bus full of everyone who tested. You know what man, I'll do you a favor, clearly we can't see who tested, so I'm just gonna do it myself, I'm gonna find out who tested. I sailed in the seven seas to find out who tested, yo I literally found the one piece before I found who tested, I literally climbed to the top of Mount Everest and didn't find who tested. Keep searching boys we gotta find who tested. I just infiltrated the largest satellite dish in the world and I still can't locate who tested, I literally found the cure to cancer before I found who tested, I'm on maximum render distance and I still can't find who tested, I witnessed the collapse of human society resulting from a global nuclear war, I now live in the grave of this broken world ravaged by radiation for years on end before I found who tested, I visited every single planet in no man's sky and still didn't find who tested, doctor strange literally looked through 14 million different timelines and not in one of them than anyone tested, I literally searched through every single backroom's level and didn't find who tested, I literally died and went to heaven and god himself doesn't even know who tested. Leaving the earth's atmosphere to expand the range of our search, yo I literally found extraterrestrial life on Mars before I found who tested, I have achieved intergalactic travel before I found who tested, I just found a dyson sphere before I found who tested, I found the edge of the universe before I found who tested, I literally visited every single planet in the entire universe before I found who tested, I am literally witnessing the death of almost every star around me before I found who tested, the light of the universe is slowly fading I have searched across galaxies leaving no stone unturned, yet I am afraid my time in this universe is finally running out, it's a shame really I've witnessed stars being birthed and those same stars dying, I've seen literally everything there is to see in this beautiful universe, yet this whole time I've been caught up with such a petty task instead of enjoying my time while it lasted. I was distracted from the beauty of it all I don't regret what I've done, though the question that started it all: who tested has finally been answered. I've searched every nook and cranny in this entire universe and can now confidently say better than anybody that truly nobody tested [Music] the contest.

Happiness both ways

https://codeforces.net/blog/entry/21496

keeping it simple --> difficulty level is DIV.2 and Penalty is like DIV.3 :/

Is that Bokita?

observation !!

Read 2nd testdata of testCase 1 in the example. You might get it.

You can squeeze in $$$O(NK^2)$$$

How far did you get/what part of the problem do you want a hint for?

I think there are several stages in solving this problem:

1. Thinking of any solution at all (this one you should probably do by yourself).
2. Realizing how to make it run in $$$\mathcal{O}(N×K^2)$$$.
3. Realizing how to optimize it into $$$\mathcal{O}(N×K^{1.5})$$$.
4. Making the implementation efficient enough to fit in the time/memory limits.

(I failed at step 4.)

:| I didn't read the explanation of test cases question was quite self explanatory!

Oh I am glad, I am not alone.

How to prove that if answer is no then the string must contain such a pattern?

How??

can you please tell what helped you in AFTER READING SECOND TESTCASE DATA in TESTCASE 1 ?, i didn't get it , is this testcase so obvious for BS. how did it helped solving the que

You need to do max(suff_sum[i + 1], ..., suff_sum[n — 1], 0) instead.

It seems to be correct as that's I what I've done. I find the continuous interval with the smallest negative sum, and then remove it.

I'll try to explain my solution in my own words. First, define C[n] as the prefix sum of A[1..n] (formally: C[0] = 0, C[i] = C[i-1] + A[i] for 1 ≤ i ≤ N). The elements of C are the scores that would be obtained if there wasn't a floor in effect.

Code: 211553817

I bootled this so bad . I got accepted after 7 minutes of contest end , the idea is so easy i just messed up the implementation :

idea is that after you choose a number the first occurrence of that number splits the string into two, now the problem reduces to the right half only . so we can greedily choose the number from possibilites (that is between l[i] and r[i]) which gives the shortest possible remaining string. If at any iteration (i) one of possible numbers is not in the remaining string choose it and that gives answer yes. If you finish traversing all i's without then the answer is no.

Start from last in both range strings(l and r) and string s, let say p1 = n-1, and p2 = m-1.

Now, looking from last (i.e from p1 to 0), find the numbers in range l[p2] and r[p2], if at any p1, you find all the numbers in the range, then reduce p2, then again find all the numbers in range l[p2] and r[p2], do this until you will encounter one of the case, if p1 becomes -1, then that means you can make some password which will not be subsequence in string "s" therefore the Answer would be "YES", else p2 would have became -1, that means all the ranges have ended therefore all the possible subsequences are present in string "s", Hence the Answer would be "NO".

How did you solve D with binary search and sparse table? I am curious to know. My technique used a modified version of kadane's algorithm to solve it.

is it dp[i][j][p] = how many possible placements are there if the ith ball is at jth position and we have used p swaps so far

in the end answer is =

for(int j = 0 ; j < n ; j++){
	for(int p = 0;p<n;p++){
		if((k - p) % 2 == 0)ans += dp[n-1][j][p];
	}
}

( I just asked this to confirm if my idea was correct )

I used the fact that if $$$one_i$$$ is the position of i-th one, possible final positions for i-th one are roughly $$$[one_{i-\sqrt k}, one_{i+\sqrt k}]$$$. If you use this then there is only $$$O(n\cdot k^{1.5})$$$ states.

Congratulations for coming up with the $$$O(n^2k)$$$ DP! My solution is simply an optimization of the $$$O(n^2k)$$$ DP and the time complexity is $$$O(nk\sqrt k)$$$.

In one word: throw away all useless states.

In more words:

DP is deciding from the left to the right for each position whether to put a 0 or 1 and count the number of inverse pairs (aka number of swaps used). Let DP[i][j][p] be the number of situations that: we have already decided the first $$$i$$$ positions, among them we have used $$$j$$$ 1s and we have encountered $$$p$$$ swaps. Naive implementation of this DP is $$$O(n^2k)$$$, but a state is useful only if $$$\left|j-S_i\right| <= O(\sqrt k)$$$ (where $$$S_i$$$ is the prefix sum of the original array), otherwise the number of swaps will be too large ($$$>k$$$).

Source: Trust me. I am gray.

Your first case of if is incorrect.

It should be 1+min(abs(xb),abs(xc))+min(abs(yb),abs(yc)).

2D DP with $$$O(100m log(n) + n)$$$ https://codeforces.net/contest/1845/submission/211518255

Managed to make a really messy DP solution in $$$O(nm)$$$

https://codeforces.net/contest/1845/submission/211527425

O(nm) worked for me

It's impressive to be able to solve this problem using dynamic programming. At first, I also thought it could be solved using dynamic programming, but I couldn't figure out how to do it no matter what.

And this problem should deliberately retain the time complexity that can be achieved by using dynamic programming, because if a greedy approach is used, m can be larger.

Yea me too. First I misread the problem, then I overcomplicated it with dp, After that fortunately I just had enough time for D

There is a strong independence between each digit of the final number. You can consider the optimal scenario for each digit and try to solve this problem using a greedy approach.

If you know the problem colorland in Kattis, this problem is similar to that, you build an implicit graph from the start of the string to an "INF" node and see if there is a path of length <=m from left to right. (Note: you can greedily jump as far as possible!) You could maybe see my solution for more clarification.

Sure, to solve it using greedy approach, one might try to think of how to build a string that would not be a subsequence.

To do so let's think of positions of possible values of first digit of resulting password. It definitely should be from l[i] to r[i]. For all such digits let's find their first positions in the string. I claim that it is always beneficial to take digit with maximum value of first appearance. Why? Well, because it destroys more possible subsequences (since we cut off the largest prefix by doing so). See my submission for more details: 211498000

just find the largest decreasing subarray of input and avoid it, then we get the maximum rating

Let's denote prefix sum to position $$$i$$$, by $$$pref[i]$$$. If you think about it a little, it's easy to see that answer must be in $$$pref$$$ (unless there is no positive value in $$$pref$$$). Let's say that our initial answer is 0, and iterate over $$$pref$$$. Assume that before position $$$i$$$ we found some answer $$$x$$$. Now, we have to find some conditions to determine if it will be optimal to change our answer $$$x$$$ to $$$pref[i]$$$. Surely, it won't be optimal, if $$$x > pref[i]$$$. Otherwise, let's denote the prefix sum to position $$$i$$$, if $$$x$$$ was the threshold by $$$pref\_ans$$$. If there is some value $$$min\_val$$$ in $$$pref[i]$$$ on positions $$$[i+1, n)$$$, such that $$$min\_val + (pref\_ans - pref[i]) < pref[i]$$$, then it will surely be optimal to change our answer to $$$pref[i]$$$ (because if $$$x$$$ was our answer, prefix sum here will fall below $$$pref[i]$$$). Otherwise it won't.

You've to be sure about monotonicity of your search space whenever you're going for binary search, which in this case is not monotonic.

C was easy. but the statement(possibly poor) made it a bit complex.

answer is 2.

C is the easiest task after A

You're adding an additional 1 after 2nd if case.

if(xc <= 0 and yc >= 0)
    ans = min(yc, yb);
else if(xc <= 0 and yc <= 0)
    ans = 1; // <------- it should be 0
else if(xc >= 0 and yc <= 0)
    ans = min(xc, xb);
else
    ans = min(xc,xb)+min(yc,yb);
cout << ans+1 << endl;

there exists n * k^1.5 solution but it takes a lot of time....

C ~ 1400

D 1600-1700

lol

Could you write the case more clearly?

23104

because you can choose 2 3 1 0 4 :

01342 -break- [104424232424004113131423112311240]

10442423 -break- [2424004113131423112311240]

24240041 -break-[13131423112311240]

13131423112311240 -break- []

[] no more elements to choose [4,4] from hence answer is yes

exactly, can someone share how they reached this conclusion and their thought process during solving the problem?

I solved this question and I still don't understand the intuition behind it.

Here are some less complex observations for problem D :

1. Let's make a prefix array first. Now, our answer is definitely from one of the values in the prefix array.(or 0 if all prefix values are -ve). Why? cuzz we won't let our rating fall from a point where we reached , so out k must be a value we reached.

2. We can calculate answer for each prefix value (though it's easy to prove that optimal value is always a local maximum).

3. Begin traversing the prefix array now how to calculate the answer from this value of k = prefix[i] ? ---> Answer is : [ Σa_i + (maximum distance you go below from k in you prefix array) ]

How to prove this ? ----> You can think of it as : When you add something -ve that takes your prefix value below the threshold k, you actually add some EXTRA to your answer to keep it fixed at value k. Hence , whenever next time when again prefix value goes below k , again add value to EXTRA to keep it at k. Finally you will notice you added total EXTRA = max(0 , k — min(pref[i])).

--> min(pref[i]) is minimum prefix value that we reached.

I did this for every i, k = prefix[i]; resulting score = prefix[n] + max(0, prefix[i] — min(prefix[i + 1]....prefix[n]))

WHAT I DID STARTED WITH INDEX POINTER 0 NOW I TRAVERSE THE L AND R STRING FROM STARTING FOR EVERY DIGIT (0 , 9) IN [ L[I] , R[I] ] FOUND THE MAXIMUM INDEX IN MAIN STRING THEN SHIFTED THE INDEX POINTER TO MAXIMUM

IF NO CHAR IS PRESENT IN MAIN STRING — > HENCE NO SUBSEQUENCE CAN BE GENERATED -> "YES"

PS : TC 2 HELPED A LOT :)