Vovuh's blog

By Vovuh, history, 9 months 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 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>

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

UDP2: I don't sure about Iamoni 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(?) Iamoni 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 CutieRabbit 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 Iamoni 0:06
D arpit040199 0:06
E1 Iamoni 0:11
E2 TsingTaoDaTieWang 0:16
F Zhao-L 0:20

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

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

I hope its not like..

DIV2<DIV3<DIV1

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

    Maybe a Div3 = Div1 + Div2 ....

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

      More like Div3=Div2-Div1...

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

»
9 months 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?

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

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

Round by Vovuh !! Always exciting to participate!

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

Wish a lot of AC <3

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

Div3 contest is like a gift for contestants below 1600.

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

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

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

Perfect announcement doesn't exi...

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

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

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

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

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

Is div3 friendly to new people?

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

»
9 months 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?

»
9 months 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 ?

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

»
9 months ago, # |
  Vote: I like it -19 Vote: I do not like it

Yet again disappointed by weak pretests >:(

  • »
    »
    9 months 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 :(

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

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

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

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

    Why are you putting if(n==69) return 0; Your all solution are hacked @problem_destroyer420

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

swap(C, D)

»
9 months 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) =_=

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

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

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

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

how to solve E2

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

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

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

      • »
        »
        »
        »
        9 months 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.com/contest/1108/submission/48881765

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

Testcase 26 Problem F?

»
9 months 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.com/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???"

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

    Same feelings, bro :(

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it -18 Vote: I do not like it

      You know how can I solve C afterward?

      Brute force the solution got AC bro lol

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

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

      That's what I did after I got WA haha

      Honestly speaking, as a C, it sucks though. I mean, brute force get AC but "proper thinking" solution got WA????

      I think if the problem setter change the distance and amount of number to 5, it will be better

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

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

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

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

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

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

https://codeforces.com/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

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

»
9 months 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?

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

    I would say that the diffucult is about the same.

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

How to solve E2?

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

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

      how to do that in E2 time limit

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

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

          Apptica what u mean by sweep line , how u used it . can u provide me its tutorial

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

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

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

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

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

            Yes, exactly.

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

»
9 months ago, # |
  Vote: I like it -34 Vote: I do not like it

contest was so easy :D

»
9 months 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?

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

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

      That's not true next_permutation prints all the remaining permutation till RGB but as GRB comes after BGR in permutation so it skips it, so if you are thinking that next_permutation won't work if your string/array isn't sorted then you are wrong!

      Happy coding!!

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

what's the dp solution for probD?

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

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

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

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

»
9 months 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?

»
9 months ago, # |
  Vote: I like it +3 Vote: I do not like it
»
9 months 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

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

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

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

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

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

»
9 months 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 ?

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

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

      Thank you, i"ll read more about it on internet.

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

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

How to solve E1 ?

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

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

      smart ty :D

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

      How ? Any reason for this approach

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

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

    Thats a greddy approach..I did same thing

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

Why my rating don't update?

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

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

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

nice problems :D

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

Someone please update Ratings.

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

Weak systests, my solutions passed

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

This round was quicker than the previous Educational round !!

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

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

»
9 months 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.com/contest/1108/submission/48890311

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

    How did you get this approach?_

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

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

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

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

          It is working , you can test yourself , I have given link to my submission

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

Vovuh, will you publish the editorial?

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

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

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

      In a few minutes,

      108 minutes ago XD

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

»
9 months 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?

  • »
    »
    9 months 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 :(

»
9 months 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?

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

48837239 — what is the issue with this?

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

Why are you not sure about [user:lamoni]?