Vovuh's blog

By Vovuh, 6 months 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 Ne0n25 for testing the round.

UPD: Thanks a lot to testers dreamoon, 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 PikMike and Ne0n25. 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 iman12 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 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 c650Alpha 0:04
C Milhous 0:08
D Milhous 0:11
E s0mth1ng 0:09
F DoveDragon 0:14

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

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

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

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

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

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

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

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

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

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

Finally!

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

Last three lines was awesome . :D

»
6 months 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 ??!!

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

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

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

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

First time I saw about myself in any round announcement.

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

It's rated for me so :D

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

unofficial participator for the first time :) :D

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

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

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

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

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

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

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

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

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

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

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

»
6 months ago, # |
  Vote: I like it -39 Vote: I do not like it

Div3 => noobs?

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

»
6 months ago, # |
  Vote: I like it -11 Vote: I do not like it

Can't Wait :D****

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

    Still messi is better than ronaldo

»
6 months ago, # |
  Vote: I like it -17 Vote: I do not like it

Hoping For short Problem statement

»
6 months ago, # |
Rev. 3   Vote: I like it -10 Vote: I do not like it

As CF is introducing div3 for begginers, it is also good to change title/color to make it interesting for begginers, like 1000-1200 is begginer, <1000 is newbie !!

»
6 months ago, # |
  Vote: I like it -120 Vote: I do not like it

Earn bitcoins while browsing the Internet https://getcryptotab.com/1065838

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

Looking forward to concise problem statements without unnecessarily long storylines!

»
6 months ago, # |
  Vote: I like it -54 Vote: I do not like it

I think it's need to make div 4 for under 1000.

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

Div3 finally comes! No more falling scores!

»
6 months ago, # |
  Vote: I like it -27 Vote: I do not like it

is it rated?

»
6 months ago, # |
  Vote: I like it -35 Vote: I do not like it

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

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

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

    Obviously...

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

      Will it be rated for div 3 contestants?

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

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

How many problems will be there?

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

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

"8093" Registration in Div 3 !! wow <3 .

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

I usually solve C in div2..Which prob i should choose to solve in div3 ??

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

Problem A : Print "Hello World"

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

HTTP Response: 500, 502. Website failed.

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

20 minutes of penalty is too much.

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

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

Failed at B

Don't understand what C is asking

Input #1 of F is wrong? Surely largest is 5~ cba to attempt as maybe I'm misreading like C

RIP, time for gaming instead

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

»
6 months ago, # |
  Vote: I like it +65 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..

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

            Sorry, you're right. Forgot that.

»
6 months ago, # |
  Vote: I like it -42 Vote: I do not like it

I think this was too easy even for div 3.

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

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

»
6 months 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)

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

Holly cow, I'm experiencing something in Java I never ever experienced in a contest!

For problem "C" I'm doing a sort using Arrays.sort. My code times out (it takes more than 2 seconds for testcase 6). But, if I randomize a little bit the input, i.e., instead of doing:

  a[i] = in.nextInt(); // "in" is the input stream

I do:

  a[(i + (n / 2)) % n] = in.nextInt();

the solution passes!

Does anybody know how can this be?

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

    It seems that there are arrays that take O(n^2) time to sort in Java, using Arrays.sort(): http://codeforces.com/blog/entry/4827

    Most likely test case 6 is such an array and was designed to discourage people to use the O(nlog(n)) solution instead of the linear one...

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

      Is there simple linear solution for C?

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

        Yes, you can use quickselect to find the k-th smallest element in an array in linear time: https://en.wikipedia.org/wiki/Quickselect

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

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

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

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

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

    I think Div3B is too simple for Div2B

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

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

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

:(

»
6 months 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)

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

how can solve the ploblem c?

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

    Case 1:- If k=0 then check if arr[0]=1. If yes the print -1 else print arr[0]-1. Case 2:- Ifk==nsimply printarr[n-1]`

    Case 3:- Check the value of arr[k-1]. If arr[k]==arr[k-1] then print -1 else print arr[k-1] This is sample test case 2.

    This is all in a sorted array.

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

      oh ,i forgot to judge if arr[0]==1, anyway,thank you!

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

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

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

        k=0.

        Output a number x such that 0 (no) elements from the sequence are less than x.

        If the smallest element in the range is l and max is r.

        Then.

        If you take an element >r then all elements will be less than r and k=0 will not be satisfied.

        If you take an element>=l and element<=r then some elements in the range will be less than x and again k=0 will not be satisfied.

        As for last case if l==1 then you can output 0 because no(0) elements will be less than 0. However since the answer must be in the range[1,1e18], in this case the answer will be 0. For all other cases output l-1.

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

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

Can E be solved using this logic: LINK

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

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

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

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

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

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

      Thanks, soham_1234. 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?

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

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

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

The contest page was not visible for the first 10-15 minutes, and the problems were not accessible for the mentioned period (well,at least for me). So will it be justified to keep it rated?

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it
»
6 months 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.

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

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

 GOGOGOGO SO FST LKE A SNIC X

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

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

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

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

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

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

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

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

      I can just delete the comment if you want !

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

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

The fixed problem at the beginning will affect penalty and so the rating changes.., many contestants have 2 or more problems tested at the same time and submitted earlier so..

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

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

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

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

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

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

Really we enjoy this contest . Thankyou Codeforces team

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

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

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

    • »
      »
      »
      6 months 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.com/blog/entry/44731

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

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

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

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

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

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

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

Will there be any tutorial for this round??

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

is it rated for newbie ?

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

Hello Vovuh. My rating is 1500 because I hasn't joined any contest before. However you said "if your rating is less than 1600, then the round will be rated for you." So why I'm not rated after this contest.

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

    The contest has not done with the large test case. So we need to wait for the final result and you will see your ranking changes.

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

i passed all of the problems!! yayyy

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

When will system testing start?

  • »
    »
    6 months 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"

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

When will the ratings be updated?

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

Pls, somebody explain, how my solution http://codeforces.com/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

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

    Afaik Unordered_map is slower than normal map.

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

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

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

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

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

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

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

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

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

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

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

»
5 months 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 !

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

»
5 months 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, а после этого смог обнаружить баги в каждом из них!

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

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

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

I would request the host to conduct more number of Division 3 contests. I am sure that many other users like me with rating less than 1600 are finding it difficult to solve Division 2 problems easily and obtain better ranks. I would suggest to conduct 1 Division 3 contest for every two Divison 1/2 contests so that we can gain confidence and hopefully aim to perform better at Division 1/2 contests.

I would like the opinion of other people too.

Thanks.

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

great round