MikeMirzayanov's blog

By MikeMirzayanov, 6 years 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
  • +137
  • Vote: I do not like it

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

»
6 years 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

  • »
    »
    6 years 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.

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

      okay , I will try to solve them thanks :D

      • »
        »
        »
        »
        6 years 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 :)

  • »
    »
    6 years 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)

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

Are contests of div 3 always same educational?

»
6 years 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?

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

Hope it won't be Readforces round! :D

»
6 years 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 :( :(

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

The time is too bad !!

  • »
    »
    6 years 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!

»
6 years 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 ?

»
6 years 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!

»
6 years 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!

  • »
    »
    6 years 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

  • »
    »
    6 years 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.

    • »
      »
      »
      6 years 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.

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

        "Read the problem statement more carefully"

        • »
          »
          »
          »
          »
          6 years 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.

          • »
            »
            »
            »
            »
            »
            6 years 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.

            • »
              »
              »
              »
              »
              »
              »
              6 years 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

              • »
                »
                »
                »
                »
                »
                »
                »
                6 years 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").

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 years 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??

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 years 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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 years 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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 years 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.

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

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

      • »
        »
        »
        »
        6 years 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?

        • »
          »
          »
          »
          »
          6 years 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.

          • »
            »
            »
            »
            »
            »
            6 years 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...

            • »
              »
              »
              »
              »
              »
              »
              6 years 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..

              • »
                »
                »
                »
                »
                »
                »
                »
                6 years 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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 years 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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 years 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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 years 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!

»
6 years 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

»
6 years 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 ..

»
6 years 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.

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

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

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

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

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

»
6 years ago, # |
  Vote: I like it -18 Vote: I do not like it
The comment removed because of Codeforces rules violation
»
6 years 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?)

  • »
    »
    6 years 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.

»
6 years 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

»
6 years 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?

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

When the editorial will be added?

»
6 years 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?

»
6 years 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

  • »
    »
    6 years 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.

»
6 years 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

  • »
    »
    6 years 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.

    • »
      »
      »
      6 years 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.

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

    I did it for like 2.5 hours. Problems are very easy there. It's more like div4.

»
6 years 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

  • »
    »
    6 years 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...

  • »
    »
    6 years 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.

  • »
    »
    6 years 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.

»
6 years 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?

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

    Thanks, I'll fix it soon. But now there is awarding ceremony of internal contest in Saratov State University. Fixed!

»
6 years 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!

»
6 years 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.

»
6 years 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?

  • »
    »
    6 years 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 :)

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

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

  • »
    »
    6 years 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]

»
6 years 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?

  • »
    »
    6 years 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.

  • »
    »
    6 years 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).

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

      ohh my my , ok thanx , got that.

»
6 years 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

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

    hacking doesnt give any extra points.

    • »
      »
      »
      6 years 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

»
6 years 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).

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

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

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

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

»
6 years 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

»
6 years 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.

»
6 years 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 :|

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

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

»
6 years 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.

  • »
    »
    6 years 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.

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

    1000000001 is correct.

»
6 years 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

»
6 years 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?

  • »
    »
    6 years 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.

»
6 years 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.

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

Where's rating changes? Any announcement about it?

UPD: Fixed!

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

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

»
6 years 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

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

Soemthing strange is with ratings of participants..