MikeMirzayanov's blog

By MikeMirzayanov, 2 weeks ago, translation, In English,

Hello!

Codeforces Round #481 (Div. 3) will start on May/13/2018 12:05 (Moscow time). It will be the second Div.3 round in the history of Codeforces. You will be offered 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.

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.

The problem are written by me and fcspartakm. Many thanks to testers AGrigorii, BigBag, nhho and Sert!

Good luck!

UPD 1: Thank you for participation. Problem tutorials have been published.

UPD 2: Congratulations to the winners! Top-5 (official standings):

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

»
2 weeks ago, # |
  Vote: I like it -65 Vote: I do not like it

»
2 weeks ago, # |
  Vote: I like it -79 Vote: I do not like it

I hope less "dfs and similar" and "dp" and more "implementation" . thanks :D

  • »
    »
    2 weeks ago, # ^ |
    Rev. 2   Vote: I like it +30 Vote: I do not like it

    You're probably the first person to ever say that

    Also, some of the easier problems with those tags aren't very different from implementation problems.

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

      okay , I will try to solve them thanks :D

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

        Don't have that kind of attitude. You learn much more from graph, dfs and DP problems rather than implementation problems. Learning is more important than getting AC :)

      • »
        »
        »
        »
        12 days ago, # ^ |
        Rev. 2   Vote: I like it -33 Vote: I do not like it

        what noob you can't understand such simple concept as a graph? Or are you too scared to try them?

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

    Why do you think that dfs is simpler than 2x2x2 Rubik cube rotation? (there was such a problem on CF)

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

Are contests of div 3 always same educational?

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

will it be possible to do the problems after the contest has ended?

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

Hope it won't be Readforces round! :D

»
2 weeks ago, # |
  Vote: I like it -7 Vote: I do not like it

Why the unusual time? Finally on a weekend, but in the middle of the night :( :(

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

The time is too bad !!

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

    I am a Chinese, the time is really good in China! It is 17:05, I can race who can solve problem faster with my friends!

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

      so good luck : ) , don't let anyone hack you!

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

Hope problems will be interesting.

»
2 weeks ago, # |
  Vote: I like it -19 Vote: I do not like it

why this bad time please make it like usual or after two hours at least:(

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

I hope problems of this round will be little more harder than the previous Div-3 round & rounds by MikeMirzayanov are always interesting. Good Luck & Happy Learning to all Div-3 participants.

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

Are the submissions only preliminary tested during the 12-hour open hack phase or are they system tested before the open hack phase begins?

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

What about Educational Round ? Will that round continue or Div3 is the replacement ?

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

    No, there will be educational rounds

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

Last weekend was also a div3 contest. That would be great if we could alternate between div3 and div2 contests on the weekends!

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

Why do you guys each time override the rules and create ambiguity, by saying "it's only for trusted participants", then, "regardless of whether you're trusted or not, if your rating < 1600, it'll be rated for you". Why do you even bother to mention "trusted users" or that it's to combat unsporting behaviour? In fact, it's not!

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

    ???????? Trusted participants are in the official standings table and it's rated for everyone currently under 1600

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

    "Why do you guys each time override the rules"
    They don't. last (and first) time was absolutely the same rule.

    "Why do you even bother to mention "trusted users" "
    Because it's about being included in the official standings table.

    "In fact, it's not!"
    In fact, it is, lol.

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

      You have no idea of what I'm saying! Read the first sentence once again till the end.

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

        "Read the problem statement more carefully"

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

          Can you tell me where is the “official standing” which only includes trusted users? I see everyone gets rated including unrated ones and the ranking takes them into account.

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

            Official standings table dosen't mean people who gets rated. Official standings table is a public table, which shows standings of the contestants who took part in the round. And from this table, because of new rules, they remove untrusted users. So they become invisible for public and there is no point in participating for the high places, like most does.

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

              Can you share the "official standing" link for the last div3 contest? I can see everyone in "common standings", and in the rating changes, I see "those" unrated ones included. So where is that "official standing" which has only the trusted users? Please share it for the round #480

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

                You're welcome (use right click — "open picture in the new tab").

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

                  Am I the only one who can still see some unrated accounts in the official standings??

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

                  Well, for some reason I now see them too. But, "Milhous", who actually won contest, still not here, which means for some reason this two guys suddenly become visible. Maybe bug, maybe intentional.

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

                  Yeah I think it makes some sense to be like this since hacking is still going on. Remove them from the standings table after hacking finishes; otherwise, their solutions are less likely to get hacked.

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

                  We are talking about round 479, which ended a long time ago, so.

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

                  Oh whoops you're right, my bad. Yeah, they shouldn't appear,

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

        I got your point exactly. Why don't you reread me instead?

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

          I can’t “reread” you sorry )))

          Just to say that by saying overriding rules I didn’t mean the rules are different from the previous div3 contest, but I meant that he first says that it’s rated only for trusted users (excludes unrated users), and then says that if you are < 1600, then you will be included. This is my question.

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

            "but I meant that he first says that it’s rated only for trusted users (excludes unrated users)"

            Where? I think you are the one who needs to reread...

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

              a. 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.

              b. 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.


              doesn't b. override a. condition? Either I'm missing very basic info, or it's confusing..

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

                a. portion does not say anything about rated status of the contest.

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

                  Share that "official standings" for round #480 which considers only trusted users. I can see all the unrated participants show up in the standing.

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

                  Shared it higher. But why are you asking round 480 btw? This rule works only for div3 round, not div2.

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

                  Yeah I noticed, thanks for that. Seems like I never realised "show unofficial" checkbox and it was left checked=true so I wasn't able to get what the statement above was saying. But I finally got it and can sleep comfortably :) Thanks for your time!

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

Although I rarely miss a CF round , I guess I will miss tomorrow's contest because I have to attend a national contest at that time :-(
Last one was Round #466

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

There will be held a great national programming contest tomorrow in Bangladesh at the same time while codeforces contest will be start.About 70% of Bangladeshi regular codeforces problem solver will be attend to the national contest. I'm requesting the codeforces authority to Retreat Codeforces Round #481 (Div. 3) for 2 hours. If this's been done, many regular Bangladeshi coder will get the chance to attend in Codeforces Round #481 (Div. 3). Thank you. national contest link : https://toph.co/c/lu-ict-fest-2018

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

ops .. i can not join you . .

we will have our university acm

albaath contest

so ... i am very sad ..

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

How can I be 'trusted participants'.
I meant: I already take part in more than two rated rounds and I also have rating less than 1900.
But when I register, it alert like I'm not rated in this round.

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

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

I so hope this is rated!!

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

Oh!! Div-3 saved my coding career!!

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

Too Hard... 42mins to solve all problems...

»
12 days ago, # |
  Vote: I like it -18 Vote: I do not like it
The comment removed because of Codeforces rules violation
»
12 days ago, # |
  Vote: I like it +27 Vote: I do not like it

I feel that the difficulty of the contest should be a little more than it currently is

Pre-system testing, 250+ trusted participants solved all the questions, which is around 10% of all the trusted participants. This never happens in Div2 or Div1, so I feel that even for Div3 standards, the whole problemset might be on the easier side. (Maybe the last 2 questions should be harder?)

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

    That is what div 2 is for. Soon they will rank up to where they can't take part in div 3 and all is good. Obviously there will be some imbalance while people get adjusted into their new divisions following the recent rankings changes too

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

    Agreed. Although having speed be part of the contest is inherently part of competitive programming, somebody who is very good at solving problems but codes slower should still be able to achieve a fairly high score on the leaderboard.

    Having the problems be too easy also introduces a lot of variance on the leaderboard.

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

I solved E F G each in about 10 minutes but in the last 30 minutes I couldn't still solve D... I think D is harder than the last 3 problems

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

    What is test case 7 for D? I couldnt pass it :(

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

      Actually, I solved D, I was talking about E. D is not that hard.

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

    There is a simple trick in D. You can find it. Try again to find that trick.

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

    D is not harder...U r just a noob...cant see easy things lol

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

I'm not able to attempt hacking any problems. It says on the right that I am doing the contest as practice, although I participated in the round and am under 1600. Can someone help?

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

When the editorial will be added?

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

Test case 7 for E anyone? Is it legit to ask for test cases now?

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

hi everyone . I am a new codeforces user. I don't have any information about hacking. Can someone give me information about hacking

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

    Click the user's solution twitch time to open his/her solution.

    Then click the hack option. And figure out such a case that case will

    Give an output that output does not match with correct output.

    If don't match with correct answer hack will be successful otherwise hacked will be

    unsuccessful.

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

Solved all problems in both of the Div.3 contest. I think it should be a little bit harder :D

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

    At the same time, Div 3 isn't meant for you though, since it isn't even rated for you.

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

      At the same time, old div2 was not meant for candidate masters but they struggle to solve all the 5 problems.

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

can anybody tell me why this is wrong on pretest 3 in problem G it seems correct to me . 2 2 2 1 1 3 4 0 4 4

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

    Exam 3 starts later so you can't prepare for exam 3 earlier...

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

    You can't study for an exam until the questions get released.

    In this case, the questions for Exam 3 get released on day 8, and you're trying to study for them on day 6.

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

    You studying for exams before questions are released....so pro much wow

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

    You can't start preparing for the test before s_i, which is in this case 8.

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

open hacking phase is running

But I can't open others codes why?

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

I can only hack my code. Can anyone tell me what's happening?

UPD: It's fixed now!

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

I have participated in more than 2 rated contest and my rating is less than 1600 but still I am not able to view other's solution and try to hack them.Why is this happening.

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

I used DP in problem D Almost Arithmetic Progression, but i am getting RTE on test 5. can someone look at my code and tell whats wrong? http://codeforces.com/contest/978/submission/38185985

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

Can someone look at these 2 solutions of C: 38161183 38162269.

The first has complexity O(k*k) the second O(k*logk) and yet the second takes 1.5 s more?? What am I missing?

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

    38161183 is not O(k^2), it looks more like O(m) to me (m being the number of letters): p is not reset after the inner loop, it just catches up, at worst in n inner iterations per outer iteration, but in constant time on average per inner iteration (n/m inner/outer iterations).

    Edit: please ignore the last brainfart. It is how Photon_ says :)

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

      I didn't read the queries were in increasing order :D

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

    Complexities are actually O(n+m) and O(m*lgn).

    On solution #1 it uses 2 pointers, so in worst case, you will traverse whole array a over all m queries hence the running time is O(n+m)

    On solution #2 it uses Binary Search over whole array. In worst case all queries will be in the start of array a so this solution will take O(logn) for each binary search hence the total running time will be O(m*logn)

    You can improve second solution to binary search not in [start, end] but in [last_pos, end]

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

please explain the 4th case of E please please please

2 10 -1 2

why us the output 9?

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

    There can be [1, 9] people on the bus before the first stop; if there were 10, after the second stop there are 11, and there has to be at least one before first stop.

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

    it could be 1 to 9. it can't be zero because after the first bus stop -1 remains. it can't be 10 because after the second bus stop there are 11 person in the bus and its more than limit (w).

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

      ohh my my , ok thanx , got that.

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

I think this guy (__123456__) is cheating he used special conditions to hack his codes

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

    hacking doesnt give any extra points.

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

      i know but maybe there is announcement for the top hackers & this will be unfair for the real hackers

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

I think it could've been more interesting or challenging if the duration were 2 hours (not 2.5 hr).

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

Why ProblemC need binary search? b_j is in increasing order.

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

Got "unexpected verdict" in hack 448105, 448122 and 448145.

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

Can any one help me in Problem C ? I think my code is correct but can't understand why it fails.
LINK : http://codeforces.com/contest/978/submission/38163975

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

    change MAX = 100010 to MAX = 200010.

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

      Is it only me or everyone else is also facing problem of latex Check this link...This is how my problem page looks
      Link : https://ibb.co/c4iQwJ

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

        On both Firefox 59 and Chromium 66 on linux render fine for me. You might have javascript disabled, which could cause this issue.

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

Interestingly, my penalty in both (all :)) of the div.3 contests is 413.

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

It's weird, my Java code passed if I use int, and it failed at test case 5 if I use Boolean and Integer :|

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

    It's not. You should learn how operator == works for objects.

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

Stay away from my solutions hackers

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

The testcases are wrong. The test 21 on problem E is the first one that is wrong. The answer should be 1000000000, not 1000000001.

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

    Nope. There are 1 million and 1 possible starting values. [0, 1 million] inclusive on both ends.

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

    1000000001 is correct.

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

I wonder if the ranking will be updated?

Just curious :D

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

I am not able to understand my rating change. I solved 2 out of 3 problems correctly (A went wrong due to a silly mistake and B, C were correct), but the rating still went down instead of going up?

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

    Your rating is dependent on how better or worse you did compared to other participants. Losing rating means you were expected(in relation with other participants) to get a better rank than what you got.

    You might be comparing your results with the earlier div 2 rounds where in general you would have gained rating on solving 2 questions, but this was an easier round than the previous div 2 rounds and contestants with lesser rating than you did better which caused you to lose rating.

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

It seems that my hacks on problem F (with n = 76297, ID 448348 and two others) weren't added to the final tests. Very nice.

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

Where's rating changes? Any announcement about it?

UPD: Fixed!

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

The rating I gained in this contest is now gone.What happened?

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

Where did my rating go after this contest? UPD. Rating returned

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

Soemthing strange is with ratings of participants..