Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

Vovuh's blog

By Vovuh, history, 2 months 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 PikMike Piklyaev, Maksim Ne0n25 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 lng11 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 SodaineGreen 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  

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

FINALY!!!

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

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

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

6 or 7 problems

When did Vovuh become Schrodinger?

  • »
    »
    2 months 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 :)

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

      Now I understand the true purpose of your profile picture

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

IT'S TIME TO UP YOUR RATING, GUYS

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

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

»
2 months 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!

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

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

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

Div 3 only? Not good.

»
2 months 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. :)

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

I've been hating div 3 for a long time ;|

»
2 months 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

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

Unfortunately, clashing with Snackdown :(

  • »
    »
    2 months 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

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

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

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

so much pain :P

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

disease

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

    Thanks, bro :)

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

Thanks for another rating round for div2 :)

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

happy new round:)

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

High rating & Good luck

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

Wish you all get +100 rating!

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

will this round have any problems with c# like I had last time?

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

Hope we will get some strong pretest problems. Wish you all high rating.

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

Hoping for no delay...

  • »
    »
    2 months 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...

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

Good luck!!I hope we will learn alot.

»
2 months 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.

  • »
    »
    2 months 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

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

This isn't Div 3

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

as I work through a relation of recurrence of order K,

F0=0

Fn= 1 for n=1...k-1

Fn = Fn-1 + Fn-2 + ....+ Fn-k

where 0<K<=3000? such that we can calculate the nth term of the sequence efficiently! I have No problem to calculate the nth term (fast exponentation!..), only problem is that it does not find a way to reduce this equation homogeneous in terms of smaller.... I would appreciate it very much!

»
2 months 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.

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

Wth happend to my brain in problem B

  • »
    »
    2 months 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.

    • »
      »
      »
      2 months 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

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

how to solve D ?

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

    start from behind till you run out of boxes .

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

      do you have a tricky corner case please? I have no idea why my solution is failing.

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

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

      • »
        »
        »
        »
        2 months 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."

  • »
    »
    2 months 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.

    • »
      »
      »
      2 months 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?

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

        Every box should contain Consecutive elements

        • »
          »
          »
          »
          »
          2 months 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.

          • »
            »
            »
            »
            »
            »
            2 months 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 .

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

Well, this round was about ranges.

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

What is formula dp for problem B?

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

    Is it dp?

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

    You can use greedy

    • »
      »
      »
      2 months 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)

      • »
        »
        »
        »
        2 months 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.

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

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

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

    It is just brute force. Let the array be a.

    You take index when a[i]==1. Then you go to i+2*r-1 and go backwards till you find another a[i]==1. and then set i=j for this j. repeat this process and put condition for -1.

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

    Ohh. Thanks

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

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

»
2 months 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.

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

    I solved it using a deq and map

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

    two prefix arrays for books placed on left and right.

    • »
      »
      »
      2 months 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 ?

  • »
    »
    2 months 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.

  • »
    »
    2 months 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://codeforces.com/contest/1066/submission/44217835

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

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

    • »
      »
      »
      2 months 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?

      • »
        »
        »
        »
        2 months 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!

        • »
          »
          »
          »
          »
          2 months 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.

»
2 months 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.

  • »
    »
    2 months 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.

  • »
    »
    2 months 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?

    • »
      »
      »
      2 months 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.

      • »
        »
        »
        »
        2 months 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.

        • »
          »
          »
          »
          »
          2 months 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.

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

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

»
2 months 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.

  • »
    »
    2 months 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.

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

very nice contest

»
2 months 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].

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

Could anybody help me why I am getting wrong answer for Problem C?Submission

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

My code of Problem B. heaters is working perfectly fine .but instead it shows me WA on test case 13 . while after contest I have submitted the same code .it gave me AC. my rating was not increased due to this . please help me and fix it

here is my code





#include <bits/stdc++.h> using namespace std; #define ll long long int main() { int n,r; cin>>n>>r; int a[n]; int res[n]; int he[n]; for(int i=0;i<n;i++){ cin>>a[i]; res[i]=0; he[i]=0; } int idx=-1; for(int i=0;i<n;i++){ if(res[i]==0){ for(int j=min(i+r-1,n);j>=i-r+1 && j>=0;j--){ if(a[j]==1){ idx=j; he[j]=1; break; } } if(idx>=0){ for(int j=idx;j<=idx+r-1 && j<n;j++){ res[j]=1; } for(int j=idx;j>=idx-r+1 && j>=0;j--){ res[j]=1; } } } } bool f=false; ll count=0; for(int i=0;i<n;i++){ if(res[i]==0){ f=true; } if(he[i]==1){ count++; } } if(f){ cout<<-1<<"\n"; } else{ cout<<count<<"\n"; } return 0; }