When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

By awoo, history, 4 years ago, translation, In English

Hello Codeforces!

On Aug/14/2020 17:35 (Moscow time) Educational Codeforces Round 93 (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 Roman Roms Glazov, 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!

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 Um_nik 7 111
2 tmwilliamlin168 7 119
3 neal 7 144
4 Farhod 7 167
5 tribute_to_Ukraine_2022 7 178

Congratulations to the best hackers:

Rank Competitor Hack Count
1 Dorost 13:-6
2 dcordb 3
3 KnightKnight 4:-4

85 successful hacks and 696 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A MikMirzoyanov 0:01
B tamahom1 0:02
C IAKWF 0:02
D shinigami11 0:09
E dorijanlendvaj 0:20
F nikolapesic2802 0:08
G tfg 0:22

UPD: Editorial is out

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

| Write comment?
»
4 years ago, # |
  Vote: I like it +56 Vote: I do not like it

Month of contests...... thanks CF <3

»
4 years ago, # |
Rev. 2   Vote: I like it +71 Vote: I do not like it

14th Aug — educational codeforces round 93

15th Aug — atcoder beginner contest 175, Facebook hacker cup round 1

16th Aug — codeforces Global round 10

I am really excited!

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    +1

  • »
    »
    4 years ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    14th Aug — educational codeforces round 93

    15th Aug — atcoder beginner contest 175, Facebook hacker cup round 1,Codevita

    16th Aug — codeforces Global round 10,Google Internship Test

    BUSY DAY's

    May I couldn't Perform well in these 3 days but i will learn many new things..

    I am also excited!

    All the Best

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      bro, did you get the mail regarding google internship test.Since, I also register for internship but haven't got any mail regarding this.

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Not yet but my friends got. I registered at last date so, i guess they are sending email according to registration date

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes ,I got the mail..

»
4 years ago, # |
  Vote: I like it -24 Vote: I do not like it

can anyone tell me the soultion approach of codeforces div 2 664 c problem. http://codeforces.com/contest/1395/problem/C

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

    You can just brute force the answer, i was pretty annoyed that i did not manage to solve it during the contest https://codeforces.com/contest/1395/submission/89732090 ...

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it -6 Vote: I do not like it

      but i dont understand the brute force logic

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

        Every element of the array a (i will use the definitions from my code) can be combined with any element from the array b. So for every element with index i from a (i = 0 , N — 1) you create an array arr of M elements where arr[j] (j = 0 , M — 1) = a[i] & b[j]. If i == 0 (we are at the first element of the array) we mark in the bitset as true every element from arr and if i > 0 we will iterate over the bitset and we will mark as true in a new bitset the values val | arr[j] where val is a value from the first bitset which was already marked as true. By doing this at every step i (i = 0 , N — 1) you will have marked in the bitset every possible result for the expression c[0] | c[1] | ... c[i] (c having the meaning from the statement). After that you copy the second bitset in the first one. The bitset from the end will have marked as true every value which is a possible answer for the problem.

        PS. 512 is the size of the bitset because the maximum possible answer is 511(2^9-1). I hope that my explanation is decent.

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

    you will find it in Competitive Programmer’s Handbook(by Antti Laaksonen), page no.102.

    I learned a lot from this book

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

    you should ask this in the editorial part of that round, this is not related to this round.

»
4 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Standard Div2 round vs Educational round , which do you think is tougher ?

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

    div 2 I guess

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

    for me educational rounds are easier than div2

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

    Don't know which one is tougher. But for me, problems from educational rounds seem to be more interesting.

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

    It's different for me, I enjoy solving standard Div 2 more, I usually get pretty upset while solving Educational rounds.

»
4 years ago, # |
  Vote: I like it -18 Vote: I do not like it

where is the comment-As a Tester give me a contribution..LOL

»
4 years ago, # |
  Vote: I like it -23 Vote: I do not like it

what is the scoring distribution?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In educational rounds, all the problems have same weight-age, therefore there is no scoring distribution.

»
4 years ago, # |
  Vote: I like it -13 Vote: I do not like it

Lucky month for competitive programmer

»
4 years ago, # |
Rev. 2   Vote: I like it -22 Vote: I do not like it

good contest

»
4 years ago, # |
  Vote: I like it +148 Vote: I do not like it

I got covid 19, I am on my fourth day of isolation. I'm not feeling very well, but codeforces has helped me a lot to distract myself, wish me luck in this contest

»
4 years ago, # |
  Vote: I like it +33 Vote: I do not like it

I don't really understand why they say "6 or 7 problems". Aren't they sure about the number of problems till the last minutes?

»
4 years ago, # |
  Vote: I like it -62 Vote: I do not like it

Let us see what are we going to have today, long queue, weak pretest, complicated problem statement, or all of these together.

»
4 years ago, # |
  Vote: I like it +31 Vote: I do not like it

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

    Can relate, I had WA on test 6 but then got stuck at WA on test 7.

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

      WA on test case 6 LMFAO

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

        Test 6 failed then try this:
        1 3 1
        10
        8 5 3
        12
        Expected: 146

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          my code gives output:146..... but i got WA on 6

          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Ohh yes now I remeber there is some more issue. I changed my entire approach instead of doing greedy I went to DP.

            • »
              »
              »
              »
              »
              »
              »
              4 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              can you please explain why the greedy logic does not work in problem D

              • »
                »
                »
                »
                »
                »
                »
                »
                4 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                I dont know fully. The test case I mentioned clearly show we have to do some case work when 2 colors with 1 pair and one with more than one remains. So may be some more such case work would be required to make it work. Has anyone solved this using Greedy, if yes please comment your submission id.

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

            Try 2 2 2
            2 2
            2 2
            2 2
            ans: 12

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

    For those wondering: test 7 could be something similar to

    4 2 2
    3 3 3 3
    4 4
    4 4
    

    Some greedy approaches print 32, but the answer is 48.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Am I only one who couldn't access codeforces for almost an hour during the contest? (I posted this and got downvoted, idk why).

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It seems nowadays codeforces has better problems than atcoder... — aid

just look at problem G today and you'll find you were wrong.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why don't you like problem G? For an educational round, it is fine. I dislike E and F much more.

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

      Could you explain your solution? I look at your code but cannot get it. Thanks in advance.

      UPD: Nevermind, I understood it now. I think your sieve-like code for handling the largest divisor is so smart.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Will u plz tell , were E and F too boring or among the standard ones ??

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        They were definitely not standard problems, and for an educational round that wouldn't even be an issue. I didn't really like how E was pretty much an implementation exercise. Looking back, F wasn't actually that bad.

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yup .. Personally i also think that F was good , and also E was heavy implementation (especially for me who did coordinate compression and segment tree) .

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

It was really an educational round reminded me to study ..

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I got problem A wrong, than was stuck on it to realise my initial idea was correct. Skipped B and went to solve C, cause I couldn't improve ranking at that point. Never solved C, I'm starting to believe I am dumb at this point...

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Don't be shy bro. Most of us started like that if you don't want to believe, just check my rating graph

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

    I can relate to this & it even become worse when no one is there for help. Just keep practicing & don't hesitate to look for editorial & video solution. In case you need any help in A & B you can refer this

»
4 years ago, # |
  Vote: I like it +17 Vote: I do not like it

What a nice contest but I think D is a little easy with typical DP

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you please explain the states of your dp?

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      F[i][j][k]=maximum sum from first i largest R, j largest G, k largest B.

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

      I'm not good at explaining things so sorry in advance if people feel my explaination harsh

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You need to do some greedy before this typical dp. This costed me 2 WA.

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

      as I said before, you must DP with i largest, j largest, k largest so you must sort three arrays before dp

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

        Yeah, that's why it's not a classical dp. You need to be clever enough to get the idea.

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Oh. I tryed to use dp but missed some status trans

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I don't think this was an easy problem. Maybe it's not hard to guess that the solution is dp but if you want to be sure that this solution is correct you need to prove that in the maximum total area obtained by using i red sticks, j green sticks and k blue sticks there exists a rectangle with sides (ri, gj) or (ri, bk) or (gj, bk). Maybe I'm missing something but it wasn't trivial and took me a while to prove.

»
4 years ago, # |
  Vote: I like it +4 Vote: I do not like it

how to solve C please help

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

    You subtract 1 from every element and it becomes a standard problem. https://www.geeksforgeeks.org/number-subarrays-sum-exactly-equal-k/

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Elaborate , coz i still dont get it.

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

        When you subtract 1 from each element, the problem becomes counting the number of subarrays whose sum is 0.

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          OMFG. There is no way u came up with this during the contest. You had to have solved this type of problem earlier. Anyway,Thanks man!

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

            how i realized it during the contest instead of writing it as

            $$$\sum_{l}^{r} ( a_i ) = r-l+1$$$

            write it instead as

            $$$\sum_{l}^{r} ( a_i ) = \sum_{l}^{r}(1)$$$

            which is equivalent to

            $$$\sum_{l}^{r} ( a_i ) - \sum_{l}^{r}(1) = 0$$$
            • »
              »
              »
              »
              »
              »
              »
              4 years ago, # ^ |
                Vote: I like it +8 Vote: I do not like it

              This is so beautiful <3

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

              mpily really liked your thought process man... appreciable!!!

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

              I saw the solution and was unable to digest why subtract by 1. Now it's clear. Thanks man.

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

              your explanation is superb

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

      Could you elaborate more?

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

        The problem asks you to count the number of subarrays whose sum equals to its length right. So imagine if we subtract 1 from every element of that subarray, we end up subtracting the length of the subarray from the sum of its elements! If that subarray satisfy the condition of the problem statement then this new sum must be 0. That is why after subtracting 1 from all elements we count the number of subarrays whose sum is 0. Hope it helps.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Why are you adding map[cursum] everytime to the answer?

  • »
    »
    4 years ago, # ^ |
    Rev. 3   Vote: I like it +12 Vote: I do not like it

    first create prefix array then

    then this should be true for subarray of (l,r) to be good.

    prefix[r] - prefix[l - 1] = (r -l) + 1

    l - prefix[l - 1] = r - prefix[r] + 1;

    try to understand this part on your own
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    My solution was a bit more complicated than cote's solution, but I think it is worth sharing. Let $$$p_i$$$ be the sum of the interval $$$a_{1, \ldots i}$$$ for all $$$i$$$ (prefix sums). Now let $$$c_i = p_i - i$$$. Notice that the number of good intervals starting in $$$1$$$ is the number of ocurrences of $$$0$$$ in $$$c_i$$$. For that we will keep a map $$$cnt$$$, where $$$cnt[x]$$$ is the number of ocurrences of $$$x$$$ in $$$c_i$$$. Now, we will "remove" the first element and update the prefix sums and $$$c_i$$$. Notice that all values of $$$c_i$$$ will change by a same value

    $$$d + c_i = c_i - a_0 - (i - 1) \Rightarrow d = -a_0 + 1.$$$

    Then we have that the

    $$$cnt[x] = cnt[x - d]$$$

    . So it is sufficient to keep a variable d and update it in each iteraction (and thre is no need to update $c_i$ or $$$p_i$$$). Submission: 89922879

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Problem D.... why????

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Solutiom of C in less than O(n^2)..??

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i think it should be O(n) using hash map or something

  • »
    »
    4 years ago, # ^ |
    Rev. 3   Vote: I like it +4 Vote: I do not like it

    After getting the prefix sums
    Basically what you need to find is $$$pref[r] - pref[l - 1] = r - l + 1$$$
    Equating that it becomes $$$pref[r] - r = pref[l - 1] - l + 1$$$
    So at index i you need to count the indices $$$j <= i$$$ with $$$pref[i] - i == pref[j - 1] - j + 1$$$

    Code
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You can convert it to pref[r]-pref[l] = r-l

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Why dp[1]=1 ?Thanks

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Notice for all $$$i$$$ I increase $$$pref[i - 1] - i + 1$$$
        So for $$$i = 0$$$ $$$pref[i - 1] = 0$$$ and $$$pref[i - 1] - 0 + 1 = 0 - 0 + 1 = 1$$$
        So basically I increase for $$$i = 0$$$ at the beginning

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What was testcase 7 of problem D?

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

    test:

    4 2 2

    3 3 3 3

    4 4

    4 4

    your ans = 4 * 4 + 4 * 4 = 32

    correct ans = 3 * 4 + 3 * 4 + 3 * 4 + 3 * 4 = 48

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I got WA on test 7 too and couldnt figure out where I went wrong. But then I realized this test case gave me a WA-

    3 3 3 3 3 3 3 3 3 3 3 3

    The answer to this should be 36 but it gives me 27. I hope this might help.

»
4 years ago, # |
Rev. 3   Vote: I like it +3 Vote: I do not like it

Getting AC in D in like 10 mins but not getting any logic whatsoever for C hurts a lot.

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

    sum(l,r)=r-l+1

    sum(l,r)-(r-l+1)=0

    v[l]-1 + ... + v[r]-1 = 0

    so just subtract 1 from every element, and find all sub arrays with sum==0

»
4 years ago, # |
  Vote: I like it +4 Vote: I do not like it

I think C is more difficult than D...T^T.. How to solve C?

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

    Calculate the prefix sums p[i]. If p[i]-p[j] = i-j, then j+1..i is a good subarray. However, this equation can be rearranged to p[i]-i = p[j]-j. It suffices to find all values of p[i]-i and use some math to calculate the number of pairs.

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

      oh...Thanks for your kind comment.

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

    Here's a nice transformation:

    $$$ \begin{align} & \sum\limits_{i=l}^r a_i = r - l + 1 \\ \implies & \left( \sum\limits_{i=l}^r a_i \right) - (r - l + 1) = 0 \\ \implies & \left( \sum\limits_{i=l}^r a_i \right) - \left( \sum\limits_{i=l}^r 1 \right) = 0 \\ \implies & \sum\limits_{i=l}^r (a_i - 1) = 0 \end{align} $$$

    Becomes much easier to code because the goal sum doesn't change.

»
4 years ago, # |
  Vote: I like it +38 Vote: I do not like it

It was really good round, my nickname is lying :)

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

How to solve E? Can it be solved using set and priority_queue.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Implemented segment tree and got WA on test 4.

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

    Coordinate Compression + Segment Tree I saw other peoples' code also and they implemented it using set only but i don't know about it .

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

please anyone tell what's wrong in my solution in D (it's giving WA on test#7)

https://codeforces.com/contest/1398/submission/89953351

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

    test:

    4 2 2

    3 3 3 3

    4 4

    4 4

    your ans = 4 * 4 + 4 * 4 = 32

    correct ans = 3 * 4 + 3 * 4 + 3 * 4 + 3 * 4 = 48

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone help me out? I can't figure out why i failed test case 2 for problem c. I have created a consecutive sum array(i dont remember the actual name) and then checked for windows of all sizes.89943421

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    There are about 10^5 * 10^5 = 10^10 windows of all sizes. 10^10 things to do is too much for this time limit.

»
4 years ago, # |
Rev. 3   Vote: I like it +7 Vote: I do not like it

C is a standard problem often asked at AtCoder beginner rounds.[the idea is just to use prefix sums]

Edit: finally question reduces to find (i,j) pair such that j>i && pre[j]-pre[i]=j-i which can be easily solved using map.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain a bit elaborate please :)

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 4   Vote: I like it +17 Vote: I do not like it

      Let $$$sum_{i}$$$ be the sum of elements till position $$$i$$$.

      If you have two positions $$$i$$$ and $$$j$$$, $$$i \lt j$$$, if $$$sum_{i} - i = sum_{j} - j$$$, re-arranging the terms we see that $$$sum_{j} - sum_{i} = j - i$$$, i.e, the sum between their positions is clearly equal to the distance between them. So we just need to keep track of the count of elements with equal $$$sum_{i} - i$$$.

      Now we note that since between all pairs with the same $$$sum_{i} - i$$$ the sum of elements must be equal to the distance between them, if the cnt of $$$sum_{i} - i$$$ occurs $$$k$$$ times, we have $$$k - 1$$$ subarrays which are adjacent to each other from which we want to form a subarray. So there are $$$k - 1$$$ ways of choosing $$$1$$$ continous subarrays, $$$k - 2$$$ of $$$2$$$ continous subarrays and so on, which is just the sum of the first $$$k -1$$$ natural numbers, or $$$\frac{(k - 1) \times k}{2}$$$ possible subarrays.

      My submission: 89890437

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

    In educational rounds problem can be standard it is OK

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

    I thought of using prefix sums to get sum of range in O(1) but still for every subarray to consider it will be O(N*N), Can you help me in understanding this a bit?

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

      What you need is pre[r] — pre[l-1] = r — l + 1. You can rewrite this equation as pre[r] — r = pre[l-1] — (l-1), so for every good subarray, pre[i] — i is constant at the ends of it. Now you just have to make pairs

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

    Can you tell me what is the need for a[i] to be between 0 and 9? It confused me a lot and consumed a lot of my time.

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

      for higher values of a[i] algo still works.

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

        Yes, that 0 to 9 constraint created a lot of confusion for me.

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

      There is no need. I think it was just to throw you off... All that mattered was subtracting 1 from every element and then doing prefix sums, and checking for 0.

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

        Yes, that really threw me off. Wasted an hour on C ;_;

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

Any idea what is test case 2 of E or what is wrong with my idea?

My idea was as follows:

If after any operation we have $$$k$$$ lightning spells, then we need to keep track of the sum of the $$$k$$$ most powerful spells, while ensuring at max $$$k - 1$$$ of those are lightning spells (use a fire spell of power 0 as a dummy spell if needed). We can maintain the non-doubled spells using multisets in descending order and the doubled ones using multisets in ascending order for both types of spells. Change in sum can be tracked at the time of transistion of elements between these sets. Is the idea wrong or did I go wrong somewhere in implementation?

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Hello, what was the idea in problem D? I assumed that it's always optimal to choose the first two biggest sides of different collor and add the area to the answer. I am really curious to know the problem since I got wrong answer on test 6!

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    There is the case where some of the sides are equal.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      That is not a problem since a square is also considered rectangle as we can understand from the test samples!

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

    I used 3d dp to solve it. Sort all the r, g, b arrays.

    Now for state solve(i, j, k) => we can have 3 possibilities

    1. solve(i-1, j-1, k) + r[i]*g[j]
    2. solve(i, j-1, k-1) + g[j]*b[k]
    3. solve(i-1, j, k-1) + r[i]*b[k]

    Take max of all the three. You will have your answer.

    Here is the link to code using above approach https://codeforces.com/contest/1398/submission/89925922

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      This is a great idea, thank you. Probably my mistake was that I haven't found any counterexample during contest so I assumed that there is no need for backtraching stuff. (Or 3d dp)

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        using greedy is wrong because by doing so you might end up with a lesser number of rectangles ,which in turn might reduce the final output. For example lets say we have red array of size 20, green of size 20 and blue of size 190, using greedy u might use all the elements of red and green arrays first (resulting in just 20 rectangles) but there is a possibility of having 40 rectangles if u also choose elements from the blue array.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      do we need to sort the array if i apply this logic, 1. solve(i-1, j-1, k) + r[i]*g[j] 2. solve(i, j-1, k-1) + g[j]*b[k] 3. solve(i-1, j, k-1) + r[i]*b[k] 4. solve(i-1,j,k) 5. solve(i,j-1,k) 6. solve(i,j,k-1)

      89945848 mine logic without sorting, can u point out where am i going wrong

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

    3 2 1 3 4 5 5 6 7

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

    Check for this testcase

    2 2 2

    5 1

    5 1

    4 4

    Correct Output (DP) : 41

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why greedy does't works for D??

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

    Check out this test case:
    1 2 2
    7
    5 3
    6 2

    Greedy gives 52 as an answer, but the correct one is 53.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      cool. How did you come up with this counterexample?

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        during the contest, when I kept on getting WA on test 6 (and eventually never got it)

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

          I kept getting WA on test 6 too but I couldn't think of any counter example. So I believed that greedy algorithm should work. I spent 40 min staring at my code trying to find stupid implementation mistake xD.

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

      A simpler one :

      1 1 2

      5

      4

      3 2

      if we take 5 and 4 we can't include (3 and 2).

      so optimal answer is 5*3+4*2

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

    I tried greedy too but failed miserably.

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

    My Greedy solution for D was taking all the combination of 3 types of triangle. Since there can be 3 types of triangle, there are 200*200*200 combinations to choose from. Each combination tells how many triangles I will make of each type. I only worked with the valid combinations so that I don't get TLE. Then I am greedily taking the maximum product and not taking any more triangles of a type than what my combination says. Can anyone tell me why it does not work?

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

      tryed the same dude, now i know its wrong on 4 2 2 3 3 3 3 4 4 4 4

      Correct output : 48 We got : 32

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

        My solution is giving the correct output 48. Still don't why it won't work. Here's my last submission 89977686

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What's the test 4 for problem E? I was using two sum segment tree one for lightning spells with twice the value of d and another for fire spell for value d. Also tracked minimum of lightning spells and maximum of fire spells by set and then computed the answer. Resulting WA on test 4.
89951160
In my submission, vectors are defined as sum -> lightning, sum2 -> fireball, v -> lightning, v2 -> fireball, st1 -> lightning, st2 -> fireball

»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Really nice Problemset :-)

»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

In E I had to query the sum of the k largest elements. Is there a data structure that supports this?

I used a messy combination of segment and fenwick trees and the fact that we know all elements before.

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

    You can do it with just two sets. First set will contain k largest elements, and second set all other elements.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you please explain the approach.

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

        Since k can change by at most one, you will need to remove\add only 1 element. Also after inserting element you need to swap elements if minimum of first set is smaller than maximum of second set.

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

    Treap can easily handle that.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why k largest elements? Isn't it 2 * (sum of lightning) + sum of fire + maxfire — minlightning and if there is no lightning then simply sum of fire

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      My approach definitely wasn't the simplest

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I see, I asked why my one is wrong? I am getting WA on test 4 implementing segment tree using this idea

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Sometimes it is optimal to cast lightning, fire, lightning, fire, etc.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Is it so? Consider the case where you have 3 lightning spell with damage 1,2,3 and 3 fire spell with damage 10,20,30. I believe the maximum damage should be 126 but your formula evaluates to 101.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you can do that offline compressing all values and using segment tree.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Policy based data structures can also work (but I ended up getting WA for some reason)

»
4 years ago, # |
  Vote: I like it +22 Vote: I do not like it

educational.jpg

»
4 years ago, # |
Rev. 2   Vote: I like it -6 Vote: I do not like it

Ciao Rating !

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This game really pisses me off

»
4 years ago, # |
  Vote: I like it +7 Vote: I do not like it

In question D, why do we have to sort the arrays before applying DP, i code it without sorting but it was giving wrong ans but after sorting with same logic it was giving right ans?

»
4 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Too sad, I can't implement E in time (in 30 mins) :((. How can I improve my coding speed

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

About problem C: Let's consider s[l], s[l+1], .., s[r] so if s[l]+s[l+1]+..+s[r] = r- l + 1 then s[l..r] is good s[l]+s[l+1]+..+s[r] = 1 + 1 + 1 + .. + 1 (r — l + 1) s[l] — 1 + s[l+1] — 1 + ... = 0 so the problem switches to finding the number of subarr (after decreasing by 1 each element) which has sum = 0 (can be easily done by map)

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

It seems testcases are weak on problem E, this slow solution passes. Go ahead and hack it! 89956850

»
4 years ago, # |
  Vote: I like it +27 Vote: I do not like it

Here's a simple alternate for C: Decrease all the values in the array by 1, and now you need to find the number of subarrays which has sum equal to 0.

Btw, how to solve F?

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

    Let's try to find the answer for each len $$$l$$$.

    • Let $$$f(pos, len)$$$ = maximum possible number of sets that could have already finished considering $$$s[pos::]$$$ and number of contiguous rounds required is $$$len$$$.

    • Now, If $$$s[pos], s[pos+1] ...s[pos+len-1]$$$ doesn't contains both $$$1$$$ and $$$0$$$ then $$$f(pos,len) = 1 + f(pos+len, len)$$$.

    • Otherwise, find the minimum index $$$idx$$$ in $$$(pos, pos+len-1)$$$ such that $$$s[idx], s[idx+1]..s[pos+len]$$$ doesn't contains both 1 and $$$0$$$ and then $$$f(pos, len) = f(idx, len)$$$.

    The time complexity of the solution will be $$$O(N+N/2+N/3...) = O(Nlog(N)).$$$

    • The solution was simple but I was not able to prove that time complexity is $$$O(N(log(N))$$$ but the the basic proof is that lets in one iteration you are going from $$$pos$$$ to $$$idx1$$$ where $$$idx1$$$ can be $$$pos+1$$$ but in the next iteration you will definitely jump from $$$idx1$$$ to $$$idx2$$$ such that $$$idx2 >= pos + len$$$ thus at max total $$$2 * (N/len)$$$ iterations will be there for a single $$$len$$$.
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How do you perform step 3?

      I use Segment Tree, so the total complexity is O(n*log(n)^2), and my submission runs in ~1.9s, nearly TLE.

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

        For every index, Calculate the previous index such that it has one and also the previous index such that it has zero.

        • $$$if(s[pos+len]== ?)idx = min(prev_zero[pos+len], prev_one[pos+len]) +1$$$

        • $$$if(s[pos+len]==1)idx = prev_zero[pos+len] + 1$$$

        • $$$if(s[pos+len]==0)idx = prev_one[pos+len] + 1$$$

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you elaborate more on this?

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

      Short proof:

      $$$ \begin{align} & \sum\limits_{i=l}^r a_i = r - l + 1 \\ \implies & \left( \sum\limits_{i=l}^r a_i \right) - (r - l + 1) = 0 \\ \implies & \left( \sum\limits_{i=l}^r a_i \right) - \left( \sum\limits_{i=l}^r 1 \right) = 0 \\ \implies & \sum\limits_{i=l}^r (a_i - 1) = 0 \end{align} $$$
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I understood this proof but why we use frequency to calculate the total answer ?

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          The goal is to find all possible $$$l$$$ s for our current $$$r$$$.

          Let $$$prefix(i) = A[1] + A[2] + ... + A[i]$$$. Suppose our current prefix sum $$$prefix(r) = x$$$. Since $$$prefix(r) - prefix(l-1) = A[l] + A[l+1] + ... + A[r-1] + A[r]$$$, then for all $$$j < r$$$ such that $$$prefix(j) = x$$$, we know $$$prefix(r) - prefix(j) = 0$$$. We keep the frequency of every $$$prefix(j)$$$ to search for how many of them are equal to $$$x$$$.

          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Thanks very much . i understood this approach very will.. but in general how can i know like these proofs by myself in the contest !? any suggestions to improve my skills ?

            • »
              »
              »
              »
              »
              »
              »
              4 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              The trick with using prefix sums to calculate subarray sums is very common because it has so many uses. This particular problem is one that comes up every so often. You just need to keep practicing so that you'll learn these new techniques and remember them for future contests :)

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

    think of the brute force solution then optimize it, you can find the answer for any x in O(n) like this

    pseudocode

    this obviously takes $$$\mathcal{O}(N^2)$$$ but we can make it $$$\mathcal{O}(N * log(N))$$$, first for each i compute X[i] = biggest x such that $$$[i, i + x - 1]$$$ doesn't contain both 1s and 0, this can be done in O(n log n) using binary search and prefix sums, now in the loop above replace i += 1 by i = find(i, x) where find(i, x) returns the first j > i and X[j] >= x, this can be done using disjoint-set (initialize the parent[i] as first j > i with X[j] > X[i]) and modify the find function slightly

»
4 years ago, # |
  Vote: I like it +59 Vote: I do not like it

could E BE more boring ?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Well,I think problem E is fine because I consolidated the segment tree from it._(:з」∠)_

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

i see the answer for "C. Good Subarrays" in this content but i still can't understand it can any one help me?

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

    if you just subtract 1 from all the elements, you will have little different array.

    but now, you need to find all the subarrays with count 0.

    Why?

    https://stackoverflow.com/questions/26532723/counting-all-contiguous-sub-arrays-given-sum-zero

    here is how to deal with this problem from this perspective

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

    $$$sum_r-sum_l=r-l \implies sum_r-r=sum_l-l$$$

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

W

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem D why is it important to sort. . . . My thinking, If I'm using exhaustive search using dp, it should give the optimal answer, int this case max area, without even sorting. Please clarify this for me. Thanks

  • »
    »
    4 years ago, # ^ |
    Rev. 3   Vote: I like it +5 Vote: I do not like it

    Let's say we have two pairs of one type with lengths $$$a_1, a_2 (a_1 \le a_2)$$$, and two pairs of another type with lengths $$$b_1, b_2 (b_1 \le b_2)$$$, then it's optimal to create a rectangle of sides $$$a_2, b_2$$$ and a rectangle $$$a_1,b_1$$$. This is easy to prove.

    So, after sorting once we pair $$$i$$$ on first array with $$$j$$$ on second array, we'll never pair $$$k < i$$$ on first array with $$$z > j$$$ on second array. So we keep a classic DP.

    $$$dp[i][j][j]: $$$max total area using pairs till $$$i$$$ on first array, till $$$j$$$ on second array and till $$$k$$$ on third array.

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

    If I'm using exhaustive search using dp

    No we are not doing exhaustive search , if we are pairing one from red and one from green , they must be of highest length in there category .

    Did you asked yourself how transition will take place (i.e how we will find $$$dp[i][j][k]$$$ with the help of some lower $$$i,j,k$$$) ?

    $$$dp[i][j][k] = max(dp[i-1][j-1][k]+A_i*A_j,dp[i][j-1][k-1]+A_j*A_k,dp[i-1][j][k-1]+A_i+A_k)$$$

    while taking $$$A_i*A_j$$$ , we will take the maximum ones and thus we need to sort.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please provide a test case where Greedy approach in problem D fails

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve $$$G$$$ without bitsets? Faster than $$$O(X^2/32)$$$

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

    fft

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Nice! Karatsuba also works.

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can you please explain your complete approach ?...

        I know that if we have (a[i] — a[j] == t) for some i,j(i > j) and t then we can use an approach similar to sieve and solve... but not getting the fact what is the exact purpose of using fft ?

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          FFT can be used to get these values $$$t$$$. For this we should calculate $$$(x^{a_0} + x^{a_1} + ... + x^{a_N})*(x^{-a_0} + x^{-a_1} + ... + x^{-a_N})$$$. If coefficient at $$$x^{t}$$$ $$$!=0$$$, then there are exist $$$i$$$ and $$$j$$$ such that $$$a[i]-a[j]==t$$$.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How to solve G with bitset?

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Problem C becomes so beautiful after realizing its logic.

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

    One more solution to solve such types of problems.

    Let $$$pref[i] = s[1] + s[2] ... + s[i]$$$

    Thus required subarrays $$$(s[L...R])$$$ will follow this property,

    • $$$pref[R] - pref[L-1] = R-L+1$$$

    • $$$pref[R] - R = pref[L-1] - (L-1)$$$

    Or, Basically you can choose any two index such that their $$$pref[i]-i$$$ is samefor both of them. Now, it's basic $$$O(N)$$$ task, using $$$C(freq, 2)$$$ for every frequency of $$$pref[i]-i$$$.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I have submitted 2 identical solutions for problem C. Solution A: 89960181 Solution B: 89960214 The only difference between the two is on line 22: In one approach I use an integer to represent the index while in the other I use a long long. I also use in both cases a long long to represent an index in line 53.

Why does one solution pass while the other doesn't? I've already read many forums regarding the indexing on arrays in C++. Nowhere did I found that it says that a long long will cause problems when indexing with it.

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

    You didn't initialize variable out 89961488

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thnx dude I mean I broke my head to figure it out. It is weird thought the fact that 89960214 gets AC. I mean I do not initialize out and because I used an integer for indexing it works for some reason XD

»
4 years ago, # |
  Vote: I like it -18 Vote: I do not like it

O(n) solution of C with HashMap 89943214

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

why the greedy solution of D — "pick two largest pair every time" fails?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Counterexample:

    R: 3 4 5

    G: 5 6

    B: 7

    If you take 2 biggest elements of different colours you'll end up with: 7 * 6 + 5 * 5 = 67

    Though the optimal split is: 7 * 5 + 6 * 4 + 5 * 3 = 35 + 24 + 15 = 74

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    9 9
    10
    10
    

    -> That greedy pairs the both 10 instead of 9,10 + 9,10.

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

      spooky mah boi , why you oscillate between colors so much ?

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

        The crazy problem setters create weird problems ;)

        No seriously, one limitation for me is the ability to concentrate, I am sometimes not able to implement simple tasks, like todays C, even if I know how it works.

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          When you fell from CM to specialist, I just thought that you are trying to get a record of biggest rating change.
          Yeah, problem setters set such problems that if you get some WA, debugging would take a lot of time. This affects me too.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why is my approach for C failing? My approach: Every good subarray should start with some index, so i'll brute force for every index checking it for lengths (1,2,...9) . Time complexity O(9*n). It failed for many, example => s = "11140000000090000000002111" , correct ans = 37 , my ans = 29

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Consider an array full of 1's. In your solution you ignore good subarrays of length more than 9, which is not correct

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

in c i storedd arr[i]-1 for each array and counted the no of subarrays with sum 0 balancing excess with shortage!

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

why my code for D is giving TLE. It is using same approach as DP solution.

code
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Close enough, but learn dp, you'll see why it fails.

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

      i have tried to do DP problems but most of the times i fail to think of a DP solution

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think rgb() is called for same vectors several times. It's same as when you find the nth element of Fibonacci sequence by iterative method or recursive method.

    The other thing is that whenever you call rgb() it will copy all data from current vector to the next function but in DP no.

    (Sorry for my bad English)

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      ok i will try to implement DP solution then. my bad i couldn't think of it during contest(sad emoji)

      Spoiler
»
4 years ago, # |
  Vote: I like it +31 Vote: I do not like it

My screencast, if you want to enjoy my fingers suffering from typing so much (video solutions for A-E included)

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

Why are the hacks shown on the hacking page in reverse order, like the most recent hack is at the end?

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

If anyone has used memoization for D pls do share your code.It would be a great help for a beginner like me as i am learning dp . Thanks in advance

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Got WA on Test 6 in Question D. The 6th test case given is not intuitive.Can anyone help me out with a intuitive test case similar to the test which is used in testing.My solution is a greedy approach, but not a general one.So test cases such as the below test case will result in correct answer.This is my solution 89953296.

4 2 2

3 3 3 3

4 4

4 4

This test case results in correct answer for my solution.

  • »
    »
    4 years ago, # ^ |
    Rev. 3   Vote: I like it +4 Vote: I do not like it

    3 3 3

    2 8 5

    1 10 5

    9 9 3

    Correct answer : 10*9 + 8*9 + 5*5 + 2*3 = 193

    Your answer : 182

»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I guess people are making fake ids just to hack those submissions afterwards. Deliberately a stupid if case is added to be hacked afterwards XD.

89940459

The hacked guy likes 78788 a lot I guess. One more of his solutions from another contest using his fake id Noob_is_back got hacked. See this 87193319 and you'll find 78788 again in the code. The hackers are still grey :)

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

My hack has been on "waiting" since this morning. It's not just when I'm logged in, it shows up like that on an incognito tab as well.

»
4 years ago, # |
  Vote: I like it +16 Vote: I do not like it

In the meantime before editorial is published and for those interested, here is the 3Blue1Brown styled visual editorial for Problem C, visualizing tmwilliamlin168's code (89883985). I have also given a somewhat formal proof before visualizing 1st input of Test Case #5

Link to visual editorial here

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how to check the time it takes for the submission when hacking?

»
4 years ago, # |
Rev. 2   Vote: I like it -8 Vote: I do not like it

I love problem D very much!!

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

    How to solve E?

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

      I use the line segment tree (weighted segment tree). In fact, it is easy to find that the answer to problem E each line:ans = the sum of the largest number in the first K + the sum of all the numbers (here K refers to how many numbers can be doubled)

      Then we read all the values first, sort them (discretize them), and then read the input of the problem again (which has been changed by array storage in advance)

      We maintain the weighted line segment tree every time, that is, we ask the sum of the top k numbers in the 1-n interval every time. For example, to find the sum of the top 4 numbers, I will first ask whether the number of the right subtree (because the number stored on the right is larger than the number on the left) is less than 4. If so, enter it directly and return the sum of the top 4 numbers under the right subtree. If not, directly Select the sum of the prior numbers of the right subtree and add the sum of the first k = 4-num [RS] numbers under the left subtree (Num [RS] represents the first number of the right subtree),and then return it.

      In short, the answer is to ask the sum of the top k numbers on the line segment tree and add the values of all the current numbers

      (PS: but note that if the minimum value of all the numbers that can be doubled is greater than the maximum value of the number that can't be doubled, we can't simply choose the top k, but we should choose the top K + 1 and subtract the minimum value of the double number, because one can't double itself.)

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Maybe my expression is not clear, but you can find ideas from it. It must be feasible because I passed after the contest.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

any news about the tutorial?

»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

why this code 89922404 for problem C won't get TLE

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The first three lines makes the code really fast.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why are Educational Rounds always so late with editorials?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Because of the 12 hour open hacking phase, I guess.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me in D. I used a 3d dp approach, which finds the maximum value using 6 cases. However, it failed on test 5. Here is the failed submission, while here is the one that passes. What does sorting do?

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

    It's always optimal to chose pairs with the maximum product. So we sort those three lists in decreasing order and take pairs from top of them. But when we have multiple options for pairs with the maximum product we don't know which one we should take without looking at the next values and that's why we do dp.

    $$$dp_{i,j,k} = max(dp_{i,j+1,k+1},dp_{i+1,j+1,k},dp_{i+1,j,k+1})$$$ = maximum area we can achieve when we have already taken first $$$i$$$, $$$j$$$ and $$$k$$$ values of the first, second and third array (according to $$$0$$$ based indexing).

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

      I found your explanation easy to understand, can you tell what does dp[i] [j] [k] stands for i.e what is the meaning of each cell of dp, can you please elaborate it more.

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        $$$dp_{i,j,k}$$$ stands for the state where we have already used first $$$i$$$ values of first array, first $$$j$$$ values of second array and first $$$k$$$ values of third array.
        The value of $$$dp_{i,j,k}$$$ is the maximum area we can obtain using remaining values of these three arrays in this situation.

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

If anyone need Explanation & implementation(not a video tutorial) for C Here

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Has the system testing finished? Its been more than 12 hrs right? Also editorial please...

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think a coincidence has occurred. I write every problem's code by myself. Before Each code I wrote my name and time.

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

This wasn't a part of the problem, but I was wondering what is the maximum number of rectangles that can be formed for problem D?

My approach

Please correct me if I am wrong.

»
4 years ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

Is there a bug in the rating change of this round? Everyone seems to be one step down to their original rank

Edit : it is correct now

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

in D ,why do we have to sort the values,even though we are using dp?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Because it is not subset dp like knapsack, we are just using dp on the number of elements chosen for each color,and we will chose that greedily, its always to better to chose highest two elements, but the choice of elements could restrict choice of other elements, hence we are using dp.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

waiting for editorial..

»
4 years ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

Dear Codeforces administrators and contest organizers:

Just now, I received the following message:

Your solution 89920639 for the problem 1398D significantly coincides with solutions yhf_2015/89920639, zstuyyyycccbbb/89946825, Gghost/89949025.

First of all, I promise that the game was completed by myself alone. I did not listen to anyone else's thoughts during the game, nor did I reveal my thoughts to anyone. I have no intersection with the two who gave similar codes.

Secondly, my thinking about problem D is straightforward and simple. I think many people may have the same thinking. With a huge base, this may really be an accident.

I was very surprised when this happened, and I don't know what kind of evidence I need to provide to prove what I said above. (If you need me to provide any evidence, I will fully cooperate.) After completing the problem, I immediately carried out the research of problem E and wrote the code. Unfortunately, due to some errors, it was not possible within the game time Used.

Regarding my IP address, the network provided by my broadband network operator cannot access your site smoothly. I used a VPN system to compete through the lines of other operators. I don't know whether this will affect your judgment.

The above English uses machine translation.

»
4 years ago, # |
Rev. 2   Vote: I like it +26 Vote: I do not like it
»
4 years ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

Nice contest with great set of questions worthy attending it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please explain why do we use FFT to get whether a value (a[i] — a[j] == t) for some i,j and t is possible or not ?

Asking this because if we can get all possible values of t from the array a.. then we can simply use sieve and solve but i am not getting the fact why do we use fft ?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Brute force is $$$O(n^2)$$$, which is too slow.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Nice trick Haha, I love FFT (but I don't know how to implement :))

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can Anyone please explain solution of 1398E - Two Types of Spells .There is no editorial and i cant think of any solution. or atleast give hint about data structure to use.

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

    Segment tree and multiset are sufficient. assume there are L lightning spells, you just need to know the first L largest power of magic spells ... and some annoying implementation.

    since all the powers are positive integers, you will always put the smallest lightning spell in the first position. then if there exists at least one fire spell, you can get L spells doubled. else you can only get L-1 spells doubled(since the last spell will be lightning spell).

    sorry for poor English, I'm trying to improve it by answering questions.

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

I get it in Problem D we have to first sort before applying dp, but I sorted all three array in descending order ( just applying the logic that since we need bigger ones first) but I got WA.
Can someone please explain the difference ?
AC. WA. Only difference between two is the way of sorting.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Editorial please, it seems to be taking forever.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone with editorials for this contest .

»
4 years ago, # |
Rev. 2   Vote: I like it +4 Vote: I do not like it

hacks of rafaelka

:|

UPD : It is deleted now.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

How come I wasn't able to hack anyone during the hacking phase? Did anyone else experience this? I think many wrong solutions got AC in this contest.

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

    after people where hacking the contest the writer added corner test cases for example 89928441 was been accepted with only 2 test but after hacking the test upgraded for example 89896719

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell how to solve problem C ? I saw youtube tutorials for this but couldn't get the logic.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone suggest me questions similar to problem C

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

it was the first time I hacked someone's solution and coming out as one of the best hackers !! I feel happy :) Thank You Codeforces