vovuh's blog

Codeforces Round #479 (Div. 3)
By vovuh, 7 years ago, In English

Hello!

Codeforces Round 479 (Div. 3) will start on May 6 (Sunday) at 14:05 (UTC). It will be the first Div.3 round in the history of Codeforces. You will be offered 6 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.

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 Neon for testing the round.

UPD: Thanks a lot to testers dreamoon_love_AA, eddy1021, step_by_step and Egor.Lifar who agreed to test the problems and found the mistakes. Now we are ready to start the round!

I hope that you will like the problems. If suddenly something does poorly with difficulties of the problems, then we will adjust the difficulties in the next Div. 3 rounds.

Briefly about myself. My name is Vladimir Petrov, I am studying at the 3rd year at Saratov State University and from the high-school I am studying at SSU Olympiad Training Center. In ICPC I participate in the team "Saratov SU Daegons" with awoo and Neon. I like reading and watching science fiction. I’ve read "Song of Ice and Fire" 3 times and wait for publication of 2 more volumes.

Good luck!

UPD2: Editorial

UPD3:

Congratulations to the winners (official results):

Rank Competitor Problems Solved Penalty
1 cMartynas 6 69
2 nimphy 6 117
3 Passenger 6 124
4 mandinga 6 128
5 raffica 6 144

Congratulations to the best hackers:

Rank Competitor Hack Count
1 greencis 36:-8
2 Tlalafuda__Tlalafu 10:-1
3 STommydx 9:-1
4 dalex 8:-7
5 dreamoon_love_AA 4:-3
6 shnk 2

97 successful hacks and 297 unsuccessful hacks were made in total!

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

Problem Competitor Penalty
A kuzmoid 0:01
B peach 0:04
C Milhous8 0:08
D Milhous8 0:11
E s0mth1ng 0:09
F DoveDragon 0:14

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

Comments Comments (159)
| Write comment?
»
7 years ago, # |
  Vote: I like it +32 Vote: I do not like it

What is the relationship between div3 & div2 problems. For instance A div1 is equal to C div2

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

    This contest is for div3 only. I do not think there will be a relationship between div2 and div3. I mean can something be easier than Div2A? Maybe Div3A+Div3B+DivC are so close to Div2A. We will see after the round :)

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

    This contest is only Div3 , so i don't think there's any relationship with Div1 or 2.

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

    "We plan to include in these rounds simple training problems that will help beginner participants to gain skills and to get new knowledge in a real contest."

    → Reply
»
7 years ago, # |
  Vote: I like it +21 Vote: I do not like it

I found a mistake for you :)) Please correct it.

→ Reply
»
7 years ago, # |
  Vote: I like it +8 Vote: I do not like it

So will there have Educational Round like the time before updating? :P

→ Reply
»
7 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Finally!

→ Reply
»
7 years ago, # |
  Vote: I like it +23 Vote: I do not like it

Last three lines was awesome . :D

→ Reply
»
7 years ago, # |
  Vote: I like it +8 Vote: I do not like it

"The round will be hosted by rules of educational rounds..." Honestly, It's really boring! Given that this is a div3 and problems should be easy.. Then what is the use of the hacking phase ??!!

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

    We will experiment with formats of Div. 3 rounds, but there are some reasons to start with rules of Educational Rounds:

    • I prefer Div. 3 participants to solve problems during a round instead of spending time trying to hack
    • for non-trivial problems tests in Educational rounds much more complete than pretests in regular Codeforces round.
    • my plan is that Div. 3 rounds will not affect regular Div. 1/Div. 2 rounds in terms of schedule. It means that Div. 3 rounds (as well as educational) can't use time of KAN to coordinate them. They completely prepared by writers with my little help. It is much easier to write a round by rules of Educational Rounds than Codeforces: issues in writer solutions/validator/checkers affect a round less, less requirements on completeness of tests, etc.
    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +9 Vote: I do not like it

      This is what I have been waiting for long time: "**I prefer Div. 3 participants to solve problems during a round instead of spending time trying to hack**". Hacking is a good way to develop debugging skill. But a div3 participants should not spend the whole time trying to hack a problem just to increase rating instead of solving another problem.

      Thanks Mike.

      → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it -18 Vote: I do not like it

      But what about the feeling of DIV3 participants. I really enjoyed codeforces round DIV1 / DIV2, due to div1 and div2, DIV3 is also should not be affected. div3 also must be same as daily codeforces round not educational type.

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

        As Mike said, div2 rounds are not affected. So you can just ignore div3 rounds.

        → Reply
»
7 years ago, # |
  Vote: I like it +23 Vote: I do not like it

First time I saw about myself in any round announcement.

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

It's rated for me so :D

→ Reply
»
7 years ago, # |
  Vote: I like it +23 Vote: I do not like it

unofficial participator for the first time :) :D

→ Reply
»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Why extended ACM-ICPC? Why not like a normal Codeforces round?

→ Reply
»
7 years ago, # |
  Vote: I like it +44 Vote: I do not like it

Will I become Div.4 user if I lose rating in Div.3 contest?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it -15 Vote: I do not like it

    As of 5/5/2018, there is no such thing as a Div. 4 user. The lowest is Div. 3.

    → Reply
»
7 years ago, # |
  Vote: I like it -14 Vote: I do not like it

Hello, If this round is following Educational Round formats than I want to bring something to your notice. See the picture attached.

My friend solved Problem A and his solution for problem C failed. I solved Problem C and my solution for problem A failed. I just want to point out that Problem C was tougher than Problem A and anybody who solves tougher question should get better rank. I think people will say that it is for learning new skills and I should not concern myself with the rating. But I still think that this is unfair.

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

    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.

    So, I think, there will be no issues with Div3 problems, as at some points, we will figure out that it is eventually too easy, regardless of which problem in a contest (A, B, C, D, E, or even F).

    In other words, soon we will realize none of any Div3 problems will be any tough to be obliged to be distinguished.

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

      Still, the point system is better than the penalty system in my humble opinion.

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

    ACM-ICPC scoring is used in many contests.

    If you don't like the format of educational round, you don't have to participate.

    If you don't want to be rated because of these rounds, you can always do virtual participation of solve problems regardless.

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

      I am fine with whatever format you want to use, I am asking is it fair?

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
        ← Rev. 2   Vote: I like it -21 Vote: I do not like it

        1) You complained about the rules of the contest.

        2) You just said "I am fine with whatever format"

        3) ?????????

        4) Now you ask if the rules are fair.

        Yes, they are since your signed up knowing them.

        As I said, if you disagree with this type of scoring just don't participate. If you are annoyed at messing up on problem A check over your code more before you submit.

        → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

One more chapter is going to open from May 6 (Sunday) at 14:05 (UTC)..!!

→ Reply
»
7 years ago, # |
  Vote: I like it -39 Vote: I do not like it

Div3 => noobs?

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

    once you, too, was thus noob

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

    Hey bro cyan isn't too hot either. We're all noobs, just some less nooby than others.

    → Reply
»
7 years ago, # |
  Vote: I like it +39 Vote: I do not like it

So which one do you like better? The books or the TV show? vovuh

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Looking forward to concise problem statements without unnecessarily long storylines!

→ Reply
»
7 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Div3 finally comes! No more falling scores!

→ Reply
»
7 years ago, # |
  Vote: I like it -35 Vote: I do not like it

tourist do you want to join us in div 3 :) ?!!

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

    don't worry, they'll open div 0 for him

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

    He does not even need to look to the problems to solve them. :)

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

      lol.u can't solve some problem even by reading them :)

      → Reply
»
7 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Will div 3 participants be allowed to take part in div 2 contest?

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

    Obviously...

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

      Will it be rated for div 3 contestants?

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        when it is only div 2 contest then the user who's rating is less than 2100 can participate in this round and when both div 1 and div 2 round will be held , user who's rating less than 1900 can participate in div 2 contest as a official participant.... official means rating will be update

        → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How many problems will be there?

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

Waiting for a DIV2 contest. The sooner, the better. The more, the merrier. :)

→ Reply
»
7 years ago, # |
  Vote: I like it -6 Vote: I do not like it

Problem A : Print "Hello World"

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

HTTP Response: 500, 502. Website failed.

→ Reply
»
7 years ago, # |
  Vote: I like it +50 Vote: I do not like it

20 minutes of penalty is too much.

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

    for a 2-hour contest, indeed. 20 minutes seems better with 3~5 hours contest.

    → Reply
»
7 years ago, # |
  Vote: I like it +11 Vote: I do not like it

AH ? I can't register while the contest is running !

What a pity!

→ Reply
»
7 years ago, # |
  Vote: I like it +67 Vote: I do not like it

20 minutes of penalty is too much.

I used 19min to solve all the problems.

But I got 1 penalty.. doubled the time..

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

    20 mins of penalty is standard ACM rules. It encouages coding correctly instead of coding fast, which I think is ok. Also, the contest is targeted at people who can't solve all problems in 19 mins :)

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

    Penalty is calculated as the sum of times each problem solved (+ 20mins penalties), not as the time of the last solution. So it's not doubled because of that, don't worry :)

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

      You're right.. But I got "502 Bad Gateway" for 30 mins LOL

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

        So? That's completely irrelevant to the discussion. Nobody cares how well you did in a div3 contest, mate.

        → Reply
»
7 years ago, # |
  Vote: I like it +31 Vote: I do not like it

Thanks vovuh for this round , and thanks MikeMirzayanov for Div3 !!! This is the first time that i am able to solve all problems .

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Spending 30 minutes to solve the last problem. Is it a little bit slow compared to how such contestants like me (1800s-rating guys) are supposed to be?

→ Reply
»
7 years ago, # |
  Vote: I like it +25 Vote: I do not like it

Why are there some (not all) unrated accounts in the official standings?

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

    What exactly? Please, give me some examples of such handles.

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

      official rank #1 for me is readers5 and rank #4 T_van for example

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

        That happens pretty often in div2 if not all the time, even in older contests.

        My guess has always been that some of those are smurf accounts created by high rated people just to be on the top spots in a contest. A lot of them are legit skilled people on their first contest, but some are left inactive after one contest.

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

          Yes but the thing is that it's not supposed to happen with the new div3 rounds.

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

            Sorry, you're right. Forgot that.

            → Reply
»
7 years ago, # |
  Vote: I like it -42 Vote: I do not like it

I think this was too easy even for div 3.

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

    I agree. In Div 2, very few experts (the highest eligible rating) solve the set. In this one nearly every specialist and their mother solved it (not really but you get the idea). You never see 200+ eligible participants solve the set in a round.

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

      Yes, It should be a little harder so only about 50 or less gets full. NOT 200. Even me solved the whole set! Maybe it should be for users whose rating less than 1400

      → Reply
»
7 years ago, # |
  Vote: I like it +10 Vote: I do not like it

First time in my whole life! I solved all problems! (but... It is div3)

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

.

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    .

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

      Is there simple linear solution for C?

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        .

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

          In C++, you're right (because there is std::nth_element). But I mean that in many standard libraries, there is sort, but there isn't nth_element. So in this languages linear solution will be much harder.

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

          No, quickselect has a worst case of n^2, similar problem to your sort

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

          Quickselect have O(n^2) worst time, nth_element in C++ have O(n*logn) worst time, but here is Medians of medians algorithm (or Introselect variation), which have O(n) worst time.

          But it's not simple (or not obvious at least).

          → Reply
»
7 years ago, # |
← Rev. 3   Vote: I like it +32 Vote: I do not like it

It seems the difficulty is something like:

Div3 A, B = Div2 A

Div3 C = Div2 B

Div3 D, E = between Div2 B and Div2 C

Div3 F = Div2 C

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

    I think Div3B is too simple for Div2B

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

      Possibly. Honestly Div2 A and B feel more or less the same difficulty, at least in my opinion. Only thing I've seen is that Div2 B sometimes has annoying edge cases, so yeah you're probably right, it's probably A level.

      → Reply
»
7 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Intially i was not able to look at question and was getting a continuous error of Bad Gateway 502

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

:(

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I Accepted F after contest finished 1 sec...

(Sorry for my poor English)

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how can solve the ploblem c?

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

    Sort the elements, and the k'th element (1-indexed) is your answer. If k = 0, then just subtract 1 from the first element.

    The no solution cases are when the k'th element equals the k+1'th element (why?) and when k=0 and the first element is 1, because subtracting 1 would be outside of your range (you may be tempted to try to be clever and subtract 2 so you don't have to handle that case separately, but that fails if the smallest element is 2).

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

      I don't get how, for k=0, there could be an answer different than -1.

      I mean, as I read it, there is no x «such that exactly 0 elements of given sequence are less than or equal to x.», regardless the value of the first element. Am I missing something?

      What exactly do you mean by «because subtracting 1 would be outside of your range»? I guess you refer to the range [1, 10^9], but why should I subtract something?

      Thanks

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

        Say your sequence is 10 26 4, and k=0.

        Simply output the number 3, and that is 0 elements from the sequence are less than or equal to 3. If the smallest element is 1, then there is no answer that is in the range from 1 to 1 billion.

        → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Can E be solved using this logic: LINK

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    if you mean E,E is simple. Just for each connected component see that every node is connected to exactly 2 other nodes.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      I tried this for problem D.

      Take a boolean array check[n] and mark all as false. Then I tried making chains. Take the first element and mark it as true and this will start a new chain. Then for each other false element in array check if it can be added to the chain started by this element, either by appending it to the beginning or to the end. If yes mark this as true too. For beginning, check if the new element divided by 3 is equal to first element in chain or if new element multiplied by 2 is equal to first element in the chain. Similarly we do for the end.

      However, I couldn't figure out how to decide a way to print all these chains in a valid manner. Is there any way to do figure this part out.

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

        I think your approach is wrong or maybe i understood it wrong anyways this is what i did: A move consists of dividing by 3 (if divisible) or multiplying by 2. This means given a number we are taking away 3's and giving it 2's. So a state once reached will never be reached again. Why? Because to reach that state either you need to multiply by 3 or divide by 2 both of which is not a part of move. So what we can do is treat every element as starting element once and try generating the sequence from elements available. If all the elements are used you can just print that sequence.

        → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        This can be done by thinking of an array as a directed acyclic graph, and do a topological sort.

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

          No need for directed graph...just make undirected edges and start from any end that fits into any one of given two operation.

          → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Thanks, antipr000. I got it.

      Can you check out the link I shared? There is a formula given to get the count of all cycles. Is it correct?

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

        No, take the graph

        4 6 1 2 2 3 3 4 4 1 1 3 2 4

        Number of edges = 6. Number of vertices = 4. Number of connected components = 1. 6-4+1=3, but the answer is 2 because there is only one connected component and it isn't a cycle.

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

        it has defined cycle differently not the traditional cycle we know of. See the examples and diagrams.

        → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

was this contest rated as written in the blog ?! "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." I didn't see any rating for the problems.

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

    Ratings will be changed after whet Open Hacks Phase ends (in 12 hours approx)

    → Reply
»
7 years ago, # |
  Vote: I like it +47 Vote: I do not like it

GOGOGOGO SO FST LKE A SNIC X

→ Reply
»
7 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Thnx vovuh for your efforts in making harder pretests. Really Appreciate it ! :-)

→ Reply
»
7 years ago, # |
  Vote: I like it +4 Vote: I do not like it

The round was good! Even though problems were easier quality remained high. It kind of reminds me of Atcoder Beginner Contests.

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

Angel.Yan (rank 578)'s submissions and __beyond (rank 581)'s submissions are almost the same (the differences are libraries, useless fors, spaces, blank lines). I believe they are cheating. Correct me if I'm wrong. vovuh

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

problem C ;

Output Print any integer number x from range [ 1 ; 10 9 ] such that exactly k elements of given sequence is less or equal than x . If there is no such x , print "-1" (without quotes).

equal to not equal than

vovuh

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

    Thanks, but next time please send it via private message.

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please explain why this submission got TLE while this one got AC ? I just changed the language from Java to C++. There was no I/O issue as well. I was clueless about my solution getting TLE and then in just hit and trial I converted it to C++ and it got accepted. :(

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

Is it possible to solve problem E using disjoint set union?

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

    my idea, maybe wrong.

    dsu = new DisjointSetUnionWithRollbacks
for component in componets:
    flag = 1     
    for edge in component.edges:
        dsu.add(edge)
        for edge in component.edges:
            dsu.erase(edge)
            if dsu.numIgnoredEdges > 0:
                flag = 0
            dsu.add(edge)
    ans += flag

    UPD: solution 2

    dsu = new DisjointSetUnion

for component in components:
    [head: tail] = components.edges
    flag = 1    
    for edge in tail:
        if dsu.add(edge) == EDGE_IGNORED:
           flag = 0
    ans += flag

    In fact, we are to check, if after each edge deletion, component becomes tree.

    However, this solution is very complicated.

    Simpler ones:

    1. component is good if each node touches 2 edges

    2. component is good if it contains k nodes and k edges (sorry, it turned out to be wrong)

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

      "2. component is good if it contains k nodes and k edges"

      Actually, this approach is incorrect as this is not a cycle component.

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

      I tried this problem using disjoint set union. If I find a cycle, I checked if the degrees of the nodes having this edge is 1. If they aren't 1, that means that connected component is no longer a valid cycle. If they aren't in the same connnected component, then I check if any of them were part of a cycle. If they were, then I change that value to 0, signifying that the corresponding cycle is no longer a cycle. Can someone tell me what I'm missing here? I got a Wrong Answer on test case 18.

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

Look at what Tlalafuda__Tlalafu does in hacks section (for problem B). He specifically wrote several solutions with this kind of code 

if (n == 3 && t == "LOL") {
    cout << "MEM";
    return 0;
}

And then he hacks himself several times.

Is this kind of behaviour legal in codeforces?

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

Why can't I hack solutions on C++17? The system gave me an "Unexpected verdict" several times on different solutions. Please rejudge all the hacks with this verdict, it is very important.

UPD: I can't even hack my own solutions which aren't on C++17. What's wrong, Codeforces?

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

    Could you please explain the test you used to hack so many F solutions? I tried to find something in common in the solutions you hacked but failed to see the pattern. Your test seems to be tricky.

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

      Div 3 noobs like me didn't know that using unordered_map makes the solution O(N^2).

      http://codeforces.net/blog/entry/44731

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

        So, this was an "anti-hash" test against STL's unordered_map... I'm new to Educational Rounds so I didn't think people actually use dirty tricks like anti-hash and anti-quicksort. I don't get why people do this but this broke all solutions with unordered_map instead of map. Well, learned something new, won't be using unordered_map on contests next time :)

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

          I believe this hack does not necessarily mean that you should not use unoredered_map at all.

          The thing is, the standard hash function which accepts integer values does nothing, it just returns the same number it accepts, so there is no problem with hashing itself.

          The problem is solely with buckets count, because in a hash table there is a remainder operation "key % buckets_count" and in case if you take a lot of numbers with the same remainder, unordered_map will work slowly.

          However, if you use it and call reserve(10000000) in the beginning, you will fix the amount of buckets to be over 10 millions and the hack simply would not work anymore. The maximum time conplexity will not be more than 100n, which is enought to pass 1 second time restriction.

          Correct me if I am wrong.

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

            This wasn't exactly what I meant, but I agree that reserve() will work for F. The problem is that this workaround will only work for this particular problem because of the 10^9 restriction. Given less tight bound (10^18) it will still fail.

            And with 12-hours open tests you can even generate counter test for any particular hash function from universal family (not necessarily identity) and any particular buckets_count. The only way to protect against this attacks seems to be random sampling of hash function from universal family with good source of entropy.

            The point was — why do you even need to bother about such details on a contest if you can just use map instead? It might be a bit slower but at least it has worst-case guarantees and it allows you to focus on a problem itself.

            Problem solving is fun. I don't think it's fun to protect against hashmap-attacks.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              6 years ago, # ^ |
              ← Rev. 4   Vote: I like it +5 Vote: I do not like it

              I see, I would myself prefer map container to make sure my solution will work.

              I was just too disapointed by the fact that a programming contest makes us choose the structure which 10 times faster in 0.0001% cases and 10 times slower in 99.9999% cases, that is why I tried to figure out the way how to use unordered_map and remain unhacked.

              Anyways, codeforces is not only about good ideas of solutions, it also requires us to know the low level of how c++ works, it is just as it is.

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

    I think it's because some of the author/tester solution fail on the same test.

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

    Testers' solutions receive time limit exceed, because of this your hack gave an "Unexpected verdict". I hope I have fixed it now. Sorry for long delay.

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

Will there be any tutorial for this round??

→ Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

i passed all of the problems!! yayyy

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

When will system testing start?

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

    Yeh same question,i wonder how can i know when the sys test will start ? the contest just said "Finished"

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

When will the ratings be updated?

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

Pls, somebody explain, how my solution http://codeforces.net/contest/977/submission/37965169 for Problem F was hacked. But when i changed "unordered_map" to "map" it got accepted. It seems realy strange to me

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

    Afaik Unordered_map is slower than normal map.

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

      That'_s not true. unordered_map is getting slower when many hash collision happens. Otherwise, unordered_map is much faster than normal map.

      → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    unordered_map is based on Hash table. Normally a search operation of hash table works in amortized(1) but worst is O(N) (caused by hash-collision). std::map, on the other hand, is based on red-black tree, which has O(logN) complexity in search operation on average. Your solution was hacked by anti-hash test.

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

Why unrated participants get rated in this round?

You said that they need to do at least 2 Div.2 contest and solve at least 1 problem to get rated

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

    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. So although unrated participants are not trusted, they are still rated.

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

      But why they but them in a separate room?

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

Can anyone tell me what's wrong with my F approach? 37990081

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

    You ignored MAP[A[i]] that was originally stored.

    test : 9 10 11 12 8 9 10 11 10 11

    ans = 4 yours = 3

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

      Oh.. i thought map in c++ overrides values that exists already just like in Java

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

    Yes, so change your "//m.insert(mp(a[i], m[a[i] — 1] + 1));" to "m[a[i]]=max(m[a[i]],m[a[i]-1]+1);", and this is the AC code which has a little change from your code

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

      Yes, i got AC, thank you ;)

      Thought C++ maps work as Java maps where you just use map.put(v1, map.get(v1 — 1) + 1) and it overrides v1 value if exists

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

How about the ratting changes? Can a people get the same ratting changes if he got the same place(among rated people) in div 2 and div 3 contests?

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

It's a wonderful effort for beginners like us to learn and improve !

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

It grow the internal effort of beginner programme,make hope to became a good programmer, I like it

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +18 Vote: I do not like it

You might also would like to take a look at the incredible achievement of Tlalafuda__Tlalafu, who made 10 wrong submissions for problem B and found bugs in all of them!

Думаю, что вам также будет интересно увидеть невероятный успех Tlalafuda__Tlalafu, который не поленился отправить 10 неверных решений по задаче B, а после этого смог обнаружить баги в каждом из них!

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

    He just hardcoded a wrong output for some random input 10 times... is this sarcasm?

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

is no one here concern about rating inflation? In a normal div2 round, it seems like there's usually about 100 users who will be promoted to expert and some of the expert will drop, but this round, there seems to be about 250 promoted with 0 expert demoted.

→ Reply