Vovuh's blog

By Vovuh, history, 8 days ago, translation, In English,

Happy New Year to all of you! So, meet another round from blue :)

<copy-pasted-part>

Hello!

Codeforces Round #531 (Div. 3) will start at Jan/09/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>

UPD1:

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 Jester 6 196
2 eneas 6 224
3 Nutella3000 6 267
4 pedulia 6 288
5 I_love_albeXL 6 297

Congratulations to the best hackers:

Rank Competitor Hack Count
1 ______-__________-______ 299:-99
2 im0qianqian 100:-3
3 greencis 97:-23
4 minhson 52:-2
5 MarcosK 35
1183 successful hacks and 1459 unsuccessful hacks were made in total!

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

Problem Competitor Penalty
A Isabella_Vesterbury 0:01
B ThankGodItsFriday 0:05
C Voronin_Ivan 0:05
D GiveMeAGirlFriend 0:16
E EremKa 0:21
F RedDreamer102 0:43

UPD2: Editorial is published!

UPD3: I forgot to thank eddy1021 for help with testing the round!

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

»
8 days ago, # |
Rev. 2   Vote: I like it +34 Vote: I do not like it

I was a bit surprised when I saw the black MikeMirzayanov lol

upd: I mean I am used to the magic MikeMirzayanov

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

    He is white...

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

      deep message ._.

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

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

        Why his ears are white?

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

          cause im a programmer not a graphist

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

            Dont be racist nigga

            • »
              »
              »
              »
              »
              »
              »
              7 days ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              u are white. Don't tell me u wrote that with a black pen cuz it is still offensive roflan

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

          When u write a question of this kind in English u put the verb in the second position. It's common knowledge. It also sounds really odd. come'on! Pls don't call me a grammar nazi lmao

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

        Gold.

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

      Man, at first sight I thought you were Radewoosh who changed his handle or something.
      That dp though xD

»
8 days ago, # |
  Vote: I like it -8 Vote: I do not like it

Good luck to everyone <3 !!

»
8 days ago, # |
Rev. 2   Vote: I like it -30 Vote: I do not like it

I think CODEFORCES loves me! Whatever comment(or reply) I make (I tried many kinds. Contributed, Made memes, Helped people etc.), always get dozens of upvotes. I'm really happy about it. I want to keep contribute.

»
8 days ago, # |
  Vote: I like it -15 Vote: I do not like it

17.35 (MSK) for contests is really inconvenient time for all who works in the office )

»
8 days ago, # |
  Vote: I like it +3 Vote: I do not like it

See you guys at expert. I wish..

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I didnt like first div3s but I think it evolved and now there some good problems init

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

6 or 7?

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

Oh no... "copy-pasted-part" is reaching another level. People will make memes with it (probably). Then it will die. Although it makes me laugh when I see a round begining and starting with it, stop overusing it. It will die :(

»
7 days ago, # |
  Vote: I like it +11 Vote: I do not like it

OMG, Mr Vovuh, when did u become blue? (( so sad... Is it because u are tired of session?

I wish u fast uprate

  • »
    »
    7 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Well, in last two rounds I had really bad luck and missed too many easy key ideas because of my brain (idk what's wrong with it) and because I didn't participate in any contests after NEERC at all. So I forget how to solve problems fast

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

      Lol. I thought you used the 'color changer' to get blue.

»
7 days ago, # |
  Vote: I like it +54 Vote: I do not like it

"You will be given 6 or 7 problems and 2 hours to solve them."
Can we assume that or as bitwise OR? 6|7 = 7

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

    Actually, because of precedence of operators, it is: (given 6) | (7 problems) = 69. So today we will have 69.

  • »
    »
    7 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    hahah too funny

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Huge participation :)

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Feeling like gotta explain the reference in task C to English speaking participants.

It is about a Russian video where policemen broke into an insane man's flat, by breaking his door. He was kind of surprised by that. He also appears to be very concerned and upset about that and wants them to repair the door and leave.

Here's the video (NSFW to anyone who knows Russian): https://www.youtube.com/watch?v=pJTSfvtM8iY

It made me laugh so hard, I wasted 10 minutes of my time on that. Well done, Vovuh! (how to tag a user btw?)

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

    to tag a user: press "user" in the right of spacebar at the top of a message

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

The problems are in appropriate difficulty for div3 contest,thanks.

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

I'd love to see the look on this guys face after he got WA on this test I specifically crafted just for the similar solutions (48143945) :D

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

Submitted F successfully at 1:59:20 ... Phew!!!

»
7 days ago, # |
  Vote: I like it +1 Vote: I do not like it

How to prove A?

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

    You can construct the solution for x from solution of (x-4)

    Base cases: n = 0 => ans = 0, n = 1 => ans = 1, n = 2 => ans = 1, n = 3 => ans = 0

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

    Suppose you have numbers x, x + 1, x + 2 and x + 3. Then you can take x and x + 3 to the first set, x + 1 and x + 2 to the second set and the difference between their sums will be 0. So you can take n modulo 4 and just solve it manually.

  • »
    »
    7 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The summation from 1 to n is n*(n+1)/2, let it be S, if S is even we can straight away divide the array into two subsets such that, the sum for both the subsets are equal, thus giving a minimum of 0, in the case of S being odd, since the division will not happen equally, the difference between the sum of two partitions will be at least 1, since the difference will be caused by any two numbers which are consecutive in nature.

    • »
      »
      »
      7 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you! I solved it but didn't know why it worked tho :D

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

      When a newbie explains better than an expert!

    • »
      »
      »
      7 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      This argument isn't thorough. I agree that the optimal difference will be equal to the parity of the sum, but it's not guaranteed we can achieve that.

      For example, if your array is [2, 4, 8], the sum is 14, but the best possible division is [2, 4] and [8], which has an absolute difference of 2. It's important to prove that the optimum division can be achieved for the set [1, 2, 3, ..., n]. I proved this using the same logic as Vovuh above.

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

(48141727) why this solution for problem E is wrong? what is testcase 32?

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

Hi! Please help me with problem F. Thankyou.

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

    After some precalculations, one can do bitmask DP to find the maximum answer

    My recurrence relation was DP[mask][first line][last line]

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

      Thank you! Unfortunately, I could not solve this during the contest :(

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

Hello mister Vovuh. First things fist, thanks for the support that you've shown to us with these rounds but i think this was a bit messed up.

Problem A was ok, but i don't quite enjoy these "intuition" type problems because when i saw it i was like : "yes, that got to be the solution", without proving it.

Problems C and D was really good, altough the 10^100 statement was a bit unclear (infinite number of turns worked as well :p)

But gosh, problem B was a nightmare and it seemed terrible tbh, like i think that excluding the case where max_appearance of a number < k would have made it a perfect 1000-1200 B problem. C was easier than B.

I didn't have time to think on E or F, but my guess is E was solved using DP but F i dunno

Thanks for the round yet again! Waiting for that editorial.

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

    Haha, I actually think difficulties worked out surprisingly well. When I solved C (it was B at the time), I said Vovuh it's really hard for B (and for C, tbh). He told me the less complicated solution, but still. After that E was added and I felt it was even easier than C. And it turned out, Vovuh was about right about all the difficulties (considering B had hard to understand statement).

    • »
      »
      »
      7 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I got C really quick but i don't know if my solution was optimal. I still think C was a better B. Now i tried an easy O(n^2) solution for B and it worked....During the contest i was so sure it wouldn't work that i didn't even try it. Pff, in my country, the complexity, time limit and things matter so much, i wouldn't even think about these types of solutions.

    • »
      »
      »
      7 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      unfortunately , till now I can't understand B but luckily get solution for C .

      I think this div3 contest is more harder than last div3 contests that prepared by Vovuh . he has kill my dream to be pubil hhh . but , in general great thank's for his effort and great conests ^_^

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

could anyone explain problem F?i have no idea about it,thanks.

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

    After some precalculations, one can do bitmask DP to find the maximum answer 48133701

    My recurrence relation was DP[mask][first line][last line]

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

      You could write a backtracking with randomized order. Solution

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi, Could anybody help me what is wrong in my solution for problem D Solution

Thanks!

  • »
    »
    7 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    it is because your code make more changes than the minimum.see my code

    • »
      »
      »
      7 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I didn't get how the number of changes are more.

      What I have done is that increasing count of 0 first, then of 1 and then 2(whichever is necessary). As soon as the count becomes n/3 for all 3 values, I stop making changes. So how are the changes more than the required minimum value?

      Giving a counter case of small size will be helpful for me to understand.

»
7 days ago, # |
  Vote: I like it +1 Vote: I do not like it

why this solution on A, didn't get TLE while its running a for loop of n, where n can be as large as 2e9?

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

    Compiler optimizations

    • »
      »
      »
      7 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      can you explain more please? do the compiler translate this kind of stuff like for loops calculating sum of numbers 1 to n, or similar things into an o(1) pre-process refrencing?

      • »
        »
        »
        »
        7 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Compiler optimizes simple stuff and makes them O(1). Given that CF is very fast, such solutions will pass system tests too

        • »
          »
          »
          »
          »
          7 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          thanks

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

          It's not O(1). It's O(N), however, the operations done in the loop are very simple and C++ is very fast in those situations. It's possible that the compiler does some optimizations like loop unrolling, but it's still O(N).

    • »
      »
      »
      7 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      can you explain bit more?

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

    So his solution has a loop of size 2 × 109 which the compiler optimizes for him. And he overflows 32-bit integer which does not matter since we're only interested in the last bit.

»
7 days ago, # |
  Vote: I like it -26 Vote: I do not like it

I cannot understand, why this Div.3 was about 2 times harder than last Div.2, and even others

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

    i am agree with you for problem b.but others are not really hard.

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

      Problem B was terrible and F was too hard for Div.3 imo Others were right

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

        Problem B is not that terrible if you think in the right way. It's pretty easy to check if there is a way to give them a color or not. To choose the colors you can, sort the values, iterate through them and give them an increasing color using modulo.

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

In Open Hacking Phase, If I hack someone's solution, How will it effect my ranking. Also, Can someone explain the role of penalty.

  • »
    »
    7 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If you hack someone's solution, you (may) climb 1 place. Your ranking will increase(or decrease, in case you get hacked).

    Penalty is meant to separate contestants with the same amount of problems solved.

    • »
      »
      »
      7 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can someone explain,How penalty is calculated ?

      • »
        »
        »
        »
        7 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Sum of times in which you get accepted + 10 minutes * amount of wrong submissions

        • »
          »
          »
          »
          »
          7 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thank you for making things clear.

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

Aren't they the same?

48146681 48149357

»
7 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Thanks for nice problems, Vovuh!

Too bad I couldn't translate my solution for F 48149115 from python to C++ in time (got it accepted late by several minutes with 48154003) :'c

By the way, I know that Codeforces community mostly code in C++, but wouldn't it be better if there were different TLs for different languages, as on HackerRank?

I understand that such a change requires a lot of resources (both human time and hardware) and, probably, is not in the priority queue of Codeforces' developers (or have a low priority).

I also haven't searched Codeforces for the discussion of this idea, so maybe there is already a consensus that such a change won't be introduced, (in this case I kindly ask you not to dovnvote my comment as duplicate), but otherwise it can be food for thought for the amazing Codeforces team.

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

    this would give an advantage to python coders, because coding in python may take less time than coding the same solution in c++ because of built in functions, simplifications, etc;

    • »
      »
      »
      7 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      First, in order to use something you should know about it, and I think that it is a good idea to reward any such knowledge.

      Second, all less or more advanced C++ contest programmers have a lot of pre-written code that somewhat equalize the powers. Not to mention that there is a lot more code online implementing different algorithms in C++ (e-maxx is a nice example) than in Python.

      By the way, writing Python code is not always easier than writing C++ code.

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

    Those time limits are incredibly difficult to get right — HackerRank has many problems where writing a suboptimal solution in a slower language actually nets you more points, which is pretty counter-intuitive. This system, while harsh to slower languages, minimizes the work testers / setters have to do and has fewer slow solutions unexpectedly pass.

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

    In "Baekjoon Online Judge", Korea's biggest online judge, we can submit in about 40 (Not quite sure the exact number. Different compiler version counted.) different languages and they all get different time and memory bonuses. For example, if C++ solution has TL x second and ML y MB, all python solutions will judged with TL (3x+2) second and ML (2y+32) MB. Kotlin Native solution will be judged with same TL with C++ and (y+16) MB ML.

    This is great for python coders and most of JAVA coders. However, this had also made countless problems too. There are a lot of problems which something like in C++ you'll get TL with naive solution but with python you can actually fit the naive solution.

    To solve this problem, community members make harder datas or even "temporarily change the TL/ML bonus only for that question". This actually happens a lot. Then the system rejudges every single solution submitted for that problem — which is possible because it is online judge, not a competitive programming platform, and There are only 1/4 problems there.

    Baekjoon Online Judge holds Competitive Programming contests like codeforces gym, and to avoid these problems some setters just ignore the BOJ basic policy and make sure that the contest will ignore TL/ML bonuses (and it is allowed for setter to do so).

    I believe it is not only extremely difficult in terms of resources, it may have some unintended results which in Codeforces it will be harder to fix.

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone tell me the error in this? I don't see any difference between my output and the answer for Testcase #6 (as far it's visible on screen). Submission

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

    Maybe I am missing smth obvious, but can you explain me why you don't one-- here:

    for (int i = 0; i < n && zero < k; i++) {
        if (chars[i] == '1') {
            chars[i] = '0';
            zero++;
        }
    }
    

    It looks like you are using one after this loop, and therefore it should have a correct value.

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me with problem B?The verdict says its wrong on test case 1 which is 4 2 1 2 2 3 my code has given output NO but on my laptop its running correctly. i really am confused about this..i checked others (successful)code as well the logic is same as mine. what is really shocking to me is how my code is giving a different out put on my pc and different on codeforces. the link is herethis

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

    Second for loop "i" is reaching the number 5001 and checking if (hash[i] > k), while the maximum index of that array is 5000 as you defined it. the index is out of bound , so it is calculating the wrong number and flagging it. it works on some compilers and on others it doesn't. fixing this should let you pass the first test.

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

    From line 16 to 27: you are traversing the variable i from 0 to 5001, which caused a certain undefined behavior / memory violation since element hash[5001] didn't exist.

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

      Yeah got it thanks!!Totally overlooked it and i dont know why my compiler didnt give a wrong output.

      • »
        »
        »
        »
        7 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        The name of the problem type said it all — "undefined behaviors". Thus, different compilers might behave differently, sometimes correct, sometimes not. One assurance you can make for yourself is to test your solution on "Custom invocations" tab of Codeforces.

  • »
    »
    7 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's undefined behaviour, happens on your second for when you access hash[5001]

»
7 days ago, # |
  Vote: I like it +1 Vote: I do not like it

I saw an accepted code for the problem 'A' in which he/she uses a loop to calculate counter.LOL.I thought to hack it but then normal test cases are also of that order and the program passed for it as well. I have no idea.

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

48157132 — what am I doing wrong? :(

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

    You cannot simply divide the answer by 2 in the last line, since such division might not work.

    For example: if the true answer before dividing is 998244354, if you divide its modulo, your output will be 0 instead of expected 499122177.

    To do this, you'll need to multiply your answer by modular inverse of 2 by modulo 998244353. Remember to take the remainder of the product again (since obviously there is a high chance that it might exceed 998244353).

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone explain me the problem B please ? I can't understand it through the contest

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

anyone thought about problem E in a DP approach?! is it possible to form the states ?

»
7 days ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve F?

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

    DP+Bitmasking. DP states are mask,last row,starting row.Here mask represents which rows are selected and cannot be selected again.Starting row represents the first row and last row represents the row of previous position.

    • »
      »
      »
      7 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you elaborate more ?

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

        We will use 0-index array, so row index are from 0 to n - 1, column index are from 0 to m - 1.

        For each choice, to calculate the acceptable of table we need to calculate minimum of |ai, j - ai - 1, j| and |ax, k - ay, k - 1| where x and y is first row and last row. So we realize DP state should have first row and last row.

        Assume we have a DP state (x, y) and we want to add a row z behind row y. Then we want to make sure row z doesn't appear in above state. So we should add a binary state which tells you which rows are used, because number of rows is small. Then the DP state is (x, y, p) (1 ≤ x, y ≤ n, 1 ≤ p < 2n). We call it fx, y, p.

        If we let fx, y, p be minimum of |ai, j - ai - 1, j| and |ax, k - ay, k - 1| of a table with state (x, y, p), it would be impossible to calculate fx, z, q depends on fx, y, p. In fact, fx, y, p should only be minimum of |ai, j - ai - 1, j| of table with state (x, y, p), and minimum of |ax, k - ay, k - 1| can be calculated later.

        For each pair (x, z), we iterate all states (x, y, p) which bit x and y are represented in p, while z is not, and fx, y, p exists (has been calculated). Then p' = p + 2z and f(x, z, p') = max(f(x, z, p'), min(f(x, y, p), min(|ay, i - az, i|))). Result is min(fx, y, 2n - 1, min(|ax, k - ay, k - 1|)). We can see from the formula above that if fx, y, p has been calculated, then x and y must be represented in p, so we don't need to check x and y.

        To initialize DP state, we assign all value to  - 1, to show that these value hasn't been calulated.The only value we know is fi, i, 2i and we should assign them to (notice our DP formular). When n = 1, f1, 1, 1 = ∞, but it doesn't matter because we can iterate in last step to calculate result, since 2 ≤ nm.

        I want to warn you of iteration order. We should iterate the binary state first to get correct answer. It seems to give us correct order of DP. I haven't figured out why iterating x and y before p could give wrong answer. I think it due to the way we treat which DP value is calculated.

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I want to be an expert in this round :D

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

My solution for E:

1) We will start filling array b from the left as we know b[1]=0, we can either increment this 0 in the next element in b array or not (as stated in the third condition)

2) if we think about the second condition (if a[i]=a[j] --> b[i]=b[j]), we notice that not only b[i]=b[j], but also all b[i]=b[k] ; such that i<=k<=j, as we cant decrement as we move from left to right. Let's call elements from index i to j 'connected component'.

Consider this example:

1 2 3 1 3 2 10 10 10

b[1]=b[4]=0 (first & second condition), so if we have b[3]=1, then the third condition is violated

The solution depends mainly on the number of these 'connected components' that must have the same value in array b, in the previous example we have 2 components. First one is: (1 2 3 1 3 2) , Second one: (10 10 10)

So how many ways are possible? Thinking of it like for every position we can increment or stay constant (2 choices). Then, the answer is just 2^(CNT-1), not 2^(CNT) as we can't increment in the first connected component, it must be 0.

Remember to use mod, correctly count number of connected components.

My submission link: https://codeforces.com/contest/1102/submission/48158289

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone share your idea of problem D? Thanks :)

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

    Basically we count the 0's 1's and 2's.

    they should all equal X = (the string length) / 3;

    if not then we swap these depending on the best lexicographical outcome.

    • if the 0's are more than X then we need to swap some 0's to 1's or 2's, and the best way for lexicographical order is to swap the last 0's from the string because the 0's on the left assure a smaller lexicographical string, if we are missing both 1's and 2's we swap the 1's first because the 1's also assure lower value, after that we swap to 2's , else we just swap the number that is lower than X.

    • if the 1's are more than X then we swap the first 1's with 0's -**IF (0's are missing)** — and then swap the last 1's with 2's — IF (2's are missing).

    • if the 2's are ore than X then we swap the first 2's with 0's — IF (0's are missing) - and then NEXT first 2's with 1's — IF (1's are missing) .

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

      Well A-m-z :). Nice explained. But I don't understand if 0s are more than 1,s and 2,s why we try 1,s swap first. Since we want lexi. minimum string we should try 2,s swap first. :) Anyway Thanks :)

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

    I'm too lazy for write the proof, my solution use a greedy approach, i put the numbers in order (0, 1, 2) of course if is necessary to put them (cnt(#i) < n/3), and can be generalized for k digits instead of three. 48136350

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

I guess Mr. Vovuh purposely gave weak testcases in B. Array K-Coloring. This is bad, users are not given to chance to improve during the contests. They solve and move forward.

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

    Todays problem B was also slightly bad statement(hard to understand). It should be Problem C. Vovuh should understand people will surely attempt problem B first then they go for problem C. In my opinion problem C was too much easy than Problem B. Hopefully Vovuh will understand and next time we will get better contest. Thanks Vovuh for this type of contest. Its really helpfull contest for beginner. :)

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

    B has a simple solution, I(and probably the problemsetters too) don't get why people tend to overcomplicate things for problems like A and B which can be solved with naive solutions most of the times.

    For example, even though I obviously know how to solve B in O(n log n), it wasn't needed in this case, and O(5000^2) works fine enough and it's simple to write.

    Also, in the end, no matter how strong the initial tests are, they are still pretests so fails can come at any problem

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

    Oh yes, I made weak tests in purpose! Of course! OMG... How this thought comes into your head?

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

      I figured it out, luckily i tried tc#21 (hit & trial), that made my solution fail only because of 0 instead of 1... Mr. Vovuh this time u set all brute force problems, i was expecting some data structure problems. And yeah that profile pic, i am inspired by u.( i love cats(they are mean))..

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

    You just said B was easy to understand?

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

    It's only the problem of weak testcases, not incorrect problem statement. Thus, it's your fault that your solution got hacked or failed system test. Practice more, and try to map out every possible case within your mind.

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

      Yes, i was aware of getting hacked/failed so i submitted twice..And yeah that tc in my mind which made my 1st solution fail, i applied it to every users solution.. And see, i hacked 14 solutions.(two valid submissions of a single user;P)..

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

I am getting a runtime error (exit code 3) on test 5 for problem B.

https://codeforces.com/contest/1102/submission/48162017

Can someone tell me where the error is caused? The testcase isn't being shown completely since it's too big. I considered a vector of sets and tried to insert the numbers and stored the equivalent locations in l.

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

    Line 61 in b.at(j)

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

      Thank you for your reply. I checked the value of j with the watch(x) function #define-d and saw j's range is [0,k-1]. b is a vector of size k, so b.at(j) should be ok, I think. I'm not able to find out what exactly is going wrong. Can you please explain?

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

        I tried it on my computer with 5000 200 and 5000 random numbers and it worked, I didn't get a runtime error

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

What do I get for one successful hack?

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

 You're crazy and I'm out of my mind

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

Hello, for this submission (48133245), I think it outputs a redundant character at the same time after outputting the answer. It passes the test point. I am not sure whether this submission is correct or incorrect, or checker does not solve this problem completely.

Thank you!

Time: 15 ms, memory: 156 KB Verdict: OK

Input
4 2
1 2 2 3

Participant's output
YES
1 1 2 1�

Jury's answer
YES
1 2 1 2 

Checker comment ok Ok
  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you're correct!

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

    I guess that's a null-character, and the checker probably ignored it or considered it as a whitespace.

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

Do we have system testing? Run all hacking test to all competitors?

»
6 days ago, # |
  Vote: I like it -13 Vote: I do not like it

Yesterday's contest : ABABBD

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

When will the ratings change?

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

Though some people have already asked above, still I din't get it. How to solve F ? .
P.S: Please care to elaborate your solution .

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

Yeah, Im Expert now xD :D

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

What happened to good ol' editorials?

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

    I think, it would be a great idea if blue/purple/orange/red guys that solved all problems during the contest will write editorials. I mean, for div3 and div2 contests, there are a lot of people who could do that. For div3, even I can write an acceptable editorial.

    It's also hard for Vovuh to write every editorial, it's really exhausting. Moreover, writing editorials will increase your contribution (if someone is interested in it).

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

Could anyone give me a solution for problem B?? It was terrible

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

    https://codeforces.com/contest/1102/submission/48132783 I put first k colours to the first k numbers. Then I start iterating over remaining elements and create variable cur initialised with 1 and check if 1 hasnt been used for the same number before by using hash. If it isnt simply put cur in the answer for that element. Else increase cur.If cur>=k at any time answer as false.

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

can anyone explain question E clearly ?

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

In problem E..submission made in C++14 using unordered_map gives tle..

https://codeforces.com/contest/1102/submission/48176297

while same submission using map gives correct verdict

https://codeforces.com/contest/1102/submission/48176416

Is there any way to know when to use map and when to use unordered map as in both cases pretest are passed!

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

    You just need to understand what each of those data structures do. unordered_map implememts a hash table and, as such, it takes contsant time per operation on average BUT linear time in the worst-case.

    Cleverly designed anti-hash tests can be conceived to force the worst-case scenario (and this is very likely to happen with 12-hour open hacking). There are some tricks you can do to get around that though (you can find countless threads about this on codeforces).

    map on the other hand implements a BST and, as such, will run in logarithmic time in both average and worst case scenarios.

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

    Maybe it'll get away with hashhack.48279914

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

Anything wrong with the standings?

My contests in profile says my rank is 14 and the current standings says it's 6th.

What's going on? :P What Abracadabra is that? xD

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

    Remember that only the trusted participants of the third division will be included in the official standings table.

    Take a look at the link to see the criteria for "trusted participants". There might be users, which are still eligible to have this contest as rated, but do not fulfill the "trusted participants" criteria.

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

    Thanks Akikaze for your response. I'm quoting the important part collected from that link if anyone's interested to know as well.

    " Accounts that materially participated in less than 2 rating rounds (materially means solved at least one problem there) before the start of the Div. 3 rounds, and those who have ever gained 1900 or more rating units will not get into the official standings and will be assigned to separate rooms. However, this does not mean that there is no rating recalculation for them. Thus, the rating will be updated for all users whose rating is strictly less than 1600 at the time of the start of a round."
    
»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

48184426 I am getting TLE on testcase 48 of problem E. Can anyone point out what can I do to improve it?

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

When will this Vovuh get free from his evil cat and upload tutorial? Plz upload fast.

»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Why the problem E is "Time limit exceeded on test 48" if i used "unordered_map", but code is right if i used "map".