Batman's blog

Codeforces Round #411
By Batman, history, 8 years ago, In English

Hi!

I'd like to invite you to join in Codeforces Round #411 that will be held on May 4 at 17:35 MSK.

Actually I didn't do anything for this contest :) and most of the contest is prepared by my good friends saliii and MohammadJA. Also amsen, Navick, tundra, kastarika and I helped them in testing problems, writing statements and these sort of things. At the end, Thanks to KAN for his huge help in all of the contests and MikeMirzayanov for great Codeforces and Polygon platforms. (Sorry if there's someone I didn't mentioned, This is everything I know).

Each division contains 6 problems (4 common problems). Hope you enjoy them.

The round is rated and score distribution will be posted soon and good luck and have fun and hope you high ratings and all the other words that should be told.

UPD 1 Contest delayed by 10 minutes.

UPD 2 Contest delayed by 5 minutes. :)

UPD 3 We can see the scores now in contest page.

UPD 4 Contest is finally over, Hope you enjoyed the problems. Cause of technical issues editorial will be posted tomorrow.

UPD 5 And here are the top5 in each division:

Div1:

1-riadwaw

2-Endagorion

3-al13n

4-molamola.

5-zeliboba

Div2:

1-ConnorZhong

2-_ISB_

3-Dipak

4-hahaschool

5-BlackTools

And also congratulation to hahaschool, MKyzy and shanin who solved problem F in div2.

UPD 6 Editorial is ready now.

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

Comments Comments (390)
| Write comment?
»
8 years ago, # |
  Vote: I like it +63 Vote: I do not like it

I hope the problem statements will be clear, short and easy to understand like this blog :'D

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

How much will the round last? I see that it's a non-standard round (having 6 problems).

L.E: oh, it's 2 hours. I didn't check out the contest tab

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

"good luck and have fun and hope you high ratings and all the other words that should be told." is like saying "wish you all the best" in happy birthday

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

A round at the beginning of the summer vacation, What's better than this :)

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

    It's a round on the last day of high school for me :)

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

    It's the beginning of our final exams, What's worse than this :)

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

    begining of our 4th sem exams and my first codeforces round... fingers crossed!

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

GOOD LUCK

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

I was hoping for a Star Wars contest in the announcement.

→ Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it -10 Vote: I do not like it

Two Impressive Setter's Profile saliii & tundra from today's contest

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

I hope problem statements won't say us to assume all other words that should be told :p

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

Hope there won't be any other "HOS" in statments :D

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

6 problems and 2 hours.WOW!

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

Actually I didn't do anything for this contest :)

Sorry if there's someone I didn't mentioned, This is everything I know

all the other words that should be told.

Wow... It's... Awesome..

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

30 minutes before the beginning of the contest and score distribution hasn't been posted...

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

Maybe it will be good if CF implements a feature to reveal scoring distribution automatically, say 5 minutes before the round.

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

    I prefer more than 5 minutes, but I'm agree with you.

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

    I've never understood why scoring distribution always has to be revealed at the last minute. I mean, why couldn't they reveal it when they first made this post?

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

      may be it is something to do with the number of registered participants ... just a guess

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

      Don't worry. I'm aware that problem D is easier than C (for me at least), LOL.

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

      My guess is, to prevent people from using well-thought-out strategies. Making you think which problem to start first, second, and so on right before the contest boosts your adrenaline :D

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

Auto comment: topic has been updated by Batman (previous revision, new revision, compare).

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

Good luck for all!

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

Why the delay? I know I'll never get an answer.

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

extension by 10 has become common

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

Thx for delay :) I'm in bus getting home right now

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

    thanks again :D I even finished eating

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

UPD 1 Contest delayed by 10 minutes.

Probably, still not decided on score distribution

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

late-10minutes.

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

    one of the worst things about codeforces contest :(

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

who's girlfriend missed the registration?

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

GLHF

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

Maybe server was unexpectedly fast, so they must make delay to see what is wrong :P

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

UPD 1 Contest delayed by 10 minutes.

We saw that, maybe we can see scoring distribution next?

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

These numbers <3 :'D

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

Blin che za nesereznost'?

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

Just 2 minutes till to learn scores of problems :P

Contest delayed 5 more minutes LOL :D

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

Again 5 minutes late.So sad:(

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

Contest delayed by 5 minutes.

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

Again Delay!! :(

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

Delays ... Delays Everywhere

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

I can only say:

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

UPD 2 Contest delayed by 5 minutes.

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

Auto comment: topic has been updated by Batman (previous revision, new revision, compare).

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

    The 7th problem is almost ready? :)

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

= ChamrAn what is the score distribution ? -read the problem statement

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

UPD 2 Contest delayed by 5 minutes

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

CF is delaying the contest little by little so we don't understand that thank you CF :|

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

If this contest gets pushed back any further I'll be late for work...

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

I hope this round wont cancel at the end of the delays

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

Can we have an announcement about these delays or not? :/

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

2.5 mins next?

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

Please stop playing with my heart.

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

A first delay is ok, A second one? that's irritating

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

Why the contest is not starting?

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

They are doing Binary search on delay . first 10 min, then 5 min... :|

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

Now i regret i upvoted the blog...

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

Contest delayed by minutes

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

    it shows that contest will starts at end!

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

What the Fuck, Dude

→ Reply
»
8 years ago, # |
  Vote: I like it +17 Vote: I do not like it
5 more Minutes please
→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it dalayed? Twice? Or have a bad computer?

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

    Oh sorry I didn't see the update announcement :P

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

Annoying : delay
More annoying : second delay
Most annoying : people complaining

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

    Mostiest annoying: people complaining about people complaining

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

      Mostiest annoyingest: people complaining about people complaining about people complaining.

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

Expecting: Due to the delays starting the contest. This contest will be unrated.

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

Delays are for the people using Internet Explorer.

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

The scoring is going to be a surprise this time :p

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

Quite frustrating when you reschedule everything in your day so you can fit the codeforce's contest but it keeps delaying.

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

So we have infinite geometry series, next delay will be 2.5 minutes, and 1.25 minutes, and so on, so total delay time will be 20 minutes to sum up. :)

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

    Or they'll be like 10, 5, 10/3, 2.5, 2, etc st the contest will never start, how can we know?

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

Waiting for next delay.

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

I'm sleepy...

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

long time no cf :)

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

You know what? 100 rating points on another 5 minutes. :)

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

Auto comment: topic has been updated by Batman (previous revision, new revision, compare).

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

Long queue :(

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

Hack page is not loading. :(

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

I waited 20 minutes for the page loading to hack a code, and then it tells that the code was hacked !!!!

EDIT : 4 codes

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

I dont like rounds where if you are put in a room where everyone solves the problem right you cant participate well :(

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

long queue :s

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

Queue is driving me MAD!

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

In queue :(

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

And at this moment Jackson knew... He f***ed up

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

I've been waiting forever for the hack form to load.

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

What was approach to solve problem D?

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

    Make a little observation and you will get it.

    result of aaab is same as result of aab+aab and you get 3 a's at the resultant string.

    So, the recurrence you get is R(n) = 2*R(n-1)
    Little bit more observation will show that taking R(0) = 1 works for all cases.

    And the initial sting aaab was available without any transformation. So the answer will be R(n)-1 for this case. Now, think about what you do for the case aabab, and you will know the solution.

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

    "Bubble sort" all 'a' to right side of string, count all swaps. On every swap 'b' becomes doubled.

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

What is the hack for C (Div.2 E)?

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

    what the hell??? I hope this contest won't be rating

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

    Maybe

    2 5

    0

    0

    1 2

    Or something like this

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

    maybe each node has 0 element in their set?

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

    I was hacked by the test where no ice creams are given in any set. So i was outputting total colors as 0 whereas it should be 1(color all of them the same).

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

      NOOOOOOOOOOOOO I'M SO DUMB

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

      Great. That bull#&! testcase made the difference between ~+120 and ~-50 rating for me (according to rating estimator extension)

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

        You're not the only one, buddy.

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

For me problemset was like AAACDE but still nice though. I think may have missed something in one of problems ABC, so are there any special cases except l == r in A?

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

How to solve D?

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

    IF we have string with 'a' and n 'b'-s, it becomes 2*n 'b'-s and one 'a' after n operations. Then start from the end of the string and every time you will have string of this type, so you count operations you need and new number of 'b'-s

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

    Probably go from left to right and count 'a'. If encountered 'b', then ans=(ans+pow(2,count_of_a)-1)%(1e9+7) Because of my very stupid mistake I got AV test 13. I just precalculated powers for only first 32 arguments....

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

      I did something like this before:

      count a from left to right and count a, if I encounter b then ans = (ans + (1 << count) — 1) % (1e9 + 7) but still not pass pre-test 6 Not sure why, then I tried going from right to left, also fail

      Gonna wait for the editorial then ..

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

        Well 1 << count can easily overflow. You should use binary exponentiation instead.

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

    Think of it as sending every 'a' to the end of of the array, by operating it against all 'b' on it's right. If we start from the rightmost to leftmost 'a', there will be a contiguous (subarray) stream of 'b' for each 'a'. The number of 'b' will double for each 'a' that passes it.

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

Found this during the contest but couldn't figure out anything. Can these things actually help to solve E?

How to solve E?

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

    The graph class you should be looking for is chordal graphs.

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

.

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

It seems to be a happy hack round. :)

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

How to solve Div1C/Div2E?

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

Very bad contest Problems are very bad and first 4 problems very easy to div 2 and hacks are overrrrrrrr

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

Does a character string (example char s[200000]) have junk value towards the end ??

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

I'm just curious: is it so well-known that an empty graph is considered a connected subgraph? I've had this doubt during the contest, but somehow this phrasing got me thinking that it should have at least one vertex. Shouldn't this be an aspect worth clarifying in the statement?

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

    Graph has non-empty set of vertices. So rejudge or unrate should be done.

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

      Many hacks have been done with empty subgraphs in the input, which is a bit unfortunate.

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

      Graph has non-empty set of vertices.

      Source?

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

        Russian wikipedia, at least

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

        English wikipedia suggests an ambiguity too:

        "Moreover, V is often assumed to be non-empty, but E is allowed to be the empty set."

        I would not assume any re-evals will occur though

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

      I don't think that round should be unrated. Seems that the best way is accept all hacks, but rejudge solutions without such tests.

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

      Do authors and coordinator KAN even read the comments? Anyway it is a fault in statements, and we see no reaction.

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

        Yes, I read comments. We will think how to resolve the situation.

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

          So, what was decided in the end? I am not insisting of anything, just asking out of curiosity :)

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

        First, this test was indeed a hack test.

        Second, I think that in this particular problem the ambiguity was much less than in general question "is the empty graph a graph?". Of course, it would have been better if we had explicitly mentioned this in the statements. But now, I think the best option is to leave it as it is.

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

          I think the ambiguity was exactly the same, which is also confirmed by the fact that authors haven't made such tests. If the problem was "count the number of connected subgraphs in the tree", no one would consider the empty graph. If not mentioned in the statements, it must have been tested by pretests, because it is clearly a matter of understanding the problem.

          Leaving it as it is is the most unfair for those who wasn't hacked. But I don't see the better option now too.

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

          "First, this test was indeed a hack test."

          Does it mean that organizers didn't provide it or it wasn't added to systests?

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

            There were a lot of hacks added to systests, and there were no such tests in the testset provided by organizers.

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

      Yeah, and array has non-empty set of elements, and string has non-empty set of characters.

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

      Not exactly: https://en.wikipedia.org/wiki/Null_graph

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

        "Some authors exclude K_0 from consideration as a graph"

        Still debatable ...

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

          If there are two valid interpretations, but the problem doesn't specify anything like "sum of si's must be positive", it seems like the problem setters want to allow null graphs.

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

            If there are two valid interpretations, there is a serious issue with the problem statement.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              8 years ago, # ^ |
              ← Rev. 4   Vote: I like it -10 Vote: I do not like it

              Well, the input criteria (all si are allowed to be 0) seemed to clear up the ambiguity.

              For instance, don't you sometimes see problems where the text says something like "subsequence" or "substring" and only later when you read the input specifications you figure out it is contiguous/nonempty/etc?

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

                Actually si being equal to 0 is irrelevant to the problem of empty graph (because even if all vertices had sone color it is possible that some color is not present in the graph)

                E.g consider testcase

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

                  Makes sense. I was thinking more in terms of the case when all si are 0.

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

            But the problemsetters haven't made such tests, see my comment below.

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

              Yes, I agree this is the real issue. Perhaps the authors aren't even aware of the ambiguity.

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

                Note that even if the problem setters didn't add the ambiguity intentionally at the first, the problem setters could've announced a clarification during the contest. Certainly, there were questions about the ambiguity and author must have been aware of it. Therefore, I can say that the problem setters intentionally created the ambiguity in a sense.

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

            "Vertices which have the i-th (1 ≤ i ≤ m) type of ice cream form a connected subgraph."

            Misinterpretation can happen here if you do not consider null graph as graph .

            As cited: "To avoid the need for such exceptions, it is often assumed in literature that the term graph implies "graph with at least one vertex" unless context suggests otherwise."

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

              1. A null graph is connected.

              2. I agree that graphs generally have at least one vertex. The problem's context (it's possible that all si are 0) led me to believe otherwise.

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

                Actually I just saw this:

                "Please note that we consider that empty set of vertices form a connected subgraph in this problem."

                This does fix every issue I said. :D I don't think there is anything wrong with this problem (except checker issue discussed down in comments).

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

                  This phrase was added just recently.

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

                  To prevent confusion, I'm here to say that this part was added after the contest to make sure no one face this issue later.

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

        "To avoid the need for such exceptions, it is often assumed in literature that the term graph implies "graph with at least one vertex" unless context suggests otherwise."

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

          I agree that graphs generally have at least one vertex. The problem's context (all si can be 0) led me to believe otherwise.

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

    Well, if you consider empty graph a graph, it's obvious it's connected (I mean definition is that any pair of vertices is connected which is true)

    Whether it's a graph is a good question, though

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

    But you can't say that an empty graph is not connected? Unless you can provide two vertexes, that aren't connected by any path.

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

      Definition of a path is a sequence of edges which connect a sequence of vertices. If you have a path containing no edges, then there is no path, correct? Therefore your empty graph is not connected.

      I agree that there are many interpretations, but I believe the problem was ambiguous enough to warrant a rejudge

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

        The empty graph is definitely connected. "For every pair of vertices in the graph, there exists a path between the two vertices." is vacuously true, since the set of vertices is empty.

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

        That is not entirely correct :). A graph with only one vertex and no edges is usually considered connected. But you have just proved that it isn't.

        My point was that an expression, opposite to graph being connected is "Exist u,v from V such that there is no path between u and v". You can't select anything from empty set thus it is not correct, thus empty graph (if it is really a graph) is connected.

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

    Moreover, seems like all tests with empty subgraphs are actually hacks. So it's fault not in statements but in validator.

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

My solution for E is way too simple to be true. How to solve E?

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

In Div1 E is the answer YES iff n=2^p, n!=2?

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

    No, the answer is YES iff n = 4k, 4k + 1. Proving that 4k + 2, 4k + 3 doesn't work can be done by looking at the parity of the number of cycles in the cycle representation but I couldn't find a construction for 4k, 4k + 1 in contest time.

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

    answer is yes when n ≡ 0, 1mod4. For n ≡ 2, 3mod4 the answer is no. (which is clear, because trivial permutaiton is even so the number of transposition should be even and is even only when n ≡ 0, 1mod4.)

    Construction is harder. But I guess one should use the following identities:

    • (12)(34)(13)(24)(14)(23) = e

    • (1x)(xy)(y1) = (xy)

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

      Yeah, I knew the parity argument. I could only come up with a construction for n=2^p so I kind of assumed that was the only case.

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

        ok. The full solution is:

        when n = 4k + 1 construct first for 4k then using (nx)(xy)(ny) = (xy) plug inside all (n, 1), (n, 2), ..., (n, n - 1).

        when n = 4k + 4 then construct first for 4, 5, ..., 4k + 4 by induction. Put (12)(34)(13)(24)(14)(23) at the beginning. And plug inside all (1x), (2x), (3x), (4x) as we did in the first case.

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

DIV 2E

I was thinking that each node will form a clique of size number of icecream in that node i.e if there are 3 icecream in a node in T, then there will be a clique of size 3 for that node in G. I found maximum size of clique and colored nodes such that no 2 items in a clique will have same color.

It failed on pretest-3. Am I missing something?

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

    I think every vertex set will form a clique. And every clique will have colors = size of clique. I don't know what else to think.

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

Why so much math and greedy? I don't know about E and F though. I solved E by greedy that i did't even understand why it passed the pretest ?_?

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

Have I understood the problem E correctly? There is no meaning to use edges between vertices in the given graph T?

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

    agree with you

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

    Same. I do 2 clarifications and still don't understand what is the use of edges in the tree..

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

    Yes, it guarantees there won't be contradictions between nodes. Also you can fill the answer in the order of tree traversal.

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

      What's the point of tree?

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

        So the new constructed graph will not have cycles.

        For example: {1,2}, {2,3}, {3,1} can't be nodes on a tree. (vertices which have the same type of ice cream form a connected subgraph)

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

          Can you please explain with a sample case?

          → Reply
          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
              Vote: I like it +5 Vote: I do not like it 
            3 3
2 1 2
2 2 3
2 3 1
1 2
2 3

            This is invalid.

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

              can someone explain why this is invalid??

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

          The new constructed graph will have cycles if vertex set size >= 3, right?

          I meant, vertex set of given tree, not the new one.

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

            No, maybe you missed this: Vertices which have the i-th (1 ≤ i ≤ m) type of ice cream form a connected subgraph.

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

              Hmm, I think what you mean is, after compressing each clique to one node in the new graph, we have a new tree. Am I right?

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

                Yes, G was a "tree of cliques".

                You could use the tree to assign the colors greedily correctly :)

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

                  I now understand why input has to be a tree. Otherwise, we might have clique of cliques. The solution only works if G is a tree of cliques.

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

                  The "every ice cream forms a connected subgraph" condition means nothing, unless graph is specific. In case of a clique any pair of vertexes are connected. That means there are absolutely no restrictions. You can easily reduce any vertex coloring to it.

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

Auto comment: topic has been updated by Batman (previous revision, new revision, compare).

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

When problem C is about finding yourself :D

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

I was sure my solution for C is correct, but obviously it is not :)

Is asnwer always max(Si) ?

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

    Is it even a div2 E level problem!

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

    Nope, look at this case:

    4 4

    3 1 2 3

    2 1 4

    2 2 4

    2 3 4

    1 2

    1 3

    1 4

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

      [DELETED]

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

      This test case violates the fact that vertices with color 'i' form a connected subgraph. Consider color 2.

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

        I edited the testcase. I think it is valid now..?

        UPD: Sorry, no, it is still wrong.

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

          Again it is not valid.

          I was right. But I do not know how I missed implementation part.

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

            Yeah...

            I also thought the same thing as you did, but then I came up with invalid testcases like this one! -_-

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

    No, because all Si can be zero, but you should answer 1. XD

    And yeah, this test is used as a hacktest on the contest. Many contestants missed this including me at first.

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

Div 2 A — D problems were almost two liners. xD

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

    For me it's an advantage. I prefer enjoyable thinking to tons of coding (often frustrating).

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

      but there weren't much thinking either...

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

        It depends on the skill level of participant.

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

          agreed, I personally find A-D too easy, while I can't understand what E is asking, so i give up. Anyone mind explaining what E is asking for?

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

In my Div2 B

link 1 — fails pretests

link 2 — passes pretests

Any help ??

Does setting s[n]='\0' matter ??

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

    Yes, it does.

    1. When you create an array inside a function it's allocated in the memory area called stack. It's randomized (filled with random numbers).
    2. When you create an array outside it's allocated in so-called global storage. It's filled with zeroes.
    3. '\0' marks the end of a word and on most systems numerically equals zero (i.e. '\0' == 0).
    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks I got 2 wrong submissions because of that !!

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

    when you're dealing with string as a char array, it does.

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

500-500-500-1500-2500-3000

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

In C (Div.2 E), not including a test where all vertexes have sets of size 0 is like purposely making a 'hack problem.'
Shouldn't hacking not be about something like that?

Nice contest overall though

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

Did anyone have trouble understanding F? I still don't understand what the problem is asking for, and I wasn't even sure where to start in terms of clarifications. Maybe one question is, do the coin transfers happen all simultaneously at each hour? Is there a fixed number of hours? Usually, when I see 10^100, it suggests that we let a random process run until it converges, but I don't see any randomization here, so that's probably another reason I got confused.

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

    Here you can consider 10^100 inf.

    The problem ask for this:

    For each gang consider that after 10^100 hours it has a[I] billions at first and it has b[I] billions now.

    Each of them will have a number of accepted billions between a[I] and b[I].

    Police sort them in increasing order and choose a gangs from top and choose b of them.

    What is the number of choosing b gangs.

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

      Ok that makes a bit more sense. I guess my other question would be how exactly does the tranfer process work? It seems we have the i mod s_i thing which seems not to suggest splitting indices up by gcd. Also I guess you also split the gangsI into strongly connected components and solve those individually. I believe there is a cycle involving arbitrary gangs within the same strongly connected component. Can you check my understanding is correct?

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

        It works till they see a completely same state that they saw it before ( it happen before 10^100 hours)

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

          Does the selling and trading happen in separate stages or can they be mixed together?

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

          Ok, I think I finally figured it out. Here is what was confusing to me.

          There are two distinct parts to this problem: 1) Compute for each person, can they eventually receive a fake coin? 2) Afterwards, there is the math problem that you mentioned above.

          I was very confused about part 1, and was not sure how to interpret the statement. For example, a sample explanation explaining the process would have helped greatly in clearing up any confusion, and I don't think it would have made the problem easier. Because I wasn't able to figure out what part 1 was, I didn't even get a chance to think about part 2. It was only having the interpretation with part 2 in mind was I able to correctly decipher what the statement was asking. To be honest, I think statement is unambiguous, but I don't think it was clear or concise.

          Also, as a side note, my solution is O(sum s_i + n^2), but it takes 2.7s. Is there a faster solution in mind?

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

            I'm happy that you understand this problem.

            I agree with you that the statement wasn't clear enough but it changed at the last moments, I read the last one and that was clear, for some changing in problem they change the statement.

            I was tester of the problem and my solution works in 700ms.

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

Honestly , speaking , questions weren't clear . Some had multiple answers but there wasn't any clarifications regarding this. :(

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

    well most of them informed that if there were multiple solutions you could print any.

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

How to solve Div2 F/Div 1D ?

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

    You can find for each component its diameter and the distance from each node in that component to the furthest node.

    Now you need to find the average for combining two components.

    This can be done in O(n * m) time where n is the number of nodes in the first component and m is the number of nodes in the second. However, this obviously wouldn't run in time. We can speed it up greatly by knowing the average diameter will just be (avgA + avgB + 1) Where avgA is the average max distance of all nodes in the first component and avgB is the same for the second component. However, this isn't always true. In some cases, connecting two nodes will not extend the diameter further than it currently is in the two components.

    Thus, we need to count these cases where the diameter doesn't change. We can do this in O(n) time where n is the number of nodes in the first component.

    We will for each node, binary search which node we can connect it to such that the diameter doesn't change. (We will have all distances of each component in sorted order so we can binary search) Then we can do some math with cumulative sums and cumulative averages to subtract out the appropriate portion and add back what we need knowing that all of these pairs will result in an unchanged diameter.

    This brings our runtime down to O(n * q * log(n)). This is still far too much. However, we can do two speedups to get it to run in time. First, we can memoize the answers we find for each pair of components. Thus, we will never need to deal with the same query more than once. Second, we will always do the linear loop on the smaller component. This will bring our runtime down to O(q * sqrt(n) * log(n)) which is good enough for the time limit.

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

      Use 2-pointers will decrease the Time To : (n+q)*(sqrt(n))

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

        You have to be very careful doing a two point sweep there. If each pointer always gets to go its full distance, you don't get the sqrt(n) speedup and your runtime is O(n * q).

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

      Why after last optimization you do, complexity turns to O(q * sqrt(n) * log(n)) ?? Can you prove it please ?

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

        Let a1  ≤  a2  ≤  ...  ≤  an be the sizes of the trees in the forest, and qi the number of times tree i is the smaller tree in a query. Also, let and

        The runtime is . We can forget about the term and multiply by it after we're done. Now,

        The second term in the inequality comes from the fact that if we must have (because the ai are sorted, so in the worst case every ai has elements greater than it.)

        Edit: lmn0x4F did this in an earlier comment below, sorry about that.

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

      Very nice explanation tbuzzelli, could you give some insight about the sqrt(n) in your complexity analysis?, I have some sign that could be like it, when the sizes of the each tree in the forest are: 1, 2, 3, ..., x and this sum is equal to n, for this x = sqrt(n), and now answer the querys is as you say O(q*sqrt(n)*log(n)), is it correct? What is a better analysis for it?

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

        mckkentmwk,

        Because each component will only contribute it's size for all things larger than it, it is fairly easy to show that in order to maximize runtime, all the components should be the same size. Now the question is, how many components should we have.

        Let N equal the number of nodes in our graph and let X be the number of components. Our runtime would thus be q * (N / X). However, each query must be unique because we memoize. Thus q <= X^2. Therefore our runtime is actually max(q, X^2) * (N / X). Let's assume that q = X^2 because any excess queries would just be repeats and are trivial to handle. Now we have a runtime of X^2 * (N / X) = X * N. We want to maximize X. Because X^2 <= max number of queries, X should be sqrt(100,000) which is technically sqrt(N) in this case because I considered the variables for bounds on N, M, and Q to all be the same for Big-Oh runtime analysis.

        I hope this makes sense. It is a fairly common runtime as if X is too large, the pairs don't contribute much and as X gets too small there just aren't enough pairs to make a large runtime. Feel free to message me if you have any further questions.

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

      This is such a nice and simple speed up! Did you came up with this during contest or is this something somehow common?

      Also, could you elaborate on where did the sqrt came from? I thought something like:

      For each query we find U, V (connected components) with U ≤ V.

      • then it's easy to see the .
      • then each vertex in U gets visited at most times in total.

      This leads me to something like

      Is there other way to think about it?

      Thanks :)

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

        So as long as we only loop through the smaller of the pair, we can show that our runtime will amoritize to q*sqrt(n) if we make sure to never repeat the same pair

        This is a fairly common speedup. In order for us to get a bad case, we need the max of n and m to be as large as possible where m and n represent the sizes of our two components.

        Because no pair can be repeated (because we memoize) the worst case on queries will be if we get every pair of components given to us(this may not be possible if the number of components is large but we will assume we can have an infinite number of queries for now). Thus, if we query every pair of components, our runtime is the sum of min(n(i), n(j)) for all (i, j) pairs. Therefore, for each component it only contributes it's size to our runtime the amount of times equal to the number of components greater in size than it. If we have two components of size n/2 we will have O(n/2) just for that but then we have little to no nodes left. It turns out that the way to maximize this runtime would be to have sqrt(n) equal size components. This brings us to the sqrt(n)*q runtime. The log(n) part is because we binary search ontop of that.

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

        This is a well known technique, introduced in IOI 2009

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

That feel when you realized you did not fix your own bug before hacking others :(

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

How was DIV2C/DIV1A supposed to be solved? :c

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

When you are that one guy -_- (Div1 A, somehow thought that answer on 1 would be 1 :D and then locked it immediately) :D :D

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

Will the system testing be today itself??

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

    I believe it should start in less than an hour like normal.

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

How to solve Div2 E?

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

What was pretest 3 for Div 2 E ? I used DSU for finding connected subgraphs and assigning colors incrementally to each node in each subgraph !! WA on pretest 3

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it -10 Vote: I do not like it

how this code get AC http://codeforces.net/contest/805/submission/26862337 and this get TLE ?!!!!!!!!! http://codeforces.net/contest/805/submission/26850899

How ????????????????????????????????

Edit this code get AC how !!

http://codeforces.net/contest/805/submission/26864979

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

Div3 contest difficulty

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

Ice cream coloring : "Wrong answer on test 131" :((((((

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

I have never seen so much systest fails as Div 2 E.

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

It depends on your room xD

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

Pretest Passed/Accepted ratio for Div2 E O__O

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

    how do you check that statistic ?? in submissions ??

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

[deleted]

Sorry I found a bug in my code.

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

GG me lost :( Every time I gets near that purple bar I always go haywire lol. Curse of the Expert is strong with me.

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

I have attempted a hack on solution submitted by user: exp1ore. I thought and I still think that his solution should get a TLE verdict. Problem:805A — Fake NP His submission:26862337 I have seen similar brute solutions receiving TLE verdicts, can someone please clarify the situation? Similar solution receiving a TLE verdict: 26850899 WTF, the same person I have tried hacking just got a TLE verdict in an even smaller case 26862337

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

how can this code pass without tle? he ran a loop l to r and got AC!

http://codeforces.net/contest/805/submission/26850369

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

When C was more solved than A ... (Div 2)

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

Wow! This wa129 on div1c on everybody's solutions makes it look like authors themselves made 0 tests with number of icecream types greater than maximal number present in data. That's the quality!

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

[DELETED]

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

By the way, may I wonder how many author solutions failed on first hacking attempt in div1c? :D

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

I have an argument that the tests that failed a lot of people in Div1C are invalid: how is T "a tree with n vertices and m types of ice cream", as the task described, if some of those m types DON'T APPEAR on the tree? I think it is perfectly valid to assume that each number WILL occur at least once, because otherwise the tree actually has less than m types of ice cream.

I liked a suggestion someone said above on fixing this: keep the hack scores, but remove these tests and rejudge the solutions.

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

    Why so? If m=4, the tree can have only one ice cream of type 4. The other three are available, but not used. But this is not illogical. Unusual, but still valid.

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

I forgot to cast the function size of vector to long long in problem F div 2 :'(

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

Div2 E Test 143

Input

3 2
1 1
1 2
2 1 2
1 3
2 3

Correct Output 

1
1 1

How ?! 1&2 are in the same set of node 3 so there is an edge between them how could they have the same color?

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

    That's your output to the test case. The correct output is:

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

      Oh!, I'm so sorry I didn't recognize that xD

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

    It is not correct answer, it is your output.

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

Auto comment: topic has been updated by Batman (previous revision, new revision, compare).

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

The output for Div1 C for the following test case:

3 6

3 1 2 3

3 4 5 6

2 3 6

1 2

2 3

For most of the solutions is:

3

1 2 3 1 2 3

But as you can see vertices 3 and 6 are adjacent and cannot have the same color. Most of the solutions seem wrong or i don't understand the question.

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

    the colors form a connected component

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

      Basically the ice-creams in each set form a clique and the tree structure doesn't matter, right?

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

Why All of my submissions show skipped? All of them are passed in system test.

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

My code for Problem C (Problem E for Div2) produces wrong colors, e.g. color values out of range(<=c) and for some tests even prints more than c colors. But it gets AC. Plz check...

26864974

UPD: I didn't mention that this code got AC...

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

    Yes the checker doesn't even check that number of colors used should be equal to c, like in test 3, 5, etc.

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

    Printing max(1, maxSi) and 1 2 3 ... M got AC (26865288)! :D

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

      Thats a serious problem with the checking policy. Not expected on codeforces.

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

      lol max

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

      Ping KAN

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

      Even max(1, maxSi) is seems wrong to me. Eg:

      3 3

      2 1 2

      2 2 3

      2 1 3

      1 2

      2 3

      Since all 1, 2 and 3 ice-creams are adjacent to each other, the number of colors required should be 3.

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

        your test is incorrect. 1 and 3 have color 1 and are not connected

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

        Node 1 and 3 has same color but not making connected subgraph. So it doesn't meet problem description.

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

        The vertices that have 1 don't form a connected subgraph.

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

        Vertices which have the i-th (1 ≤ i ≤ m) type of ice cream form a connected subgraph

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

        I guess i did not get the question. Could someone please elaborate?

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

    http://codeforces.net/blog/entry/47258?#comment-316511

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

    It looks like the range was set to [1, M], not [1, C].

    26865686

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

    Oops this is a serious problem. We will investigate how many people are affected by it. If this number is large, then... unfortunately you know what it means. If there are only few people affected, we will think.

    The result will be delayed as it takes some time to analyse the problem.

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

    It happened that only one person was affected by this bug, so this is a bit of luck to us, no rejudge needed.

    Nevertheless, it doesn't cancel my error. Sorry about that.

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

      I have a feeling that, the only person was the judge himself .

      → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it -19 Vote: I do not like it

Could one of the writers please provide the full test 25 for problem F in div2? I get a negative result. Not sure if there's a bug in my code (which I can't find) or a problem with overflows (on long long or double).

EDIT: nevermind, I found the bug.. I was forgetting a cast to long long

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

I am not getting why if in DIV 1 C I call dfs first and calculate the value later then it gives WA..

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

The tests in D are somewhat weak. My solution 26859777 uses two pointers instead of binary search and works 50s on test with one component of size n / 2 and n / 2 components of size 1, queries are all pairs of type (large component, small component). After changing to binary search, it works 0.6s.

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

    we have ten of such tests! but seems you passed them.

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

      ¯\_(ツ)_/¯

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

      Speaking seriously, could you share a generator for them? I think it'd be useful to fully understand the situation to prevent such issues in future. Could be a bug in generator, for example, or we simply misunderstood each other on the test structure.

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

        Yes, Of course. The correct generator should be this.

        void make2(int n){
    printf("%d %d %d\n", N, N/2-1, N) ;
    for(int i = 0 ; i < n ; i ++)a[i] = i + 1 ; 
    shuffle(a , a + n);
    for(int i = 1; i < n/2 ; i ++){
        int par = rnd . next(0 , i - 1) ; 
        printf("%d %d\n" , a[par] , a[i]) ;
    }
    for(int i = n/2; i < n; i++){
        int x = a[rnd . next(1 , n/2)] ; 
        int y = a[i]; 
        if( rnd.next(1,2) == 1 ) swap(x,y);
        printf("%d %d\n" , x , y) ;
    }
    for(int i = 0;i < n/2; i++){
        int x = rnd . next(1 , n) ; 
        int y = a[i+n/2]; 
        if( rnd.next(1,2) == 1 ) swap(x,y);
        printf("%d %d\n" , x , y) ;
    }
}

        We tried many time-limit-exceeded solutions, and they successfully timed out. But about your code, I don't know.

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

          Hah, seems like I was testing in Debug mode. I've run it on other machine in Release mode and my code works 3.1s on my test and 2.3s on your test. The difference between them is that I use a path as a large tree.

          So operations is ok for modern computers :)

          UPD In run mode my code 26877753 works 5.3s. So the tests are weak still.

          UPD2 I changed generator in several ways to make the same test that I used in my solution — still works 3.1-3.5s. Don't know what's the difference now.

          UPD3 If I output my test in file and then read it instead of generating in the code, it works 3s too. C++, you make me crazy!

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

            I have a path, too. In the last test. And I don't have any Idea for better tests.

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

              Yes, see the last comment. Reading my test from the file speeds up the solution somehow. I have no idea why though.

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

                After all, we are guilty. I must tell you sorry about the problem. We could lower the time limit.

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

                  Then there would be more solutions with correct complexity receiving TLE. Honestly I don't know how to prevent passing of my code without cutting these solutions. Furthermore, many solutions were faster than solutions, so you can't cut the first complexity.

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

If graph coloring is NP-complete, why is it possible to solve div1-C (Ice cream coloring)? I solved it but can't understand why the same idea cannot be aplied in a general graph.

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

    I solved it

    Then why can't I see the code in your submissions?

    As for the question, the structure of the tree is extensively used in the solution: the vertices in the subtree of v are handled after v. Take a careful look at this thing in your solution, if you've really solved it.

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

    Imagine the dfs while "remembering the colors".

    You are on some vertex, there are c slots for colors (u1, u2, u3, u4, u5, ... uc) ui has been colored using color i. If you go to some next vertex and some ui inside some slot isn't there, you can open this slot. If there's some new ui, you need to find some empty slot to fill with ui. Since the subgraph that has only the points that have ui is connected and the original graph is a tree you will never have a path from inside ui to outside ui and back inside without going back inside through the same point that you first went outside. This means that if you start the dfs from the point that has the most colors, when you go to some other point you will always have enough slots for new colors (if you are using all slots and some new ui appears, some uj will disappear) and you will find only 1 color for every single ui (you won't try 2 colors because you will enter its connected component only once).

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

How did this solution pass ? :D

http://codeforces.net/contest/805/submission/26865714

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

Div1C checker is wrong. Div1D tests are weak (some participants got AC with O(n^2 + q * sqrt(n))). I think this round is even worse than the previous one.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +35 Vote: I do not like it
    • unclear definitions in Div1C

    also hacking was so much important to get high rank, which is really bad in my opinion.

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

      Technically, C never claims anything about G. The part which mentions that an empty set of vertices is a connected subgraph is referring to the constraint on the original tree T. G is never defined to be connected and is not even connected in the samples.

      Furthermore, no where does it claim that all colors must be used. I do agree, however, that it is somewhat stupid to have a problem with such an easy break case for people to hack with.

      -Edit- -Edit 2- (the following clarification was apparently added after contest) The part that says "Please note that we consider that empty set of vertices form a connected subgraph in this problem." makes it clear that not ever color needs to be in T. This definition would be unnecessary if every color was present.

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

        This comment wasn't there initially. I (almost) always open all tasks at the beginning of the contest (just in case of cf technical troubles). It seems that the comment was added without any notification.

        UPD: lol, not even before the end of the contest. Seems that it's for future submissions and isn't supposed to affect the results of the contest.

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

        I'm pretty sure this comment was added recently.

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

          Oh. I didn't know that. Thank you for letting me know.

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

the checker for 1c is broken

and why 1a 1b are so trivial?

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

b……bba?

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

Wll there be an official eitorial?

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

I'm sorry,but I get confused with div2 problem E with this input :

4 4
3 1 2 4
3 1 2 3
2 3 4
0
1 2
2 3 
3 4

Some AC code get the output with

3
1 2 3 3

But actually the output should be

4 
1 2 3 4

Could anyone help to explain me where am I wrong?

UPD1: Thanks for tfg in the previous input vertex 3 1 2 4 and vertex 2 3 4 are not connected in the induced subgraph with only these two vertices.Here's a brief for dfs algorithm

We traversal the T using dfs we denoted vertex Vi with icecream i and vertex Vj with icecream j.
if i,j get different color then it is ok
if i,j get the same color , if we get a wrong result which means we meet a vertex with both icecream i and j then this node should be the parent of Vi and Vj and should be traversal before Vi and Vj this gets a contradicting.
→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    That's not a valid input since the vertices with 4 aren't connected. "Vertices which have the i-th (1 ≤ i ≤ m) type of ice cream form a connected subgraph."

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

Can anybody explain me the Div 2E.I'm getting a WA on third subtask. Every set of vertex v will form a complete subgraph. So the minimum no. of req colors is size of the subgraph. Is this true?

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

Problem E (div 2), "Each vertex i has a set of si types of ice cream. Vertices which have the i-th (1 ≤ i ≤ m) type of ice cream form a connected subgraph." Does this statement hold for the graph G which we are trying to build ? Does it have any use ?

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

wow ! 26865501

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

JUST WOW, you guys did it! Finally amazing INTERESTING problems (despite technical issues with tasks and translations in div1C) I'm looking forward to ur next contests!

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

Editorial ???

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

Auto comment: topic has been updated by Batman (previous revision, new revision, compare).

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

Why there are 2 UDP5 ? :)

UPD: Fiexed

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

    Cause I copied that and forgot to change it :).

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

Auto comment: topic has been updated by Batman (previous revision, new revision, compare).

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

in div2E: the reason behind that the sets where given as nodes in a tree with edges between them is that the order of filling the colors of the new graph nodes is guaranteed to be correct using DFS, for example in a case where n=3, m=2, node1 has set with color 1, node2 has set with color2, node3 has set with colors 1 and 2:

1) using a normal loop you will check the set of node1 of the tree (having color1) and assign node1 in the new graph with first unused color in the set which is 1 (for example if set with colors 4 and 5, node4 is assigned color1 in the new graph, and node5 isn't assigned yet, so first unused color is 2), then you will check the set of node2 of the tree using the same strategy (so node2 of the new graph will be assigned color1), which will make a contradiction because colors 1 and 2 are in one set in node3 of the tree which wasn't checked yet.

2) using dfs if you started from node1 of the tree and checked its set and assigned node1 in the new graph color1, you will guarantee the next node that you will check its set is node3 (because nodes having color i form connected subgraph), since node3 and node1 both have color1 in their set they will be connected in the given tree, and since node3 and node2 have color2 in their set they will be connected in the given tree, and since this is a tree node1 will never be connected with node2 (cycle), so since you will move from node 1 to node 3 in the dfs you will assign node2 in the new graph the first unused color in the set of node3 of the tree (which is color2) and no contradictions then.

note: in the contest time i didn't notice this so mine failed in system test (test 143)

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

when does the contest start in India? please reply with Indian standard time.

→ Reply