McDic's blog

Codeforces Round #589 (Div. 2)
By McDic, history, 5 years ago, In English

다시 만나서 반가워요, 코드포스! (Nice to see you again, Codeforces!)

I'm again happy to introduce you to Codeforces Round #589 (Div. 2). Please look at following information for details:

  • This contest will take place on Sep/29/2019 16:05 (Moscow time).
  • The round will be rated for all Division 2 participants.
  • There are 6 problems and you will have 2 hours to solve them. Score distribution will be announced later.

The listed handles below are contributors. Thank you for all who listed!

For this contest, I tried to improve following things:

  • Reasonable difficulty: At my last contest, less than 200 official participants managed to solve at least one of DEF. Especially, 1182D's problem difficulty rating is 2500 and 1182F's problem difficulty rating is 2900(no official solvers!). This is not good for Div.2 participants. In other words, my first contest was hell. So this time, I tried to make my second contest to have more reasonable difficulty than my first contest.
  • Stronger data: There were 300+ successful hacks and almost 2000 sysfails at 1182B. At this time, I splitted testing phase into early phase and late phase. I'm bit worried, but I believe data will be stronger than my last contest.
  • Compact statement: I remember many people complained about 1182C's super complex statement. I made very compact statements for this round. There is no problem with more than 10 lines of statement(except I/O section) in this contest.

I hope everyone can enjoy my second contest. Thanks in advance!

UPDATES:

  1. If you want to discuss problems in chat after contest ends, come https://discordapp.com/invite/algorithms and you can enjoy discussion.
  2. I have deleted my last problem(G) from this contest during testing period. I really wanted to include that beautiful problem in my contest, but nobody solved that problem for a week. That problem will be appeared in another Div.1 contest.
  3. Scoring distribution is 500(A)-1000(B)-1250(C)-1750(D)-2250(E)-2750(F).
  4. Editorial: https://mirror.codeforces.com/blog/entry/70162
  5. Congratulation for winners!

WINNERS (updated):

  1. PositionZero
  2. supy_2
  3. hitman623
  4. lzqaq
  5. cwise
  6. LittleBeetle
  7. Tsypkokokokoko
  8. i_love_gnar
  9. 8-_-8 (handle mentioning is not working on his handle)
  10. wdk1745
  • Vote: I like it
  • +1581
  • Vote: I do not like it

Comments Comments (187)
| Write comment?
»
5 years ago, # |
  Vote: I like it +185 Vote: I do not like it

McDic orz. It will be a great round!!!!!!!!!!!!!!

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

I like the compact statement part

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

This what they call learning from your failures :)

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

Ideal time! I wish good luck to all of the participants!

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

Wa! Another Korean round!

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

I can still remember the last round QAQ. I get a wrong understanding on B.

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

Congrats on your round McDic O_o

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

Another Korean round! I think this round is well-prepared. Wish your high rating!

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

I've never seen someone post about their previous mistakes on a round, and talking about how to make the next one better. What a good way of making the most of constructive feedback. I'm eager to see these improvements in the round. It would be cool if this example is followed by other contest writers. And by other writers I mean GreenGrape.

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

Thanks a lot:)

There is nothing better than Compact statement！

look forward to a wonderful contest!

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

My code was hacked for the first time in your previous round :). Hope this round will be fun.

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

Many successful hacks is not bad. As long as these hacks are not if (n == 1).

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

sounds like an awesome round Good Luck :D

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

GOOD LUCK

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

finally .... tow of my solutions was hacked last round ... thanks you ,,

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

I love how you are trying to improve your contest. Hope it will be a great contest! :D

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

Welcome back McDic after 4 months with a new contest;

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

thanks for the improvement :)

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

Thanks a lot for all the hardwork. Particularly, reflecting on the previous mistakes is great <3

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

Interesting blog . truly to say , I read every word of a blog (about contest) after a long time !!!!

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

Is this some special round? I have never seen such upvotes on any contest announcement blog before.

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

First time to see someone writing on the past mistakes. Hope for a good round :D

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

McDic make me "out of competition".

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

Soo much upvotes before a contest. Seriously what if this guy(dude) is like a politician who's promising what he can't execute?

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

    after all, he admitted his mistakes in the last contest and is trying to make this one better.That's why he deserves these ups.

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

      Admittance doesn't matter, Results do. Y'all should at least wait and experience first. I guess that's why it's quite easy to scam y'all

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

        I am in super pressure. QAQ

        Hope there will be no fatal issue on my second contest.

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

    agree.

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

      why your comment has only 7 downvotes but still light coloured?

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

WTF? Why so many upvotes?

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

In ready to compete in excellent contest!

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

Imagine if after all the upvotes the round isn't better than the previous one lol that would be funny as hell XD (just kidding I think it will be good)

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

    Thats why I always keep my vote till the end of the round

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

      Ah geez, Rick, you shouldn't be so cynical

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

        Am f***ing Rick Sanchez C137, I can be what I want :D

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

something new

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

nung nung

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

It seeming a well-prepared contest. I think it will be an enjoyable one.

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

I like nice weather :)

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

sorry

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

One of those rounds where the pupils do A,B and then keep refreshing the ranklist for 1 hr.

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

I hope you will not set problems with 4 levels of definitions in the future. And I hope coordinators will not approve such problems in the future.

All that I can do now is to vote a blog down, but it was boosted by orzing schoolboys to 1k+, so probably it won't get downvoted. Or can it? There are 13k participants...

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

    you are salty

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

    I have no problems with multiple definitions as long as each of them is clear enough. Anyway, if you hate definitions, you may enjoy this gem 1120A - Диана и Лиана.

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

      I have problems when the definitions are recursive. In today's problem we have 4 levels: 1) prime 2) g 3) f 4) answer. It is hard work to build a full picture of the problem in the head, it takes a lot more time than thinking of a solution and coding that problem. I think I'm not alone here.

      The problem you mentioned have many definitions and it is bad, but they are parsed easily.

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

        Fully agree with you

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

        I think the examples given in statement does really help me understand how to connect all those definitions. I agree that it's not a good problem but your original comment seems to be a bit excessive.

        McDic do you mind explaining why do you have to include $$$x$$$ and $$$prime(x)$$$ in this problem? I feel that it does nothing but add a negative value to the problem.

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

          My original statement for C was full of math. I simply changed part of them to English sentences, step by step.

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

This contest brought to you by the number $$$1000000007$$$

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

    And I used $$$998244353$$$ from my template in E, and could not debug that :( Otherwise the code was correct.

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

deleted

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

ARGH! Could you do less number theory problems next time?

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

    By less you mean 0? I see 1 "number theory" problem.

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

      C and E is pure math, no programming at all. F i dont know.

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

        F is definitely not math.

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

        Ok, I can agree that C felt a bit "mathy" and the statement was a little off-putting, but labeling E as pure math is just wrong.

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

It is about math, not about programming.

If you want to do a programming contest you can go to a programming contest site.

Oh, wait...

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

I feel like C's statement could be improved by using consistent variable names.

I mean sth. like

$$$\prod_{i=1}^{n} f(x,i)$$$ with $$$f(x, i) = \prod_{p \in prime(x)} g(i, p)$$$ where $$$g(i, p)$$$ is the maximum....

would be much more understandable, or not?

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

    It is not understandable either way.

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

    CF team requested me to use less formula, but use more english sentence

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

    The first version of this problem by McDic was like this. However, not every CF user knows this. Since we wanted to make the problem clear for everybody, and in the same time short enough, we decided to rewrite the statement using simple English words.

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

      Makes sense, but still could've defined $$$g(y, p)$$$ instead of $$$g(x, p)$$$ to be more consistent with the definition of $$$f(x, y)$$$.

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

    calculate the number of N! for the prime P in X are NUM ,so the answer are the product of quickpow(P,NUM).

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

What was pretest 15 for C?

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

What the hell is pretest 5 in C

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

How to solve C ?

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

    For each prime in the prime factorization of x, it will appear in the answer exactly k times, if it appears k times in the iteration of 1 to n, so for instance, if n = 8, and x = 2, then the answer is 2^7.

    Now, how to count them fast? Simply count all n/prime^i, for all i, such that prime^i <= n. call this value sum. this can simply be done by calculating first n/prime, then n/prime/prime , etc.

    After this, calculate prime^sum, multiply to answer. Iterate for all primes.

    Unfortunately I'm getting a WA on test case 5, so I'm probably wrong somewhere, but I can't figure out where.

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

How to solve E and F?

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

If I sent two correct decisions, which one will count?

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

Modforces :)

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

I had to wake up at 5:50 am on a Sunday morning to write the contest, but it was (mostly) worth it!

Good job McDic.

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

Whats B pretest 6???

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

How to solve E, I tried memoization, for all pairs of n,m size of grid, got TLE though....

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

I found D's problem statement a bit vague, the line "All set should not be empty", I believe it could have been written as "No set should be empty". What about you guys?

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

What is pretest 4 in Problem B ?

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

    4 4 2 0 3 1 1 3 0 3

    I don't know why the answer is 0 instead of 4. Do you know?

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

      Red is for row constraints and blue is for column constraints, check is where there has to be a black cell and 'X' is where there has to be a white cell so as you can see in the 3rd row 4th column there is a contradiction.

      Hope this helps

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

        Yes, I didn't get from problem statement that the input could be invalid. Thank you.

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

https://mirror.codeforces.com/contest/1228/submission/61492326 https://mirror.codeforces.com/contest/1228/submission/61490870 https://mirror.codeforces.com/contest/1228/submission/61490695 ???

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

Pretest 12 in D? how to solve D?

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

13444 Registered users, new Record?

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

what is pretest 13 in C?

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

Is the intended solution of E $$$O(n ^ 3)$$$ DP?

I saw someone passing E with this complexity, unfortunately mine TLEd at test 3.

submission: 61507994

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

    Mine passed with that complexity, you shouldn't use fastpow in such a deep loop, just precalculate every power.

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

      Thx for ur advice, the constant factor really sucks

      To be honest, a 2000 ms would be more reasonable

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

        As far as i know, TL is 1s to cut off $$$O(n ^ 3 * log(n))$$$ solutions.

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

    Yes, it can be solved in $$$O(n ^ 3)$$$.

    My code: pastebin

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

    $$$O(n^2)$$$ inclusion-exclusion, I guess.

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

    can you please explain your approach ?

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

      It is somewhat similar to BZOJ 1801: [Ahoi2009]chess. U may read it’s solution if u know Chinese.

      The idea is to calculate $$$f(i, j)$$$, the number of combinations such that there are $$$j$$$ columns having at least one $$$”1”$$$ after filling up $$$i$$$ rows. Then the answer is $$$f(n, n)$$$.

      I believe u can derive the transition formula on ur own :)

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

61473445 61473656

I submitted the exact same code twice by mistake, and got -50 for it? :X

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

That feeling when you find out that your code actually matched the samples before the end of the contest but as a matter of fact you forgot what the sample actually was in the first place so you thought your code had mismatched the sample and didn't submit code

A life-saving tip- don't keep yourself unfed for 16 hours before any contest.

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

can someone tell me what's problem with my solution for problem — > 3 https://mirror.codeforces.com/contest/1228/my

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

    dude, that link will send everyone to HIS/HER submissions page lol

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

      it's cool bro. It show my entire mind and you need to find out bug from that.

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

        not your mind, whoever clicks on that.

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

        although this reply doesn't have a link, it sent me to google translate, and I still don't get it -_-

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

How come score 1250 for C while 1000 for B?

Is C seriously easy for 2500 contestant?

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

Such an awesome contest . I got to learn so many amazing concepts.

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

In Problem B Div 2, Please help me know why my code is getting runtime error in TestCase 6?

https://mirror.codeforces.com/contest/1228/submission/61498112 (commented code)

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

Although I had a terrible performance on problem D, I like the succinct Title Description very much.

The simpler the topic is, the more favorable it will be for those who are not proficient in English, and the more favorable it will be for fair competition.

Thanks a lot.

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

why this submission https://mirror.codeforces.com/contest/1228/submission/61492705 passed? Does here j var will not be overflowed?

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

Thanks for 3 combinatorics tasks. I liked them a lot. I think every math codeforces round should have 3/6 math tasks.

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

    Can you clarify to me which 3 tasks are combinatorics?

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

For problem D, you can also use this approach:

  • Sort each adjacency list and hash it using Rabin Karp
  • Every node with the same hash is part of the same partite.
→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    In fact, you don’t need to use hashing — you can just store set of vectors

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

      Thanks for pointing that out. I forgot that std::vector implements == and < operators.

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

    Wow that's really neat solution. Here's my solution using the above idea.

    Please ignore my naive question in old revision.

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

    How to solve D?

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

Wowwww... Great contest <3

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

D seems to be an easy version of DOOFST in Codechef September Challenge.

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

The round was awesome! But why would you warn the contestants about integer overflow in problem C? Isn't it a part of the problem to figure it out by yourself?

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

    Many blue testers struggled in that. That's why I warned.

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

    And why even have $$$10 ^ {18}$$$. Problem would have been equally interesting with $$$10^9$$$

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

How the System Testing done so quick even after such large number of participation

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

Was the diagram for the sample input/output for 1228D - Три множества added partway through the contest or after the contest? I don't remember seeing it when I solved the problem.

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

Thanks for the problem C test 3 overflow warning.

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

Can you please fix the problem D?

It mentions that "not all vertex sets should be empty" while it implies "all vertex sets should be non- empty" (which I figured out after the contest ended). Both statements are very different.

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

    No, it mentions "All vertex sets should not be empty."

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

      This doesn't mean All vertex sets should be non-empty. All vertex sets should not be empty -> There should exist at least one non-empty set.

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

    At first I also thought that some vertex sets can be empty but not all of them.

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

Although a bit too many math problems, still a great round it was, I believe.

I really enjoyed problem D. I haven't solved problems that require sharp observations for so long.

Now I'm also curious about your problem G. Anyway, thank you for such a great experience!

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

I am literally losing my mind :/ , can someone explain why in problem C when in this code 61512229 I add this line "if (a==0||b==0) return false;" in line 10, I get WA in TC3? 61512212 , i mean it says overflow, but adding "if (a==0||b==0) return false;" should'nt give a different verdict in this problem :/ should it? someone pleaseeeeee help ;(

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

    McDic first of all great contest thanks :D , second please help, seriously I am lost for words, I feel like the problem is from CF compiler itself, I am seriously losing it here...... I just added an "if" which doesn't even get to do anything there in TC3 but still get TC3 WA ;(

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

Position Zero! This is Tendo Maya. (((

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

Thanks to McDic, I'm purple ^_^

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

Great contest thanks to McDic. Hope to make another contest!!!!!

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

the system test of problem D is too weak.

UPD: maybe using "too weak" is unappropriate, but I think it's a big slip.

most submissions can't pass #48(it was added after system test).

input:

3 1
1 2

output:

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

    I am sorry about such issue. I considered 7 types of graph and that was not enough :(

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

What happened to the candidate with 3rd rank.All his solutions are shown skipped?

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

McDic Thank you for this awesome contest.

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

How to solve B. I could not find any idea

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

I have a headache of problem C statement and tutorial. Very hard to understand the problem.

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

Problem C.

Does taking modulo with LLONG_MAX really matters?

with %LLONG_MAX ACCEPTED

without %LLONG_MAX WRONG ON TC3

By the way in local compiler both code were giving same answer.

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

    Signed integer overflow is actually undefined behaviour; in your WA example, the compiler notices that you're diving a*b with b and automatically replaces it with a, meaning that your if condition never triggers. When you're doing %LLONG_MAX the compiler actually calculates the expression.

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

      But multiplication and division are in different instructions. So it should be like two long long int numbers multiplied and stored in another long long int variable(if it overflows wrong value stored here). Then in another instruction division takes place and should trigger if condition in my code.

      Or may be codeforces compiler is more smart then my local compiler :( that it can combine two different instructions, which is unexpected.

      REF. Same method for int is used here . Which should work for long long int also.

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

While trying to hack during the contest I came across these submissions and I feel like this submission and this submission is almost the same and has been purposely modified to escape plagiarism. I request the officials to take appropriate action.

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

For problem D,

I don't know how to prove it, but this seems to be a solution.

Observe a valid graph focusing on the degree of edges.

In common cases, if a graph is valid, it can be divided into 3 sets, and the degree of vertexes in every set is n - size_of_this_set , and they should be the same. (so in a valid graph, it could have 3 type of vertex at most)

When add all possible degree values up, the sum is 3n - sum_of_size_of_every_set, that is, 2n.

Denote all possible degree values as a set $$$S={ s_k }$$$ .

There are only four cases:

  • case 1: S.size() = 1, which means every vertex has same degree $$$s$$$ . There should be $$$s+s+s = 2n$$$. The construct scheme is arbitrary, while every n/3 vertexes are in a set.
  • case 2: S.size() = 2, $$$S={s_0,s_1}$$$ . If the graph is valid, there should be either $$$s_0+s_0+s1 = 2n$$$ or $$$s_0+s_1+s_1=2n $$$. The construct scheme is divide one type of vertexes in half .(actually, the number of this type must be even.)
  • case 3: S.size() = 3, $$$S={s_0,s_1,s_2}$$$ . If the graph is valid, there should be $$$s_0+s_1+s2 = 2n$$$. Hash three types of vertexes into $$${1,2,3}$$$.
  • case 4: S.size() >=4 , -1.

Seems enough , but I got Wrong answer on test 1461514754. Because it's not necessary and sufficient condition.

So, in case 3, I make a check of all the edges to see if it's not valid, and passed all the test cases (for now).

My solution: 61514951

BTW：Nice round.

BTW2：Sorry for my awkward expression...

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

Hi, How can I avoid overflow in question C?

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

    if(((a*b)%LLONG_MAX)/b==a) then it doesn't overflow, else overflows...... check special cases a==0 && b==0 too so you don't get RTE for dividing a number by 0.

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

    If you don't mind this $$$log(t)$$$ time, you can calculate the max $$$sz$$$, which satisfy $$$a_{i}^{sz}<=t$$$ , by the code below:

            while (t >= a[i]) {
            t /= a[i];
            sz++;
        }

    When you reach $$$a_{i}^{sz}$$$, there is no need to get larger. So this will keep all your variables below t(or some other threshold).

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

In problem D. I find number of connected components in complement graph and if this number is 3 then answer is yes and sets is this connected components. why is this solution wrong? I recieve wrong answer in test 11.

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

    You also have to check that there is no edge between vertices in the same component

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

I am not getting my solution accepted[submission:61543290].As per test case 7,expected output is different from answer but I am getting correct output on my code using IDEYour text to link here...

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

This round is way better than the last one.

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

Could you please update tasks' ratings?

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

    Do you mean difficulty ratings for my problems? It will be updated by Codeforces team, not me.

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

Can anyone explain the question D easily? I didnt understand the question for a long time. TIA :)

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

    Make 3 vertices sets to make each pair of sets forms complete bipartite graph.

    → Reply