vovuh's blog

By vovuh, history, 6 years ago, translation, In English

<copy-pasted-part>

Hello!

Codeforces Round 535 (Div. 3) will start at Jan/23/2019 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>

UPD: I also would like to thank testers ismagilov.code, budalnik, Arpa, filippos, eddy1021 for the great help in round preparation!

UDP2: I don't sure about G63-AMG so I included top-6 instead of top-5 in the table. And I'm also don't sure that some hackers aren't cheat so forgive me if my information is wrong.

UPD3: Editorial is published!

Congratulations to the winners:

1 b31quocbao 7 358
2 GZY_AK_IOI 7 455
3(?) G63-AMG 6 101
4(3?) pushkar12 6 216
5(4?) _DarkDawn_ 6 226
6(5?) Amooo 6 229

Congratulations to the best hackers:

Rank Competitor Hack Count
1 _bacali 181:-49
2 Chiakisa 55:-8
3 CNH_NHI 10:-1
4 Cylinder 9
5 CNH_NSIS 8
378 successful hacks and 348 unsuccessful hacks were made in total!

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

Problem Competitor Penalty
A spacewanker 0:01
B mpstxdy 0:03
C G63-AMG 0:06
D arpit040199 0:06
E1 G63-AMG 0:11
E2 TsingTaoDaTieWang2 0:16
F Zhao-L 0:20

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

| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope its not like..

DIV2<DIV3<DIV1

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

    Maybe a Div3 = Div1 + Div2 ....

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

      More like Div3=Div2-Div1...

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

        Let's Increase it's value a little Div3 = (Div2 — Div1) * 1.5; ;)

»
6 years ago, # |
  Vote: I like it -27 Vote: I do not like it

i hope it won't have any useless and pointless math involved...
also may i ask will it rate my rating?

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

    The contest will be rated for you as long as you're under 1600 (now you're 1599). If you took part in today's contest and it will raise your rating — the next Div. 3 won't be rated for you. Half of your comments are complains about maths :D I don't agree with your statement that maths has nothing to do with programming. It has a lot, especially with competitive one. All of the algorithms (e.g. graph theory) come from mathematics. Try to deal with it if you want to have fun from Codeforces.

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

Round by vovuh !! Always exciting to participate!

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

Wish a lot of AC <3

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

Div3 contest is like a gift for contestants below 1600.

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

Announcement of Codeforces Round #299 (Div. 2)?

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

Perfect announcement doesn't exi...

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

[Off Topic] I am trying to practice on my hacking skills for the next contests. Is there any good blog post about how to approach hacking effectively? Some sort of guidelines/best practices on how to hack solutions.

I searched but couldn't find any

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

Step 1 : study for exam

Step 2 : participate in Cf round

Step 3 : loose 100 rating points because your mind was tired from studying

Step 4 : fail the exam because your mind became even more tired after trying to solve problems

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

    problems are easy in Div3, today I'll be in TOP 20

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

Is div3 friendly to new people?

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

    Yes, it's without a doubt the best contest new people can choose. But it doesn't mean it will be easy. If you have no or little experience in competitive programming, doing 2 or 3 problems will be a quite good result. Good luck.

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

Is vovuh nephew of Mike Mirzayanov? Why does he take every single Div3 Round?

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

Does it mean that participants with 1600 higher rating taking part in Div.3 would not be rated ?

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

Another div 3 round, which is equal to div 2. In any case, thanks for the prepared problems. Good luck, have a fun. Take care of your feet

»
6 years ago, # |
  Vote: I like it -19 Vote: I do not like it

Yet again disappointed by weak pretests >:(

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

    Sorry, I tried to make strong tests in almost all problems and just forgot about you! The only tests among your solutions are in the problem B with answers 69 and 42 :(

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

      Bro just do it like a normal CF Round... please drop that 12-hour open hack feature.

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

    All of your solutions are hacked.Because "if(n==69)return 0;".

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

swap(C, D)

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

C && D giving TLE in java wow in-spite being O(N) =_=

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

    Changing the string to char array gives AC WOW! okay -

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

      String objects are immutable, which means ans+='B' requires creating a brand new String object and copy all characters, then append 'B' to it.

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

how to solve E2

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

    i think this solution is right though i couldn't find an apropriate implementation that fit in time and memory limit for it...

    first you have to prove that the answer is when you choose the segments that doesnt intersect whith the maximum element.now you can fix the element that shoud be the maximum and apply all the segments that doesn't intersect with this element and get the minimum,this can be done using segment tree

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

      I did that in E1 , assumed that each element is a maximum and chose the segments that don't affect that number

      However I don't know how to do it in E2 time limit

      how can it be done using segment tree ?

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

        you have to use minimum segment tree.

        but for the precise implementation,i couldn't get the accept for the problem,i fix the time limit problem by just a little spitting on my code,but that one agian couldn't fit in memory

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

          My implementation with segment tree : 48837273

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

            yes,you used the sweep line trick that i didn't and because of that i couldn't get the accepted

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

        We do not need a segment tree here, check it out for my solution: https://codeforces.net/contest/1108/submission/48881765

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

Testcase 26 Problem F?

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

Need help on C. I don't know what I did wrong.

https://codeforces.net/contest/1108/submission/48833951

BTW any recommendation for E1,E2 and F???

//swap(D,C). and maybe even swap (D,B). I lost 50 mins on C and just read D and like "Uh what???"

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

    Simply try "RGBRGB..." "RBG" "BRG" "BGR" "GRB" "GBR" and find the minimum among these choices.

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

So it's my first time to see a problem which has two types in Codeforces.

(And I haven't solved it/them.:D It should be an easy problem though..)

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

I don't know about you guys but 12-hour phase of open hacks is certanily the only thing I don't like about this Div.3 contest, why don't you leave that feature for Educational Rounds only ??? You can downvote me, I don't care about that, but I have to say it... is painful.

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

    But this is really helpful to improve your skills.

    I think that Codeforces is a site to help you improve your skills, ratings is not the only thing right?

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

      Ok, but regular CF rounds allow you to hack as well, my opinion is that it would be better to leave the 12-hour phase of open hacks for Educational Rounds only and let this div. 3 rounds more like the regular div. 2 / div. 1 rounds. Again is just my opinion. Happy codings to all :P

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

Can somebody tell me what's wrong with this code on problem E2?

My submission

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

https://codeforces.net/contest/1108/submission/48801874 i find new thing one of the guy is submitting right solution expect for case n == 69 and he is hacking with another account . please report this user and please dont allow this to happen in future the user is @problem_destroyer420

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

I did try to solve the problem E1 using DP. but I did not solve the number of segment T^T...

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

Am I the only one who felt today's Div3 first 3 problems are more difficult than yesterdays Div2 first 3 problems?

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

    I would say that the diffucult is about the same.

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

How to solve E2?

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

    For every index of the array assume that it is not affected by any of the M updates. Apply all the other updates which don't affect that index and calculate the answer i.e. max — min.

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

      how to do that in E2 time limit

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

        Apply all the queries to the given array initially. Now you can do a sweepline on the updates based on which index they appear and which index they disappear. Submission

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

        You can use sweep line technique. Iterate i from 1 to n, for each i subtract all segments [i, j], then calculate. After calculating, add all segment [j, i] so that next i won't use old segments.

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

        Check all indices in increasing order. For each index, check all the segments and find if the index is the start of the segment. If it is, then subtract 1 from all elements in the segment, and re-calculate min and max and update the answer. Check all the segments again and see if the index is the end of the segment. If it is, then add 1 to all elements in the segment.

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

          Can you explain in some detail why it works? Is it because you are trying to depress the value of the ith element as much as possible, and the highest element e such that e-a[i] gives the max answer can either be a part of that segment or not, if it is not a part you gain one, if it is you dont lose anything since both get devalued by 1? Please correct me if I am thinking of something wrong

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

            Basic principle is to make each element as small as possible. So for each element, you're going to subtract 1 from all segments including that element.

            If you check indices in increasing order, the only segments you need to check are the ones you enter or leave. This guarantees that when check an index, all segments including that element has already subtracted while others are not.

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

            Yes, exactly.

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

      Yeah, I solved E1 with that observation. But that gets TL for E2.

»
6 years ago, # |
  Vote: I like it -34 Vote: I do not like it

contest was so easy :D

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

Anyone tell me what happened with my solution. I just change string color = "GRB" code (WA on test 4) to color ="BGR" code and got AC?

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

    next_permutation needs your passed array to be in sorted order, RGB is not sorted, but BGR is

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

what's the dp solution for probD?

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

    State: dp(index, prev_letter)

    Transition:

    if(prev_letter != cur_letter):  
      dp(index, prev_letter) = dp(index+1, cur_letter);  
    else  
      iterate i over ['R', 'G' and 'B'] and i != prev_letter: 
         dp(index, prev_letter) = minimum_of ( 1 + dp(index+1, i) ) ;
    

    Please check my solution for more clearity.

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

can anyone tell why my code https://codeforces.net/contest/1108/submission/48851718 for problem https://codeforces.net/contest/1108/problem/E1 shows wrong answer on online ide while it give correct answer in sublime text??

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

What is the intended sol in E2? Segment tree with lazy prop didn't pass for me. (tle #15)

UPD — AC. Missed to apply sweep line on updates.

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

Someone can explain me why my position in standings changes after refreshing the page? Which of these is the official one?

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

Can anybody tell me what is wrong with my E?

I tried greedy + segtree.

Like if you want to have ai as the maximum after applying the subset of intervals applying intervals that contained ai would not help and applying intervals that do not contain ai would not damage, so I just iterated over i and do the updates :P

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

    Your idea is right. I think there're some mistakes in you code.

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

      Can you please help me find what is wrong ?

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

        I'll send you a private letter.

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

Can anyone explain problem F a little , I mean the sample test case 1.

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

    Initially, two kinds of MST are possible. Both uses edges (3,7), (4,8), (1,2), (1,4), (2,3), (3,5). One possible MST uses edge (1,6) while the other uses edge (3,6).

    If you increase the weight of edge (1,6), then the only MST possible now is the one that uses (3,6). Same for increasing the weight of edge (3,6) where only the MST using edge (1,6) remains.

    If you're not familiar with MST, you'd better search for it first.

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

in B, can answer to test case

4 9973 1 9973 1

be 9973 9973 ?

nowhere it is mentioned x!=y. this solution satisfies all conditions in question.

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

Thanks vovuh for this nice contest. Questions were well constructed and difficulty was also gradual :)

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

Hi guys, i work in c++ gnu g++14. I have a problem with task B. All my solutions when tested by me output correct answers but when i submit them, program always output "0 0". Any idea why is this happening ?

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

    You should only use one I/O library (C or C++) after using ios_base::sync_with_stdio(false);. i.e. using only cin or using only scanf.

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

copying alert : The submissions of the a/c LightningFrenemy213 and arpan_dg are identical.

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

How to solve E1 ?

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

    For every index in the array, apply every query that doesn't include that index, to the original array and calculate the difference (max-min).

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

      How ? Any reason for this approach

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

        What you're doing with this approach is just checking the final states of the array when that particular index is not included in any query that you've applied. There will always be a case when the difference between max — that index element and min — calculated after applying the queries, will be maximum.

        This is one approach, there might be other approaches to solving this problem.

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

Why my rating don't update?

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

O(nmlogn) algorithm of E2 48867037

I use some method to decrease the constant, and it exits when time is up.

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

I can't blieve D is much easier than C,But it's TRUTH :P

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

nice problems :D

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

Weak systests, my solutions passed

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

This round was quicker than the previous Educational round !!

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

User Iamoni coded with friends.
Problem A(48801772)
Problem C(48805698)
Problem E1(48808903)
Problem E2(48822818)
Different templates, different coding styles.

vovuh MikeMirzayanov

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

    Good catch there. Also the submission times are highly suspicious. Hopefully they will look into it.

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

can anybody help why my O(n^3) solution for B is wrong https://codeforces.net/contest/1108/submission/48890311

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

    How did you get this approach?_

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

      I tried to make all the pair of x and y from the given array and then checking for every pair whether it satisfy the given constraint for x and y , if yes then print x and y ( I still don't know what is wrong in my approach).

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

        try tests,where x — is 1 and y — composite num

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

vovuh, will you publish the editorial?

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

    In a few minutes, bro, please wait a bit :)

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

      In a few minutes,

      108 minutes ago XD

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

        It is published now XD But it isn't work XD I don't know why XD

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

How to solve E by segment tree? (PS: When will the Tutorial be published?

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

    A key observation is that there is always an optimal solution that selecting all segments covering a specific index (let us call it x). To look for x, we can use a sweep line to handle with the segments and use a segment tree to update the answer.

    You can see my code for more information.

    (UPD) It seems that someone has answered the same approach before :(

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

Editorial Page is not working for me! does someone else has this issue too?

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

48837239 — what is the issue with this?

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

Why are you not sure about Lamoni?