vovuh's blog

Codeforces Round #515 (Div. 3)
By vovuh, history, 6 years ago, translation, In English

After the long delay (disease, conference and many other things) the new Div.3 round is coming!

<copy-pasted-part>

Hello!

Codeforces Round 515 (Div. 3) will start at Oct/12/2018 17:35 (Moscow time). You will be offered 6 or 7 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. Probably, participants from the first division will not be at all interested by this problems. And for 1600-1899 the problems will be too easy. However, all of you who wish to take part and have rating 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round it will be a 12-hour phase of open hacks. I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over. You will be given 6 or 7 problems and 2 hours to solve them.

Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participants of the third division, you must:

  • take part in at least two rated rounds (and solve at least one problem in each of them),
  • do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of my work. Thanks to my good friends Mikhail awoo Piklyaev, Maksim Neon Mescheryakov and Ivan BledDest Androsov for help in round preparation and testing the round.

Good luck!

I also would like to say that participants who will submit wrong solutions on purpose and hack them afterwards (example) will not be shown in the hacking leaders table.

</copy-pasted-part>

I also would like to thank arsijo, Decibit, PrianishnikovaRina and nooinenoojno for help with the preparation and testing the round!

UPD: I'll be on the community Discord server shortly after the contest to discuss the problems.

UPD2: The editorial is published.

UPD3:

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 nickyrio 6 165
2 smokescreen 6 205
3 lanven 6 239
4 RockButterfly 6 242
5 wythend 6 330

Congratulations to the best hackers:

Rank Competitor Hack Count
1 Gabies 82:-24
2 djm03178 33:-3
3 Laggy 27:-10
4 wanderer163 11:-1
5 antguz 10:-1

231 successful hacks and 322 unsuccessful hacks were made in total!

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

Problem Competitor Penalty
A CopeCope 0:01
B stafdasca 0:06
C nickyrio 0:04
D nickyrio 0:11
E somanaik 0:15
F Ohyeeeeee55 0:50

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

Comments Comments (82)
| Write comment?
»
6 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Hope this div — 3 won't be like last div — 3

→ Reply
»
6 years ago, # |
  Vote: I like it +15 Vote: I do not like it

6 or 7 problems

When did vovuh become Schrodinger?

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

    Sometimes the the number of problems changes right before the start of the round :) It might happen, but in this round (I hope) will be exactly 6 problems :)

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

      Now I understand the true purpose of your profile picture

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

IT'S TIME TO UP YOUR RATING, GUYS

→ Reply
»
6 years ago, # |
  Vote: I like it -10 Vote: I do not like it

How can I improve my level to solve C&D?

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

Wow!

About 1 month the Div.3 contest came again!

I feel surprised!

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

The last Codeforces Round before NOIP 2018. RP++.

→ Reply
»
6 years ago, # |
  Vote: I like it -16 Vote: I do not like it

Div 3 only? Not good.

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

Finally a contest by my favourite problem setter after a long time. I love Div 3. :)

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

finally div 3 , i wish it will be esiear than last one

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Unfortunately, clashing with Snackdown :(

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

    Duration of snackdown is of 3 days. You can easily participate in both

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

if my rank is above 1599 can i participate in div 3

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

disease

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

    Thanks, bro :)

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

High rating & Good luck

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Wish you all get +100 rating!

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

    Guess Mike hasn't yet been able to find an algorithm to make that happen...

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

    Some wishes can never become reality unfortunately :(

    → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Hoping for no delay...

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

    I guarantee that there will no delay because of problems readiness :) So there will no delay if nothing special happens...

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck!!I hope we will learn alot.

→ Reply
»
6 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Hey vovuh, i suggest that you should become Master quickly, because your color doesn't match top contributors's colors, which makes me a little uncomfortable.

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

    Ahah, this makes me laugh :D I will become Master as soon as possible, hope I can do it :D

    → Reply
»
6 years ago, # |
  Vote: I like it +13 Vote: I do not like it

This isn't Div 3

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This Div3A was much, much harder than Div2A typically is. It also didn't have any coding, just math.

→ Reply
»
6 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Wth happend to my brain in problem B

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

    Same, but for me it was an error of index in the vector, it took me like 20 min to find it.

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

      in div(1+2) last contest I solved 3 problems but in div3 Idk why I always become dumper than homer (simpsons)

      the problems aren't that hard but it's like my brain gets numbed because I'm telling myself these are div3 too easy

      → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve D ?

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

    start from behind till you run out of boxes .

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

      How did you think that you will have to start from behind?

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

        It's specified in the problem statement that you can remove boxes from start.

        "Maksim wants to know the maximum number of objects he can pack by the algorithm above. To reach this target, he will throw out the leftmost object from the set until the remaining set of objects can be packed in boxes he has. Your task is to say the maximum number of objects Maksim can pack in boxes he has."

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

    Use greedy, start from behind and keep a temporary sum, as soon as this temporary sum is bigger then k take another box, if you have an available one, if not then you just end.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      in case : 3 2 5 2 5 1 wouldn't the distribution be [1 2] [5] so the answer is 3?

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

        Every box should contain Consecutive elements

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

          I keep reading the problem statement and can't see where was that mentioned.
          Any way thanks for the clarification mate.

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

            It wasn’t said directly but you can understand it from the statement .

            → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is formula dp for problem B?

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

    Is it dp?

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

    You can use greedy

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

      Really ? I wasn't able to figure out a greedy solution during the contest. In the back of my mind i was still thinking that a Div3-B can't be a DP problem.

      Now after the contest, i saw a few codes, many were done neatly using Memoization. Can you share what Greedy approach you have used ? And which approach would be easier to Debug here ? Greedy or DP ? (I think DP looks neat enough here)

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

        For every position X that is not heated i look for the first heater from the position X + r — 1 backwards to position X — r + 1. The next X is the position of the heater I chose + r.

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

        For coding and debug DP is better. It is short code.

        → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Codeforces Round #515 (Div. 1 + Div. 3, combined)

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C?, I was thinking in a segment tree but i wasn't sure.

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

    two prefix arrays for books placed on left and right.

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

      Can you elaborate please ? I would love to know a new way to solve the problem ?

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

    You can map the book ids to a set of consecutive integers which are ordered according to the order in which we put the books on the shelf. (Let's call these integers — "second IDs") (Use a C++ std::list or even std::map for this)

    Then for third type Query, you can use the mapping just created and binary search for the second ID of the required book in the second ID collection(Either a vector or a SET) and using the smallest second ID and largest second ID in the collection you can get the answer.

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

    Two arrays for books on left and on right. You can see my solution. Don't think you would need to find an easier one:

    http://mirror.codeforces.com/contest/1066/submission/44217835

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

    I used segment tree for fun. http://mirror.codeforces.com/contest/1066/submission/44219102 If you don't understand the code I can explain with more detail

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

      Can you explain what you kept in node and how did you managed query and update?

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

        I created a center position far enough so i csn go left in every query and never have a negative position. Each node has 1 if position is occupied and 0 otherwise. Every left query ocuppies a node left to the last one and similar with right queries. You end up with a segment tree where leafs look like this: 000...01110111000...000 I save another array where a[id] is the position of the book in the segment tree. Now queries are simple Query from 0 to id (id not included) is the sum of all 1s left to id. Which is what you need to delete so id becomes the leftmost one. Query from id+1 to N which is from id to rhe rightmost node of the segment tree is the sum of all 1s right to id. Which is what you need to delete so id becomes the rightmost one. I hope i explained it well. Good luck!

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

          That's some precious and articulated explanation! Thanks! I just learnt segment tree few days back, and I got accepted following your approach. Learned a simple but effective technique, storing the position in the segment tree to another array. Thanks again.

          → Reply
»
6 years ago, # |
  Vote: I like it -12 Vote: I do not like it

Contest was so poorly managed. See what I encountered when I opened problem B:

Explanation Part: In the first example the heater at the position 2 warms up elements [1;3], the heater at the position 3 warms up elements [2,4] and the heater at the position 5 warms up elements [5;6] so the answer is 3.

6 2 0 1 1 0 0 1

But there wasn't any heater at pos 5.

Problem Scenerio Part: If n=6, r=2 and heaters are at positions 2 and 4, then Vova can warm up the whole house if he switches all the heaters in the house on.

How can heater on pos 4 warm 3 to 6? r is 2 so it should warmed up 3 to 5.

Asking this, the contest team replied it was an typo and to refresh the page. What about the 15-20 minutes I wasted scratching my head off over the explanation? Why wasn't any announcement made? Assuming the typo was fixed much earlier, what about the people who have had opened the tab in the very beggining? Do I get consideration for that time penalty? Even after replying my question, they didn't make any announcement.

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

    I too left the problem B during the contest because of that. I thought it was not my thing.

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

    I will describe it to you. I cannot make any announcements by myself. Mike was too busy with the Southern Quarterfinal preparation, other admins (or who have access to make announcements, I don't know) didn't have the access to this contest. So how I can post an announcement if I have no rights to do it?

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

      First of all, thanks for explaining the reason. I get it. I won't blame the contest team for this. But definitely CF team should come up with a better system. Giving access to make announcements to contest creators won't be bad for a start. You don't expect this kind of bugs from one of the world's leading competitive programming hosts.

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

        I understand your opinion. In fact I had hold this contest alone and answer all the clarification by myself. Sorry if sometimes you has got bad answers or don't understand my replies.

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

          From your part, I suppose you did what you could do best. Thanks for the quality problems, though.

          → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I Liked the contest, really felt like a Div. 3 competition.

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

I would like to know if there is Hack data in the D question using the traversal method from the back to the front.

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

    No, this solution can be proved (I will describe it in the editorial) and this cannot be hacked.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

very nice contest

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The editorial is published now!

P.S. I write this comment because of [cut] of the blog at the main page. Someone can miss that the blog is already published because of this [cut].

→ Reply