Generally, I like educational rounds but...

Worst Contest I Have Ever Seen!..

I agree, at least without trash problems...

didn't age well

:(

:(

Happy birthday liar :) Today isn't your bithday)

yesss, [user:blitzage] orz

all the best, ig it's possible now

ur highest rating was in educational round

And positive too x )

congo

Didn't age well:(

continuous contests may have tired everyone

me 2

size of maximum subset is log2(r — l) + 1

to calculate count subset u need to calculate sum (1) (2), where:

(1) count of i, l <= i, that i * 2^(sz-1) <= r

(2) count of i, l <= i, that i * 2^(sz-2)*3 <= r, and multiply by (sz-1) (count of take one number from sz — 1 numbers)

It's not a DP problem. For a certain length there can only be some 2 and some 3 as factor, for each number of 3 count the number of valid left boundary for that. Should be fast enough if you pre calculate the combination result.

The set will have this form : $$$[x, 2*x, 4*x, ...]$$$ or $$$[x, 3*x, 6*x, ...]$$$. Note that we can only multiply by 3 at most once, because $$$[x, 3*x, 9*x]$$$ can be replaced by $$$[x, 2*x, 4*x, 8*x]$$$

Now we will find some $$$x, y$$$ such that for any set that has the lowest number in $$$[l,x]$$$ we can afford to multiple by 3 once, and set having lowest number in $$$[x,y]$$$ can only multiple by 2

Then the answer is $$$(x-l+1)*maxsize + (y-x)$$$

the maximum length is 1+m, where m is the max value where $$$2^m \cdot l \leq r$$$. Given a set $$$S={ a_0, a_1,\cdots, a_m}$$$, with $$$b_i=a_i/a_{i-1}$$$, one can show that $$$B={b_1,\cdots, b_m}$$$ has only 2s, or exactly one 3( and the remaining values 2). If B has only 2s, one can choose all $$$a_0$$$ in the rank $$$[l, r/2^m]$$$, and if B has exactly one 3, you can chose $$$a_0$$$ in the range $$$[l, r/(2^{m-1}\cdot 3)]$$$, if this range is valid, and the position of 3 in the rank $$$[1,\cdots, k]$$$.

The answer is: $$$(r/2^m - l + 1) + (2^{m-1}\cdot 3 \leq r/l) * (r/(2^{m-1}\cdot 3) - l + 1) * m$$$

First of all let's calcualate the max length. Notice that it can be achieved in a such way: x 2x 4x 8x and so on. So it can be easily calculated in log(n) time. Now lets find out how all sequences of this length look like, for example for l=4, r=100:

1. 4 8 16 32 64 -> *2 *2 *2 *2
2. 4 8 16 32 96 -> *2 *2 *2 *3
3. 4 8 16 48 96 -> *2 *2 *3 *2
4. 4 8 24 48 96 -> *2 *3 *2 *2
5. 4 12 24 48 96 -> *3 *2 *2 *2
6. 5 10 20 40 80 -> *2 *2 *2 *2
7. 6 12 24 48 96 -> *2 *2 *2 *2

So its not optimal to perform any kind of operation except *2 and *3 in this sequence, because if you do *4, you can replace it with *2 *2 and get sequence with higher lenght. Also we dont care about in what order they were performed since multiplication is a communicative operation. Now we can fix number of *3 operations, calculate total number of seq with this count of *3 operation: C(numberof(*3), maxsize) and then find from what numbers they can start.

I got the logic, and my code is working for first 3 examples, but for the case 4 100, shouldnt it be 5 3 instead of 5 7?

in Problem A the pattern of BF string repeats so just set the BF string as "FBFFBFFBFBFFBFFBFBFFBFFBFBFFBFFBFBFFBFFBFBFFBFFBFBFFB" and compare every substring of length k to get the answer

First time this is a misleading information in CodeForces for me.

good think that's what happend cause i forget to modulo it :>

In problem C example 4, (input -> 4 100), what are the 7 arrays which satisfy the constraints? I got only 3.

I totally thought that my "perfectly correct solution" is going to get WA

I bet there are cheaters in US too. Quit your racism and focus on "high quality questions" rather than the "high quality participants" (many Indians too, will be counted as high quality participants as a matter of fact). Don't get salty if you are not able to get positive delta.

deleted

Same but solved B and C too

I solved it with an O(n) solution, could still fail system test though

for the subarray's length <= n-k , it can be solve by just searching the maximun subarray sum and plus the length*(-x)

for the length > n-k , just search all possibility from n-k+1 to n .(k<=20)

I don't think $$$x<0$$$ case is annoying. You can observe that when $$$x<0$$$, you should add $$$x$$$ to some prefix(say $$$p$$$) and suffix(say $$$s$$$) such that $$$|p|+|s|=k$$$, and subtract $$$x$$$ from remaining elements.

Now you can find max subarray in $$$O(n)$$$ using simple $$$dp$$$.

You have only $$$k$$$ options for $$$|p|$$$. Thus time complexity is $$$O(n \cdot k)$$$.

Solution for D:

This problem can still be solved even under the constraint of $$$0\leq k \leq n$$$.

If $$$x<0$$$,do:$$$x:=-x,k:=n-k$$$.

If $$$x \geq 0$$$,we notice it is always optimal to use the "+x" operation for consecutive $$$k$$$ numbers(use proof by contradiction).

Next, we need to get the max-sub-segment sum of these sequences:

• $$$a_1+x,a_2+x,...,a_k+x,a_{k+1}-x,...,a_n-x$$$;

• $$$a_1- x,a_2+x,...,a_k+x,a_{k+1}+x,...,a_n-x$$$;

• ...

• $$$a_1- x,a_2 -x,...,a_{n-k}-x,a_{n-k+1}+x,...,a_n+x$$$.

We can use a segment tree.Maintain a segment tree supporting the following operations:

• Single point modification

• Query max-sub-segment sum

How do this work? I don’t understand what the ~ operator is doing here

how to do problem C?

I did like that, but I didn't get Accepted :(

upd: I know why i didn't get AC and I pass it now.

there are a few obvious mistakes.

1. I forgot to reduce the value in the positions out of $$$[i, i + k - 1]$$$

2. I didn't ask for the max-sub-segment sum of $$$[1, n]$$$, $$$[i, i + k - 1]$$$ instead.

silly me!!

Segment tree is overkill, you can replace it with pref/suff maximums.

I thought of the same idea but got confused because of the low constraint on K

code for the mentioned idea

You probably can't choose root and need make rerooting (when you calculate dp with fixed root and then recalculate for every root)

In my solution i fixed k with binsearch and made dp with rerooting

Your time complexity is O(t(r-l)), notice that there could be a lot of test cases

20000 testcases?...

You need to do it in LogN, because of the number of test cases. I also suspected whether there is a limit on the sum of (R-L+1) over all cases or not, so I asked the judges a question. There wasn't any

a abcd should give NO but in your case it will give a* which I think is wrong

Sounds working, did you implement something wrong?

you are right. Are you checking for when first and last letters don't match and lengths of a or b is one. then answer should be no.

If the first letters match, we can just form the template with first letter and asterisk.

If the last letters match, we can just form the template with asterisk and last letter.

Beyond that, we need to make sure a substring of length at least 2 matches between both strings. If we don't have a matching substring of length 2, the answer is NO (alternating between asterisk and non-asterisk won't work, since there are more asterisks than non-asterisks then). But if we do have a matching substring of length 2, then we can simply construct a template as asterisk, two-length substring, asterisk (equal number of asterisks and non-asterisks so it counts).

Checking whether the two strings have a matching length-2 substring can be done by simply storing all length-2 substrings of the first string in a set/map (or an array of size 26*26) and then retrieving the length-2 substrings of the second string to check if any of them were found in the first one.

1-2 2-3 3-4 4-5 3-6

There are 2e5 testcases for 2 seconds. For each case, expected correct time is O(1)

Say the smallest number in the set is a. Then all numbers in the largest set are of the form a*(2^x) or a*3*(2^x). Use binary search to find the answer.

base l, l *2, l * 2 * 2, l * 2 * 2 * 2, .....

sometimes it is possible to change one of * 2 to 3. But not two of them, because * 3 * 3 > * 2 * 2 2, so if you can do * 3 * 3 and still be <= r you can change them to * 2 * 2 * 2 and increase amount of numbers. Same with * (>= 4)

first number in base is l, last is l * 2^k. We want to find max l' such that l' * 2^k <= r

it is r / 2^k, so l, l + 1, ..., r / 2k is good

same if *2 -> *3, but also * (cnt — 1) because we can chose which *2 to change

Could you explain your 2nd case ? If $$$x < 0$$$ then $$$k$$$ can be very big, so the naive $$$O(n*k)$$$ doesn't work. I'm not familiar with the $$$O(nlogn)$$$ technique