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

Hello Codeforces!

On Jun/05/2019 17:35 (Moscow time) Educational Codeforces Round 66 (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 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 participants!

UPD:

Our friends at Harbour.Space also have a message for you:

Codeforces! What is the next step in your development?

We understand all about doing things by yourself — after all, we are a startup university, and our student body is exceptional in part because of it’s made up of people who didn’t wait for anyone to show them the way.

If this is you, you belong at Harbour.Space. The purpose of our University is to create a global community of these kinds of people, regardless of age or nationality, because when you’re working by yourself, you can change for the better, but when you work with others, you can change the world.

If you believe you have what it takes, we want you!

The curriculum is part of what makes the modules so special, and the other half? Our outstanding teachers who are leaders in their own respective industries.

Our scholarships are set in such a way that doesn’t require additional applications — we believe in merit and potential, and so what you put in your application to the university will be our criteria.

You could be just the diamond we’re looking for, but you’ll never know unless you apply!

APPLY NOW→

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 mango_lassi 6 145
2 E869120 6 148
3 244mhq 6 154
4 Egor.Lifar 6 154
5 Umi 6 157

Congratulations to the best hackers:

Rank Competitor Hack Count
1 Radewoosh 97:-19
2 test_hack 56:-37
3 alvinvaja 30:-10
4 AryaKnight 48:-48
5 nikolapesic2802 30:-14
779 successful hacks and 1077 unsuccessful hacks were made in total!

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

Problem Competitor Penalty
A Geothermal 0:01
B mango_lassi 0:05
C nuip 0:07
D Yushen 0:04
E Sehnsucht 0:20
F ---------- 0:05
G LgndryGrandmasturbator 0:47

UPD: The editorial is out

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

| Write comment?
»
5 years ago, # |
Rev. 2   Vote: I like it -6 Vote: I do not like it

[deleted]

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

Thanks for the consecutive contests! Wish that the problem statements will be neat and clean and short as the previous one. Eid Mubarak everyone!

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

»
5 years ago, # |
  Vote: I like it -42 Vote: I do not like it

Comment "Is it Rated?" if you want to gain contribution points! (In the negative direction)

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

    Let me do this job for you.

    Is is Rated (for Div1)?
    Ans seems Yes.

    MikeMirzayanov awoo Please fix it.
    Everyone is registered as "Contestants".
    Mark me and others as "out of competition".

    Div1 in Comp.

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

      No, it is not rated for you. It is rated only for those who are below the master

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

      It is not a bug. In Educational Rounds no one is out of contest everyone can compete officially but it is only rated for Div2. And after contest in the Final Standings there are options (div1,div2) to see standings

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

thank u, pik misha!!!!!!!!!!!!!!!!! i love you

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

I never really understood the concept of Educational Rounds. Don't we learn something new from every contest? Why exactly term it Educational?

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

    LoOOoOOooOooLoOOOoooOOOoOOLoOoOooOoooooOOL. ROFL. LMAO.
    Problems at usual contests: "use a segment tree with some trciky operations and tricky queries"
    Problems at educationals: "use a trivial segment tree, (yes) and queries are in the form of $$$[p_i,i]$$$
    didn't you feel that difference?"

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

      Finally found the person who uses the id LanceTheDragonTrainer.

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

        no, he uses id riela

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

          LoOOoOOooOooLoOOOoooOOOoOOLoOoOooOoooooOOL. ROFL. LMAO.

          marymarine is no longer my alt, we disbanded because he doesnt like twice.

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

      Yup, that makes sense. Thanks!

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

      And for us mortals, Educational rounds are ironically harder than the normal rounds, and the editorial comes the same way for both educational and normal rounds, so not even sure what's the point of calling it "educational".

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

        it is your fault if you fail to solve problems
        once more:
        edu rounds -> hard problems with classical ideas
        usual rounds -> hard tricky problems

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

          Yes, I'm just saying how ironic it is for a round that calls itself "educational" is as educational as any other round and it manages to make itself harder than an average round.

          I just don't get it, I literally don't get why it's called "educational", it has no special property what so ever that would make it educational.

          I'm talking about ABC tasks, I'm not qualified enough to talk about the difficulty of DEF...

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

            Yes, DEF are actually educational

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

              If educationals DEF are so much easier than normal round DEF then why does DEF get solved the same/less than in a normal round ? This EDU alone has only like 20 people who solved DEF, maybe 50 that solved DE, and the rest are D

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

                i didn't say they are easier, i meant they are with classic ideas

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

                The purpose of contests is for people to solve problems and learn from them I think.

                It doesn't matter if its name was "Educational" or something. If you are good you can solve problem. If you are not you need to learn more, tutorials is a good point.

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

                  I'm fine with the rounds, the more the merrier, just saying that EDU rounds are worse than normal rounds imo.

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

                  I enjoyed all of the problems. I mean we aren't allow to choose our life condition so we need to prepare for the worst.

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

                  I enjoyed the problems of this EDU as well, I'm talking about the previous EDU.

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

                  Yes, I'm talking about every problem :)

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

awoo is a boy or a girl?

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

yes
Konstantin Mertsalov is a nice man , we discussed some math problems with him through skype

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

Eid Mubarak to all Programmer.

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

»
5 years ago, # |
  Vote: I like it -70 Vote: I do not like it

First question has wrong limits on K!! Because of this I lost valuable time

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

    I wonder why im getting downvotes...am I wrong?

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

      what is wrong with the limits?

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

        k = 1 in one test case but question says k>=2

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

          Can you see the test case? How do you know that?

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

            I added the check for k == 1 and it passed

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

              Is that the only difference in your solutions?

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

              If you want to be sure add assert(k >= 2) right after your read input and submit again! If you are right you should get a RuntimeError verdict.

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

              You changed types from int to long long

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

          I don't think it's true. My accepted submission would loop forever on $$$K = 1$$$.

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

      Yes.

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

      because you wrote very trashy comment.

      you are just a pupil after 4 years and you said codeforces contest has a problem ??

      how did you decide to write this comment ?

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

Thanks for the round.

»
5 years ago, # |
  Vote: I like it -28 Vote: I do not like it

The worst B problem I have ever solved

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

    There is always "A worse" in CF...

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

    why?In my opinion this problem is cool.

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

      IDK, maybe im stupid, but i couldn`t find whats wrong with my code

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

      But tricky. Swapping C and B would be better.

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

      How did you solve it? I got WA in test 5.

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

        Think of following test case 10^5/2-1 nested for loops with add.

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

          https://codeforces.me/contest/1175/submission/55150517 what's wrong with this? please help me in debugging.

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          for 100
          for 100
          ....
          ....
          ....
          add
          end
          end
          ...
          ...
          

          Like this?

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

            Yes. People who are storing value to add will result in overflow for long long.

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

              I didn't do that but still I'm getting wrong answer on test case 8. Please help.

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

                same here, can't figure out why am I getting WA on TC 8

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

                even got WA on tc8. I wasn't checking th condition when the answer was exactly 2^32.

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

            Can you tell why this code gives WA on test case 9?

            55158372

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

              I guess you are using the accumulated sum and multiplying it for each loop. Check for input : 6 for 3 add end for 3 add end // output : 12 // should be : 6

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

I really liked D there's a relation between each possibility but I don't know how this is going to help :/ how did you solve it

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

    Expand the summation using prefix sums everywhere

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

      Is this correct k*ps[n] — (sum of small k-1 smallest prefix sum)

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

        Yeah

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

          Too bad I cannot implement it. Though this problem looks like some DP optimization which I am not familiar with and started searching articles for it.

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

            don't forget to exclude ps[n] though, while finding k-1 smallest prefix sums.

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

Problem B!! :'( made it the worst contest I gave on codeforces :/ and why cant we use python3 signal in codes :'/

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

    Problem B is just a simple stack based problem of evaluating parenthesized expressions.

    And as for signal, check the documentation. signal.alarm is unix only

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

I'm so sorry of that. I just wanted to laugh and maybe some upvotes. I didn't think reminding some old joke would be that annoying. Maybe this cause more downvote, but I want to talk some more words. I'm just a kid, please just don't make me cry. :( Last day I started commenting and I got contribution +3. But now it is going down to -4. I'm so depressed by now. I promise I won't write something idiot more. I'm sorry again. Can you help me get my contribution up to 0 again?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +44 Vote: I do not like it
    throw new JokeTooOldException();
    
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      Just a reminder. :D

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

        Which site you use to upload photos there's alot of memes in my mind to post XD

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

          I just got this from another comment on CF

          But I found a site to upload.

          After that I disabled my antivirus and then something special happened to my desktop.(the backgroung and resolution changed suddenly)

          Be Carefull. Btw do you know how to get upvotes?

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

            Don't post all the jokes you think about because some of them aren't that funny
            the more unique and unexpected the joke is the more upvotes it will get also the right timing plays a role
            . Btw I did not understand what does the antivirus has to do with uploading a photo.

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

              After uploading I wanted to send it here. I copied the URL and posted it. Then the antivirus blocked it. Because I wasn't sure that it is sent correctly. I turned off the antivirus. And after a few moments that happened. It was my mistake to turn off the antivirus.

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

    D was quite solvable

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

    C is extremely hard to me. lol In my opinion D is easier than C. :)

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

      Agree. 38 minutes spent on C, mostly staring at piece of paper. 30 minutes for D, no idea why it took so long.

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

How to solve E?

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

    Create sparse table such that nxt[i][j] is the maximum index sucht that [i, nxt[i][j] ] can be covered using atmost $$$2^j$$$ segments.

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

      Can be solved using binary lifting (this is the same, but actually easier to code).

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

        Don't we call binary lifting on arrays as sparse table?

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

      how do u prove this?

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

      During the contest time I was thinking if I can create a sqrt decomposition solution.
      Couldn't find one. Can you think of one? ( I am pretty sure that the time limit can be tight)

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

        I have one in mind. For all precompute the ans for all [i, j] such that $$$j - i < \sqrt{n}$$$. Then the queries for $$$y - x < \sqrt{n}$$$ can be answered in O(1) and for others in $$$O(\sqrt(n))$$$

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

          Yes, I had similar in mind.
          But I realized, it can be troublesome when an interval ( say [li, ri]) lies inside 2 blocks (say, [√n+1, 2*√n] call it block1 and [2*√n+1, 3*√n] call it block2).
          Because, that time when we loop through block1 and block2, I am not sure how to combine their answers. Are you able to feel the difficulty? Or do you have a better approach to it?

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

      Would you like to elaborate more on how do you use the sparse table to find the minimum number of segments?

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

      I learnt about sparse table and successfully solved this problem.
      Thanks to you <3

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

How to solve D?

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

    Let 1, x2, x3,...,n be index where new subarray starts. Then answer is f(1)×1 + (f(x2)-f(1))×2+....+(f(n)-f(x_k-2))×k. Open it. f(i) is prefix sum till i'th element.

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

    You can extend this proof to general k segments

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

can't we solve C using the ternary search?

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

    No you can't 55147246

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

      Why go for ternary when you can do with binary?


      Ref: 55155030
      I used binary search on answer over f(x). Now if f(x) exists, it means that x must be equal array[i]+f(x) or arr[i]-f(x). Iterate over the array to find such possible 'i' where you get at least k-1 elements in the array which are less than or equal to f(x) (using upper bound). If you find any such 'i' then modify r, else modify l.
      f(x) = (l+r)/2 i.e. mid
      Hope it helps! :)
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No. because the f(x) might be something like sin(x) (just for imagination!). suppose there are k + 1 points close to each other, then a huge gap then again k + 1 points close to each other, then a huge gap and so on...

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

      Ok. to clarify my idea let's see this test case

      4 0
      10 20 30 40
      

      k = 0 so $$$f_k(x)$$$ means the distance of the closest point to x for each integer x. the graph of $$$f_k(x)$$$ will be like this :

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

How to solve problem C?

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

    Average of points which have k-1 given integers between them.

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

      Could you please explain the correctness of this approach?

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

        If the solution you get from that is not correct, that means you could move left or right. If you move left, you will be further away from the point on the right, which means you are no longer at the minimum. If you move right, you will be further away from the point on the left, which means you are no longer at the minimum.

        So, you just want to find the 2 given points that have k-1 given points between them, and the average of those 2 points will be your answer.

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

    My solution lets find minimal distance using binary search. Suppose the answer is X.

    Then, our answer point should be in the distance X for at least k points.

    Second part is just easy to check if there is a point where k segment intersect [a_i — X, a_i + X].

    Complexity O(n * log^2)

    But can be easily implemented in O(n * log)

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

      why are you using binary search? if you already knows the greedy approach to check the answer, you can just do it without guessing the answers ... just get the mininum distance that a X point have the elements. The X with this minimum distance is the answer.

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

        The problem that I don't know the minimum distance, I use binary search to find it.

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

What is the proof of correctness of C?

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

    Have you solved it? Well, supose X is outside the range we are right now. Then its better to put it inside the range, to decrease the distances of the k consecutives elements. The ans is the min middle point of all ranges with lenght K. (the best point is the middle one because it gives us the least k minimum differences).

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

when will tutorial soln for educational contest will come

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

How to solve D?

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

How to solve G?

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

    D̶&̶C̶ ̶D̶P̶ ̶o̶p̶t̶i̶m̶i̶z̶a̶t̶i̶o̶n̶ I'm actually not sure(there is no editorial for task, so I wrote what i remembered it was), thx for pointing it out

    By the way, the problem is not original, statement is only in romanian though

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

    I have an $$$O(NKlog)$$$ solution for G but still havent been able to implement it until now which ruins my rating as always :)

    So we lets denote $$$MAX(L, R)$$$ be the maximum value in the subarray $$$[L, R]$$$, and $$$F(i, j)$$$ as the minimum weight of splitting first $$$i$$$ elements to $$$k$$$ subsegments.

    By that, we have $$$F(i, j) = min(F(x, j - 1) + MAX(x, i) * (x - i + 1)))$$$ for every $$$x ≤ i$$$.

    Lets have an observation:

    We can separate $$$(i - x + 1) * MAX(x, i)$$$ to $$$(i - 1) * MAX(x, i) - x * MAX(x, i)$$$. As always, we will have some data structre like Convex Hull or Lichao Tree to query for the minimum $$$w* MAX(x, i) - x * MAX(x, i) + F(x, j - 1)$$$ for $$$w = i - 1$$$.

    Now, normally, one will always think of idea of iterating elements from left to right, maintaining the stack of maximum elements and trying to do something about deleting and pushing elements to that stack. As every time $$$MAX(x, i)$$$ changes, we will need to reset our Convex Hull or Lichao Tree over again.

    Lets fix $$$i$$$. Now our stack will represent the changes of the $$$MAX(x, i)$$$ if we iterates $$$x$$$ from $$$i$$$ to the left. And for every fixed $$$k$$$, the elements that satisfy $$$MAX(x, i) = k$$$ lies on a continuous subarray. So my main idea is for each $$$k$$$, i will first find the $$$x$$$ that minimizes $$$-x * k + F(x, j - 1)$$$ before we actually inserting it to our Lichao/Convex Hull.

    To do this, you can think of an segment tree which each of its node has a Convex Hull or Lichao tree to take this query. And we will use Convex Hull in this case. If we notice that every time we try to change the $$$MAX$$$ of some subarray by deleting some elements from our stack, their $$$MAX$$$ only gets bigger and bigger. So if we use Convex Hull, we can actually handle queries in $$$O(1)$$$ by using the pointer trick instead of binary searching.

    Now once we get the best $$$x$$$ for our $$$k$$$, we will insert a line $$$(k, -x * k + F(x, j - 1))$$$ to our Lichao Tree and take queries later.

    But another thing to notice is that if some elements are poped out from our stack, the Lichao tree should also be changed. But luckily, only the top elements are deleted from our stack so its prefix is still the same. Here, we can use a persistent Lichao Tree to handle this case.

    So my time complexity is actually $$$O(NKlogC)$$$ for building the segment tree of ConvexHull and $$$O(Nlog)$$$ memory for having a persistent Lichao Tree.

    Since this solution is pretty much disgusting, I hope its not author's solution. But i dont want his solution to be $$$O(Nkloglog)$$$ either cause I didn't expect it to pass and spent all my contest thinking of a better (not the one above lol) one.

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

      "...I hope it's not the author's solution..." - Your hope is futile.

      On the other hand, I was sure, that there would be much better solutions.

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

        Here's a similar solution but maybe easier to implement.

        Denote $$$D_{i, j}$$$ as the minimum cost to split prefix $$$i$$$ to $$$j$$$ subarrays. we fix $$$j$$$ and solve the layer in $$$\mathcal{O}(n \log n)$$$.

        We compute the answer for all $$$i$$$ in a D&C fashion; to compute the answer for all $$$l \le i \le r$$$, first recursively solve for $$$[i, m], [m + 1, r]$$$ where $$$m = \frac{l + r}{2}$$$, and then we consider transitions between the two halves.

        define $$$A_i = \max(a[m+1...i]), B_i = \max(a[i...m])$$$, the transition is

        $$$D_{i, j} = \min_{k \le m} (D_{k, j-1} + (i - k) * \max(B_k, A_i))$$$

        Notice that due to monotonicity of $$$A, B$$$, for fixed $$$i$$$ there is a suffix of the first half where $$$A_i$$$ is larger, and a prefix where $$$B_j$$$ is larger. We can solve both cases independently;

        $$$D_{i, j} = \min_{k \le m} (D_{k, j-1} + (i - k) * A_i) = \min_{k \le m} (D_{k, j-1} - k * A_i) + i * A_i$$$

        We have a linear function inside (for constant $$$k$$$), so we can maintain those in a cht. When we increase $$$i$$$, the suffix in which $$$A_i$$$ dominates increases, and we repeatedly add functions with smaller slopes, so we can do this in $$$\mathcal{O}(n)$$$.

        The case when $$$B_k$$$ dominates is almost identical, same analysis.

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

        Here's another boring solution.

        As many said, DP formula should be like $$$dp(i, R) = \min(dp(i - 1, L - 1) + (R - L + 1) \cdot \max(a_{L}, a_{L + 1}, \ldots, a_{R}))$$$ $$$(L \leq R)$$$.

        Now let's rewrite this formula using $$$a_{M}$$$ $$$(L \leq M \leq R)$$$ as any maximum element in that subarray, and then we can boost the transmitting process of $$$L \to M$$$ and $$$M \to R$$$ separately.

        Denote $$$[left(M), right(M)]$$$ as the maximal subarray that contains $$$a_{M}$$$ as its maximum element. For each $$$M$$$, we first calculate $$$f(M) = \min(-(L - 1) \cdot \color{red}{a_M} + dp(i - 1, L - 1))$$$ $$$(left(M) \leq L \leq M)$$$, and then we update $$$dp(i, R)$$$ $$$(M \leq R \leq right(M))$$$ by $$$(a_M \cdot \color{red}{R} + f(M))$$$.

        In both parts, we only need to answer the minimum inner product for a query 2D vector (e.g. $$$(a_M, 1)$$$ or $$$(R, 1)$$$) with one vector (e.g. $$$(-L + 1, dp(i - 1, L - 1))$$$ or $$$(a_M, f(M))$$$) selected from a certain set.

        To implement easily, we can maintain two segment trees of convex hulls offline. Since we don't need to support insertion and query for segments simultaneously, and we can sort the points in increasing order of the first coordinate, we can solve the problem in $$$\mathcal{O}(n k \log n)$$$.

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

          I don't know how to work without supporting insertion and query for segment simultaneously. For answering $$$f(M)$$$ , we need to know the minimum inner product, it can be solved by working binary search on segment tree with $$$O(log^2n)$$$. And for updating $$$dp(i,R)$$$ , we need to maintain a set by stack and use Li Chao tree with the same complexity. I can't understand how to solve this problem by sorting the point:(

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

            Let's maintain two SegmentTrees, in which each node stores the convex hull of a set of points. By doing insertions and queries offline, we can insert points in increasing order of the first coordinate (which means you only need to append points at the end of each hull) and then resolve query points in increasing order of the first coordinate, which means you only need to calculate the inner product between each query point and the point at the end of each hull (and drop useless points when it's necessary). Note that we avoid any binary search by doing things offline.

            The outline is like this:

            • insert all points obtained from $$$dp(i - 1, \ldots)$$$;
            • query all points needed to calculate $$$f(\ldots)$$$;
            • insert all points obtained from $$$f(\ldots)$$$;
            • query all points needed to calculate $$$dp(i, \ldots)$$$.

            Here is my submission: 55180395

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

              Oh! I get it! Thank you so much!

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

    It can be solved with ordinary segment tree. With time complexity O(NKlogN). Our dp will dp[k][n], where k is number of groups, and n is representing last added to some group. Now let's focus on solving only one dp layer in terms of group. Update segment tree by setting cost of each index to value of dp[prevgroup][that_index]. Now iterate from left to right, suppose that we are at index i now. Each index will have some cost in segment tree. Now our reccurence will be dp[i] = min dp[j] + cost(j,i). This can be easily found if we can calculate efficiently cost(j,i). Instead of calculating it each time, we will somehow update it efficiently. We can do so by grouping elements by maximum element from them to our i. Now one can see that when moving right, we can find where this element represents maximum. And set it as maximum for new group, while deleting previous groups that those elements belong to. Only thing that is left is that maximum is multiplied by length. We can handle this again by segment tree arithmetic progression update (it can be found easily on net, i am lazy to write about it now). I hope i helped.

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

      It seems like there will be a problem to combine operations "add arithmetic progression to a segment" and "find minimal value on a segment".

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

why ternary search is not correct for problem C? i am getting WA on test case 2.

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

    Ternary search (to find crest) holds good for a function whose value keeps on decreasing till some point, then keeps on increasing.

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

Why my this solution for B is failing on test 8 . Solution

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

    your answer bigger than 2^32 so you should puts OVERFLOW!!!

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

    seems that u need to judge if no>0 when adding to ans

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

      But when no > 0 sum will be ~1e15 so I think there is no need to do it .

      By the way I'll see . Thanks for your time .

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

    you missed a few cases while handling your 'no' variable, just made required changes 55178901

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

What is the hacking penalty and profit for Educational round?

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

    There is no direct addition in score on hacking a problem in Educational Round but it seems quite a good debugging practice

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

Can anyone help what's wrong in this submission for Problem B. 55174319 Thank you!

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

What is hacking test case for B)?

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

Why there are so many hacks in B? Weak Test Cases?

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

    code which loop through vector/stack every time they add the number can cause TLE.

    the test case looks like this.

    100000
    for 1    x 10000
    add      x 80000
    end      x 10000
    

    mine got hacked too :)

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

I saw some of the solutions for F rely on the fact that the answer will not be too large. Does anyone want to give a proof/intuition on that?

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

    Let a valid subarray be $$$a_{l}, a_{l + 1}, \ldots, a_{r}$$$.

    Observation 1: Pick up all the elements of value $$$1$$$. For every two adjacent elements $$$1$$$, denoted by $$$a_{x}$$$ and $$$a_{y}$$$, if $$$l \leq x$$$, then it must be held that $$$x \leq r < y$$$.

    More generally, for every three adjacent elements $$$1$$$, denoted by $$$a_{x}$$$, $$$a_{y}$$$ and $$$a_{z}$$$, $$$x < l \leq y$$$ must lead to $$$y \leq r < z$$$.

    Observation 2: Let's fix the position of value $$$1$$$ as $$$a_{k}$$$ ($$$l \leq k \leq r$$$). Without loss of generality, we assume the position of value $$$(r - l + 1)$$$ is on the right of $$$a_{k}$$$, and then we can conclude the only one possible $$$l$$$ by enumerating $$$r$$$, as we know $$$l = r + 1 - \max(a_{k}, a_{k + 1}, \ldots, a_{r})$$$.

    Consequently, there are at most $$$2 n$$$ possible subarrays that we need to check if the elements in each subarray are distinct.

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

Why this solution of D is wrong? Take the cut $$$[ k, n ]$$$ and find maximum suffix of it, $$$[ l, n ]$$$. Increase answer by the sum on $$$[ l, n ] * k$$$. Then find the maximum suffix of $$$[ k-1, l-1 ]$$$ and so on. In the end, if there some elements in the beggining of the array, which weren't counted in any suffix, also add them to answer. We can do all this with the segment tree in $$$O ( ( n + k ) \log n )$$$.

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

Can you tell me why it gives WA in test 9? https://codeforces.me/contest/1175/submission/55166598

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

Was I the only person who felt B was trouble-some and spent more time on it compared to C and D?

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

Could someone tell me why I will get WA in T5? Thansk. 55187500

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

    The problem is in this part:

    if(tmp*x>=LIMIT){ cnt++; }

    what if there is no add inside the loops, but you still increase cnt and print overflow.

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

      But I solve this case like: else if(str=="end"){ if(cnt>0) cnt--;

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

      I think I am so stupid that I will ignore the x of input,if cnt>0 :(

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

At first, there was a legend related to the name of the problem, but now it's just a formal statement.

Does someone know about that legend?

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

editorial?

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

In problem B it was specified "x is an integer variable and can be assigned values from 0 to 2^32−1" so doesn't it means the range of x is [0,2^32-1] and the number 2^32-1 should be included or my English is just bad?

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

    Yes, both 0 and 2^32-1 are included.

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

My Submission got accepted during the contest 55132811 but after the contest ended the status changed to Compilation error. I checked the same code on custom invocation and it compiled without any errors. What the heck is going on!! Can somebody explain?

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

Ok, feels lucky for being expert again :^)

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

Hello everyone! Answer me please. Why is my solution for C getting TL? What's wrong? https://codeforces.me/contest/1175/submission/55161342 Please, help)

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

Help!! Could someone please explain how to solve C what does ar[i+k]-ar[i] even mean;

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

    In my opinion, it's because the first k value will be generated in a[i] ~ a[i + k] intervals.

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

    To answer on task's question you should find the smallest interval which include exactly k points.

    My submission: 55152560

»
5 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).

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

Any hint for F?

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

    (l,r) is a subpermutation iff r = max(l,r) + (l-1) and all values in(l,r) are unique. so we try to find out how many valid l are there for a fixed r, and this can be done by a segment tree with lazy propagation

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

      Can it be solved via BFS? Start bfs at each 1 with state (i,i+1), from (l,r) next state is (l-1,r) if a[l-1] == r-l+1 and (l,r+1) if a[r+1] == r-l+1. Increase answer by 1 for each state reached. Bound is number of permutations, which should be much less than N^2.

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

        I don't think, it can be solved by BFS .

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

          You're right, I missed the statement by a mile.

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

      Can you explain how to find number of valid l for a fixed r using segment tree with lazy propagation

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

        If all values are unique in range (l,r) then r <= (l-1) + max(l,r). Its equal only when (l,r) is a subpermutation. So for a fixed index r, in each l such that l<=r we need to have (l-1)+ max(l,r), and in each node of segment tree we need to store the minimum in that and a count denoting in how many indices that minimum occurs. As you go right and your r changes, the max (l,r) for some l is changing. You can maintain the maximum with the stack technique. And in segment tree you need to handle that with lazy propagation. You can have a look at my code for a better understanding. 55194670

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

Can someone help me find the problem with my code for problem B ?

Submission: https://codeforces.me/contest/1175/submission/55197218

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

    The value val should be (1<<32) — 1 instead of just (1<<32) . Read problem statement to sure

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

      Thanks for reply. But, I used '>=' to check for overflow considering that.

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

Can anyone explain why it is giving wrong answer on test case 8 in problem B? My submission-55198130

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

    Read a bit above . Mb it will help you

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

      I have applied the overflow condition whenever I am adding but still I cannot understand why I am getting wrong answer on test case 8

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

        sarthakoherwal, your code will fail for this test : 4 for 2^32-1 add end add

        You have to apply additional overflow check in the else if loop after the line 'x+=checker'

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

    are you checking for if( x > (int) pow(2,32) - 1 ) then cout<<"OVERFLOW" ?

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

where is editorial ??

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

Why isn't the editorial out yet?

»
5 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).

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

When will tutorials come ?

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