By awoo, history, 20 months ago, translation, In English

Hello Codeforces!

On Feb/28/2023 17:35 (Moscow time) Educational Codeforces Round 144 (Rated for Div. 2) will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest, you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 6 or 7 problems and 2 hours to solve them.

The problems were invented and prepared by Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also, huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

UPD: Editorial is out

  • Vote: I like it
  • +198
  • Vote: I do not like it

| Write comment?
»
20 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Good luck everyone!

  • »
    »
    20 months ago, # ^ |
      Vote: I like it -75 Vote: I do not like it

    Generally, I like educational rounds but...

    Worst Contest I Have Ever Seen!..

    • »
      »
      »
      20 months ago, # ^ |
        Vote: I like it -65 Vote: I do not like it

      Worst Contest I Have Ever Seen!..

    • »
      »
      »
      20 months ago, # ^ |
        Vote: I like it -27 Vote: I do not like it

      Worst Contribution Voters I Have Ever Seen!..

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

      turkish.. hmmm... maybe the earthquake is responsible :(

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

        ...Said 10555th of last Div3 xD

        Note that you do not have any right to underestimate or make fun with an event which killed more than 45k people!.. ;( Also, stop racism...

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

Hope problem 'C' of this contest would be easy and not like the previous round.

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

hope this contest will make me expert

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

    :(

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

      even I lost everything which I gained after solving hard problem C from previous 2 contest

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

        Yes i saw, it's okay bro. It doesn't effect your skills. The learning here will help u become CM one day :)

»
20 months ago, # |
  Vote: I like it +18 Vote: I do not like it

BTW the cat in vovuh's profile in cute (◠‿◠)

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

I'll try to perform my best in this contest last 3 contests didn't go my way

»
20 months ago, # |
  Vote: I like it +7 Vote: I do not like it

Today is my birthday. I hope that in this round I will get good deltas.

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

Hopefully back to master, been a hardstuck purple for ages now

»
20 months ago, # |
  Vote: I like it -11 Vote: I do not like it

I hope for really good problems and good pastime in this contest!

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

Its better to skip Educational Rounds

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

    ur highest rating was in educational round

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

Why are there so few people take part in this time?

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

hope to get a big delta:)

»
20 months ago, # |
  Vote: I like it +11 Vote: I do not like it

Hope this is my CM promotion contest): (for the third time LOL)

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

    Didn't age well:(

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

      So sad , I hate letter K now !

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

        You should use a comment //don't use letter k instead of u

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

Why are so few people participating?

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

How can problem C be solved? Is it a DP problem? I figured out how to get the length but am stuck on counting the number of them. I also can't imagine that number of sets having maximum size being very large, is my intuition off?

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

    me 2

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

      Hint: In the optimal set, every next element is a multiple of the current one.

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

        I knew that but I don't still know how to solve it.

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

          Well because of that the maximum length is (maximum number of times you can multiply l by 2 while its less than or equal to r) + 1. Also because of this, if you multiply by anything greater than 3, the length will of course be less than maximum. So then you are just multiplying by 2 and 3 the maximum length # of times. Simply fix the number of times you multiply by 2 or 3 and binary search for largest number that we can multiply by that.

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

            There is no need to use binary search to find largest number that we can multipy by that .we can just use r/2/2/2.../2/3 that is the largest number,and the number of above 2 is before we cauculate;

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

              Ah yes you're right

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

    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)

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

    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.

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

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

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

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

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

    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.

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

      why do we only consider 2, 3? there's might be multiple of 5:

      like set{5,25} and 7 like {7, 49, ..}, and multiple of prime numbers within the range l, r

      Is it true or i missed understood ?

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

        If we can multiply by 5 it means we can multiply by 2 atleast 2 times as 2*2<5 so multiplying by 5 will never gives the biggest set size.

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

    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?

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

      you dont count these 4:

      4 8 16 32 96

      4 8 16 48 96

      4 8 24 48 96

      4 12 24 48 96

»
20 months ago, # |
  Vote: I like it +8 Vote: I do not like it

-12 in A... Yay

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

    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

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

      It doesn't even need to be that long. The string repeats every 8 characters, and the input string is always at most length 10, so even if the input string begins at the 8th character, it should end on the 17th character at the latest. Therefore, a length-17 string suffices, i.e. FBFBFFBFFBFBFFBFF

      Short Python Submission: 195354083

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

        That might be the case, but overoptimizing can sometimes lead to issues, for example, I overkilled with 200 on A, but for some reason, tried doing away with 2*n memory on D and wasted a good half an hour, which could have otherwise been saved.

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

      should BFB output "YES" or "NO". If we just consider a substring of the larger FB string then the answer is YES. But there a no valid L and R for which the string formed would be exactly BFB. The question is a little contradictory in this edge case.

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

        YES

        $$$\ell = 8, r = 10$$$

        There is no contradiction. Note that $$$\ell$$$ and $$$r$$$ are indices of the FB-string; they don't correspond to any particular values that generated characters.

»
20 months ago, # |
  Vote: I like it +227 Vote: I do not like it

Since the second number can be very large, print it modulo 998244353

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

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

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

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

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

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

    • »
      »
      »
      20 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it
      4,8,16,32,64
      4,8,16,32,96
      4,8,16,48,96
      4,8,24,48,96
      4,12,24,48,96
      5,10,20,40,80
      6,12,24,48,96
      
  • »
    »
    20 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
20 months ago, # |
  Vote: I like it +34 Vote: I do not like it

Well that C was a bit misleading with that modulo lol

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

Problem C is kind of similar to https://codeforces.net/contest/414/problem/B

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

Weird contest, managed to solve D easily but failed last minute submission on C xD

»
20 months ago, # |
Rev. 3   Vote: I like it -39 Vote: I do not like it

Can we considering move the contest time to sometimes when Indians couldn't participate? Like almost half (or even more) of the indian accounts ever do is waiting for paid solutions to get out and cheat during contests.

This will also allow the US participants to participate. The start time in the US east coast is 9:30am and 6:30 am in the US west coast. The contests will have a lot more high quality participants rather than just a bunch of Indian cheaters.

»
20 months ago, # |
  Vote: I like it +5 Vote: I do not like it

-7 on A. Sucked all the energy out of me and didn't feel like even trying B or C. Newbie here I come.

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

Were we supposed to do D with an O(nk) DP solution? If so, Python gave me TLE. I really need to learn C++ lol.

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

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

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

      Interesting! With the bound of 20 on k I assumed an O(nk) solution was what they had in mind. I'll try this problem more after the contest.

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

        My O(nk^2) solution got accepted. C++ lol

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

        I think they meant $$$O(n)$$$, since $$$k$$$ is so small it can effectively be treated as a constant. The problem gets a lot harder if $$$k$$$ has high constraints.

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

          check my submission 195331445
          it's O(n)
          tell me if it's wrong

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

            It's probably correct, but I still feel like approaches that exploit the small constraints on $$$k$$$ are simpler than approaches whose runtime is independent of $$$k$$$.

            My approach was to first try every possible subarray length of size 1 to k first (everything in the subarray gets boosted). After that, I considered subarrays of length $$$> k$$$ by reducing all values by $$$x$$$, computing the largest subarray sum, and elevating the sum by $$$2xk$$$ to account for $$$k$$$ of the values getting an addition instead of a subtraction.

            This has $$$O(nk)$$$ time complexity, so raising $$$k$$$'s upper bound can cause it to fail, thus making the problem harder.

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

      orz

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

Slept over and woke up right before the contest ended... fortunately I'm unrated.

I've misunderstood statement of D that I must modify k consecutive elements, and I wrote a solution by segment tree. However it's only a dp problem (with annoying corner case for x<0).

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

    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)

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

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

»
20 months ago, # |
  Vote: I like it +1 Vote: I do not like it

One of the few rounds where B felt far more easier than A. Question A just didn't made any sense and went over my head !!

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

How to solve D

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

    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

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

      thanks, can you please tell a resource to learn segment trees?

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

      How do you prove this by contradiction?

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

        Suppose the optimal solution is $$$...[a_i+x,a_{i+1}-x,a_{i+2}+x,a_{i+3}-x,a_{i+4}+x]...$$$

        Construct $$$...[a_i+x,a_{i+1}+x,a_{i+2}+x,a_{i+3}-x,a_{i+4}-x]...$$$,the answer won't get worse.

»
20 months ago, # |
  Vote: I like it -9 Vote: I do not like it

Worst C ever.

»
20 months ago, # |
  Vote: I like it +5 Vote: I do not like it

perhaps someone solved A in a difficult way.

here is how I solved that. It's really easy and you don't need to debug.

string s; int n;

int main() {
	for (int i = 1; i <= 100; ++i) {
		if (i % 3 == 0) s += 'F';
		if (i % 5 == 0) s += 'B';
	}
	for (int T = read(); T--; ) {
		read(n); string t; cin >> t;
		if (~s.find(t)) puts("YES");
		else puts("NO");
	}
}
  • »
    »
    20 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
20 months ago, # |
Rev. 3   Vote: I like it -54 Vote: I do not like it

Generally I like educational rounds, but this is the worst contest in the entire fucking century

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

Very nice contest! Congrats to the authors! I really enjoyed A-D, but didn't come up with one solution for D! Can anyone tell his solution?

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

    how to do problem C?

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

      First of all, the maximum size is k + 1, where k is the maximum number such that l * 2 ^ k <= r. Now i want to see what is the maximum number val_left_2 >=l, for which we have val_left * 2 ^ k <= r. This can be done with binary search or math. We have to observe that we can use multiplication by 3 or 2 from the previous number that is in the set, because for numbers greater or equal than 4 you decrease automatically the size of the maximum set, because you use in one operation at least 2 multiplication by 2. We alse have to observe that we can use multiplication by 3 just one time, because if we use 2 times, 3 * 3 = 9, and 2 ^ 3 = 8 < 9, so we also decrease the size of the maximum set. We have to find again using bynary search or math what is the greatest number val_left_3 >= l such that multiplying it just one time by 3 and after that just only by 2, the set has the same size. Suppose the maximum size is k. For numbers that we can multiply by 3 we have k — 1 possible answers, because we can use multiplication with 3 once time in position 2, 3, .. k. Suppose that we have the following example: l = 1, r = 12. We have k = 3(1 * 2 ^ 3 <= 12), so the size is 4. Now we can have the following sets: (1, 3, 6, 12), (1, 2, 6, 12), (1, 2, 4, 12). See that we chose to multiply by 3 at each set the number on the second, third, or fourth position. So the final answer is: (val_left_2 — l + 1) + (k — 1) * (val_left_3 — l + 1). I hope that you understand!

»
20 months ago, # |
  Vote: I like it +29 Vote: I do not like it

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

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

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

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

      Maybe you didn't do $$$x:=−x,k:=n−k$$$ when $$$x<0$$$

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

        I did it. I chose the maximum answer between the two situations.

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

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

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

      maybe that's why $$$k\leq \min(20, n)$$$.

      It seems that you can make $$$k\leq n$$$ with a segment tree :)

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

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

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

In E, I solved the problem when the root was fixed. Can anyone tell me how to choose root optimally?

I tried to choose the leaf with a minimum distance to some other leaf, but it didn't work.

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

    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

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

Got 5 wrong answer on C and wasted more than an hour over a stupid if statement.

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

Can someone help me figure out why TLE for C, feels like the order is fine.

https://codeforces.net/contest/1796/submission/195350573

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

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

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

      ohh thanks, do you know how many operations per second we can do in codeforces.

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

        Generally, with fast I/O and such, you should be able to handle about $$$10^8$$$ operations per second, but most standard solutions should fall at roughly $$$10^7$$$ operations or less. If you roughly estimate your code as performing $$$10^7$$$ operations, then it should be fine, but if you estimate it at $$$10^8$$$, then it's almost certainly slower than the intended solution and it might end up failing, but it also might actually pass, so it's worth submitting if you can't come up with any improvements.

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

      If i do binary search between l and r then it should be able to pass ig. thanks a lot.

»
20 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Was definitely not an educational contest I liked the questions tho

»
20 months ago, # |
  Vote: I like it +8 Vote: I do not like it

I think that the problems were easy(was able to view only A and B), solved A but messed up in B probably some stupid edge case.

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

When can I able to see the failed test cases?

»
20 months ago, # |
  Vote: I like it +28 Vote: I do not like it

My worst performance ever. I didnt hate the contest but man problem A got me. RIP

»
20 months ago, # |
  Vote: I like it -15 Vote: I do not like it

Why NlogN solutions were not allowed for 'C' ? My solution with TLE :- N*log N DP sol

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

    20000 testcases?...

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

      They should have then given 1sec allowed time limit . I saw top solutions can do in O(1) with some formulae which will be enough to run in 1 sec. I got misleaded with time limit and limit on N. either they should have increased 'r' to 1e9 or decresed time to 1 sec.

      I don't know ,seems like I am frustrated by TLE submissions .Don't mind.

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

        I understand, but the general thing is to check whether statement says something about limit of sum of n (or something like this) or not. Last case means that you have to come up with something like O(log n) for test case (in this particular problem). Nevertheless, sad :(

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

    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

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

.

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

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

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

    Sounds working, did you implement something wrong?

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

    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.

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

Some hints how to solve B?

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

    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.

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

What's an example where the answer is 2 for problem E?

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

for Problem C my solution was looping from [l,r] but it was giving TLE on test 3. I supposed my solution should have passed the constraints of 1<=l<=r<=1e6. Can anyone brief on how to predict approximate time complexity based on these constraints.

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

C destroyed me :( How to get total number of possible sets ????? ^_^

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

    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.

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

      Thanks used your idea, actually we can do without binary search Here's my concise code

      void solve(){
          int l, r;
          std::cin >> l >> r;
      
          int n = l, j = 1, cnt = 0;
      
          while(n <= r) {
              j <<= 1;
              n <<= 1;
              cnt += 1;
          }
      
          j >>= 1;
      
          int ans = r / j - l + 1;
      
          j /= 2;
          j *= 3;
      
          if(j > 0) {
              ans += std::max(0LL, (cnt - 1) * (r / j - l + 1));
          }
      
          std::cout << cnt << " " << ans << "\n";
      
      }
      
  • »
    »
    20 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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

»
20 months ago, # |
Rev. 3   Vote: I like it +9 Vote: I do not like it

Not sure why D had k<=20, you could easily solve it in O(N log N).

First, if x<0, then make x=-x and k= n-k. The problem stays the same.

There are 3 cases.

  1. The optimal subarray is nothing (0).

  2. The optimal subarray has length <=k. For this case, we add X to every element and use a sliding window of length K to find the maximum prefix sum with <=k elements. This runs in O(NlogN)

  3. The optimal subarray has length >k. We subtract X from every element and use modified Kadane's to find the largest subarray sum. Then, we add 2*k*x to this value to account for the k elements that we can add X to. This runs in O(N).

Just take the max of these valeus to get the answer

EDIT: I saw another solution solving k<=n, but it used Segment Tree. this solves it with elementary methods.

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

    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

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

      If x<0, then do the thing I described in the beginning (set x = -x, k = n-k).

      Then we can use a sliding window to compute the answer, as follows:

      A pseudo code is as follows:

      1. initialize variable to store the best answer for case 2
      2. create prefix sum array, with p[0]=0
      3. make a multiset with just 0 in it
      4. for int i=0 to <n:
      5. if i>=k then delete p[i-k] from multiset
      6. update best answer to max of best and sum of first i elements — smallest element in multiset
      7. add this prefix to the multiset

      if you have any other questions, lmk.

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

        I read your submission and got it thank you

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

Can Somebody can say what could be the test case where my solution get failed in Problem A

https://codeforces.net/contest/1796/submission/195295985

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

    $$$BFFBFFBFBF$$$

    You need to repeat that string more times, as the BF-string is the repeat of $$$FBFFBFFB$$$

»
20 months ago, # |
Rev. 3   Vote: I like it +27 Vote: I do not like it

Problem D can be solved in $$$O(n\log(k))$$$(or $$$O(n)$$$).

Consider two cases of interval length $$$len$$$ respectively:

  1. $$$len\le k$$$: the answer will be $$$\max(Sum(r)-Sum(l-1)+(r-(l-1))*x)$$$. We can calculate $$$F(r)-min(F(l-1))$$$ for every $$$r$$$ where $$$r-k< l \le r$$$ and $$$F(i)=Sum(i)+i*x$$$. This can be solved in $$$O(n*\log k)$$$ by using multiset (or using monotone queue in $$$O(n)$$$).

  2. $$$len>k$$$: the answer will be $$$\max(Sum(r)-Sum(l)+k*x-(r-(l-1)-k)*x)$$$. We can calculate $$$G(r)-min(G(l-1))+2*k*x$$$ for every $$$r$$$ where $$$l \le r-k$$$ and $$$G(i)=Sum(i)-i*x$$$. This is easy to solved.

Here is the code:

/* Generated by powerful Codeforces Tool
 * Author: sleep__
 * Time: 2023-02-28 22:35:03
**/
#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
using namespace std;
using ll=long long;
const int N=300005,P=998244353;
void solve(){
    int n,k,x;
    cin>>n>>k>>x;
    if(x<0) x=-x,k=n-k;
    vector<int> a(n+1);
    vector<ll> s(n+1),ss(n+1);
    multiset<ll> st;
    st.insert(0);
    st.insert(1e18);
    ll mn=1e18,ans=0;
    if(k==0) mn=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        s[i]=s[i-1]+a[i]+x;
        ss[i]=ss[i-1]+a[i]-x;
        if(i>=k) mn=min(mn,ss[i-k]);
        if(i>k) st.erase(st.find(s[i-k-1]));
        ans=max({
            ans,
            s[i]-*st.begin(),
            ss[i]-mn+2ll*k*x
        });
        st.insert(s[i]);
    }
    cout<<ans<<'\n';
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t=1;
    cin>>t;
    while(t--) solve();
    // while(t--) cout<<solve()<<'\n';
    return 0;
}
  • »
    »
    20 months ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    $$$O(n)$$$ is also possible by using monotone queue

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

    Thank you for the approach, learned something new :)

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

    If you don’t mind, could you tell me the extension you use to display date-time and author?

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

Since the second number can be very large, print it modulo 998244353....lol

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

Can the answer to question C be greater than a billion?

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

    The answer of 3*2*2*...is less than log(n).

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

      OMG the statement in C confused me a lot.. they said that answer can be very large TT..

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

        is it a kind of mistake although it's one hundred percent on purpose?

        it can't be really large but it says it can be.

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

    Nope. $$$2^{20}$$$ exceeds $$$10^6$$$, so the size won't exceed 20, and you're allowed at most one 3 (three 2s are objectively superior to two 3s, two 2s are objectively superior to any number greater than 3). There are at most $$$10^6/2 = 5(10^5)$$$ possible starting values, so that's already an upper bound of $$$20 \times 5(10^5) = 10^7$$$. This is an incredibly generous upper bound, since having a high number of starting values means the sequences are even shorter, and a good chunk of those starting values won't even be able to accommodate a single 3.

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

any idea why this submission for D gives a TLE? Submission

Help appreciated.

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

    when x<0, k becomes n-k,and O(n*k) becomes O(n^2)

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

In B, I generated all substrings of a and b, stored them in map and checked for the common substring of max length. If its length >=2 then ans will be (string). But this gave TLE. The whole process of map and substring generation won't exceed n^2 where n is length of a which is <=50. Can anyone help me with this? Here's the submission https://codeforces.net/contest/1796/submission/195333589 I don't get how it is giving TLE, fucked up the entire contest. Newbie here I am

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

    Generating all the substrings actually takes O(N * N * N). Imagine there are N * N substrings in total and each one takes O(N) time to copy.

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

      But inserting in a map takes log(n) time.

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

        It's not true for string type. I didn't read your entire code, but something like set.insert(s) where s is a string makes me concern. When insert() get called, I am pretty sure the parameter string get copied first which takes linear time. Later pushing it down to a ordered structure requires string comparison potentially takes linear time per operation. Overall I believe the time complexity for inserting a string to the set is O(N + N * logN) where N is the length of the string.

»
20 months ago, # |
  Vote: I like it +23 Vote: I do not like it

seeing that amount of hate towards problem C makes me disappointed. so want to remind everyone about this recent discussion about criticism of problems in comments after contest. please read it if you didnt before

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

During contest I thought task C was to count the no. of longest paths in a DAG, got TLE and couldn't think of any other way. Skipping C to solve D would have been a better decision. Also, there is no reason for k to be small, my solution works in O(nlgn). https://codeforces.net/contest/1796/submission/195367954

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

    As I understand it, $$$k$$$ is kept small to allow for a certain class of solutions to pass as well. Since this is an educational contest, that probably makes sense from the aurbors' perspective.

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

    Thank you for educational videos! But the link doesn't work because it doesn't start with http://

»
20 months ago, # |
  Vote: I like it +3 Vote: I do not like it

How to solve F?

»
20 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Good luck everyone!

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

195352766 For problem A. Hi can someone help with figure out why my code is giving a wrong answer on test 2. Since it is 144th token in test 2 out of 2046 test cases where the code outputs the wrong answer I am unable to see exactly where I might have a logical error. From all my thinking upto now the error with my code could be the time complexity but since it's not giving me a TLE so that beats me too. Any help would be really great. Thanks.

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

    Counterexample: "BFB", your code output "No" but thats wrong. FB string starts with: "FBFFBFFBFBFFBFFBFBFFBFFB", and fb[7]-fb[9] is "BFB". Problem of your code is that for j%15==0 you add two letter in a row and dont check a substring with only one added letter. I advice to generate fb-string once before solve cycle and just search given substring in fb That will fix this error and also will help with speed.

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

Can someone explain me the dp approach for the Problem D. Thank you in advance..

»
20 months ago, # |
  Vote: I like it +17 Vote: I do not like it

The problems are cool. Love this contest!

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

when will the rating be changed?

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

    system testing just completed.Just wait for an hour

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

      I am very excited about this contest rating because I think I will become Pupil from Newbie.

»
20 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Joy of Getting AC in last minute >>>>>

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

D is so good that it gave me headache :)
Seriously, I figured out the array needs to be pre processed(minus x), but the prefix complement subtraction is beyond my imagination. Is it something easy to think of or just a common idea? Hopefully not the former one
ps. it sounds way easier as I write it down that way :(

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

    I personally found the idea to be more intuitive when you think of it as querying a ranged data structure. Once it's down to that, it's still probably not very easy. I remember though that I saw a video on youtube, maybe 2022/21, where a Red solved some question that used the idea, basically, each node in the segment tree would need to store 4 values, the sum of all elements under it, the maximum subarray sum, the maximum subarray sum (prefix) and (suffix), using these 4, you can create the required segment tree.

    My submission Here, st_s stores the sum of all child elements, st_m stores the maximum subarray sum, st_lm stores the maximum subarray sum (prefix) and st_rm stores the maximum subarray sum (suffix)

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

Was this unrated?

Why did I not receive any rating for this contest?

Anyone, please tell

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

    Well, I want to know it, too. The System Test is over.

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

    If in any unfortunate scenario, a contest is actually unrated, it gets updated as such on the contest accouncement blog itself. I understand your emotion, I feel the same way, but please be patient, changes can sometimes take longer than expected.

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

When will the tutorial be uploaded ?

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

Problems are so nice just if we removed problem A

Thanks for good BCD !

»
20 months ago, # |
  Vote: I like it +3 Vote: I do not like it

If it had been k <= n in problem D, I would havent got 5 penalties for WA on test 2 (solved the problem in 9 minutes, trying to fix bugs for 30 minutes). Kind of an easy but annoying dp problem imo.

»
20 months ago, # |
  Vote: I like it +6 Vote: I do not like it

why no rating ,it's already 22hours

»
20 months ago, # |
  Vote: I like it +6 Vote: I do not like it

When will this contest be rated?

»
20 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Regex solution for B: 195451488, Perl.

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

https://codeforces.net/contest/1796/submission/195318855 This code was hacked (TLE) and I missed the first place.

But I just submitted the same code again  https://codeforces.net/contest/1796/submission/195453193 , then got AC (1606ms) .

It is sad to see this happen due to the blurring of judge speed by time of day :(

»
20 months ago, # |
  Vote: I like it +6 Vote: I do not like it

I participated in this contest and solved one problem but still didn't get any rating changes why? I'm a new to codeforces.

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

    The rating will get updated in some time, for knowing about the expected rating change you could use chrome extension CF predictor

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

    educational round rated slow, this time unusual slow ,but don't worry,just do something else ,you will recieve it later.

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

Excuse me, how could my solution of B get AC on the competition, despite it's wrong and didn't pass the rejudge? Unfortunately, i have no proofs, but yesterday it got accepted, and today it was rejudged and got WA on 1st test.

This solution: 195287792 (it's obviously wrong, but it passed all the tests yesterday)

Upd. the solution above is a little bit messy. Here is the same, but shorter one: 195464083.

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

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).

»
20 months ago, # |
  Vote: I like it +25 Vote: I do not like it

when are updated ratings coming?

»
20 months ago, # |
  Vote: I like it +22 Vote: I do not like it

I finally reached Candidate Master :D

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

if two people has cheated, both of them were skipped. I think if the rating changing is negative, they shouldn't be skipped.