McDic's blog

By McDic, history, 3 weeks 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://codeforces.com/blog/entry/70162
  5. Congratulation for winners!

WINNERS (updated):

  1. PositionZero
  2. supy_2
  3. hitman623
  4. lzqaq
  5. skypool
  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
  • +1563
  • Vote: I do not like it

»
3 weeks ago, # |
  Vote: I like it +185 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it +228 Vote: I do not like it

I like the compact statement part

»
3 weeks ago, # |
  Vote: I like it +136 Vote: I do not like it

This what they call learning from your failures :)

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

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

»
3 weeks ago, # |
  Vote: I like it +19 Vote: I do not like it

Wa! Another Korean round!

»
3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

Congrats on your round McDic O_o

»
3 weeks 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!

»
3 weeks 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.

»
3 weeks 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!

»
2 weeks 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.

»
2 weeks 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).

»
2 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

sounds like an awesome round Good Luck :D

»
2 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

GOOD LUCK

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope it will be very good because it is hard

»
2 weeks 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

»
2 weeks ago, # |
Rev. 2   Vote: I like it +11 Vote: I do not like it

Welcome back McDic after 4 months with a new contest;

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

thanks for the improvement :)

»
2 weeks ago, # |
  Vote: I like it -72 Vote: I do not like it

It must be unrated,right?

»
2 weeks 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

»
2 weeks 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 !!!!

»
2 weeks 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.

»
2 weeks 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

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

McDic make me "out of competition".

»
2 weeks 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?

  • »
    »
    2 weeks 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.

    • »
      »
      »
      2 weeks 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

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        maybe you are right. anyway we'll see if it's a better one just a few hours later

      • »
        »
        »
        »
        2 weeks 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.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it -7 Vote: I do not like it

    agree.

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I will prove myself in this contest...In Shaa Allah.

»
2 weeks ago, # |
  Vote: I like it -27 Vote: I do not like it

WTF? Why so many upvotes?

»
2 weeks ago, # |
Rev. 2   Vote: I like it +10 Vote: I do not like it

In ready to compete in excellent contest!

»
2 weeks 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)

  • »
    »
    2 weeks 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

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

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

      • »
        »
        »
        »
        2 weeks 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

»
2 weeks ago, # |
  Vote: I like it -7 Vote: I do not like it

something new

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

nung nung

»
2 weeks 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.

»
2 weeks ago, # |
Rev. 2   Vote: I like it -53 Vote: I do not like it

I like nice weather :)

»
2 weeks ago, # |
  Vote: I like it -19 Vote: I do not like it

i wish to you all It will be Great Round for all of us

»
2 weeks ago, # |
  Vote: I like it -29 Vote: I do not like it

I suspect too many hacks or fst for B

»
2 weeks ago, # |
Rev. 2   Vote: I like it -39 Vote: I do not like it

sorry

»
2 weeks ago, # |
  Vote: I like it -17 Vote: I do not like it

More generic test case would have been better to understand problem B.

»
2 weeks 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.

»
2 weeks ago, # |
  Vote: I like it -39 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...

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +57 Vote: I do not like it

    you are salty

  • »
    »
    2 weeks 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 - Diana and Liana.

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it +45 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.

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Fully agree with you

      • »
        »
        »
        »
        2 weeks 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.

        • »
          »
          »
          »
          »
          2 weeks 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.

»
2 weeks ago, # |
  Vote: I like it +33 Vote: I do not like it

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

  • »
    »
    2 weeks 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.

»
2 weeks ago, # |
Rev. 2   Vote: I like it -28 Vote: I do not like it

deleted

»
2 weeks ago, # |
  Vote: I like it -60 Vote: I do not like it

damn wrong alarm about the good round. damn wrong.

»
2 weeks ago, # |
  Vote: I like it -24 Vote: I do not like it

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

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +63 Vote: I do not like it

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

    • »
      »
      »
      2 weeks 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.

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        F is definitely not math.

      • »
        »
        »
        »
        2 weeks 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.

»
2 weeks 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...

»
2 weeks 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?

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    It is not understandable either way.

  • »
    »
    2 weeks 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

  • »
    »
    2 weeks 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.

    • »
      »
      »
      2 weeks 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)$$$.

  • »
    »
    2 weeks 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).

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What was pretest 15 for C?

»
2 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

What the hell is pretest 5 in C

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C ?

  • »
    »
    2 weeks 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.

»
2 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

How to solve E and F?

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

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

»
2 weeks ago, # |
  Vote: I like it +25 Vote: I do not like it

Modforces :)

»
2 weeks 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.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Whats B pretest 6???

»
2 weeks 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....

»
2 weeks 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?

»
2 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

What is pretest 4 in Problem B ?

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For instance :
    2 2
    0 0
    1 1

  • »
    »
    2 weeks 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?

    • »
      »
      »
      2 weeks 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

      • »
        »
        »
        »
        2 weeks 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.

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

Pretest 12 in D? how to solve D?

»
2 weeks ago, # |
  Vote: I like it +17 Vote: I do not like it

13444 Registered users, new Record?

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

what is pretest 13 in C?

»
2 weeks 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

  • »
    »
    2 weeks 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.

    • »
      »
      »
      2 weeks 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

      • »
        »
        »
        »
        2 weeks 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.

        • »
          »
          »
          »
          »
          2 weeks ago, # ^ |
            Vote: I like it -8 Vote: I do not like it

          Wow a log(250) is only 7, but it surely kills

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

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

    My code: pastebin

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

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

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

    can you please explain your approach ?

    • »
      »
      »
      2 weeks 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 :)

»
2 weeks 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

»
2 weeks 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://codeforces.com/contest/1228/my

  • »
    »
    2 weeks 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

    • »
      »
      »
      2 weeks 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.

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        not your mind, whoever clicks on that.

      • »
        »
        »
        »
        2 weeks 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 -_-

»
2 weeks 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?

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
2 weeks 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://codeforces.com/contest/1228/submission/61498112 (commented code)

»
2 weeks 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.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
2 weeks 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.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Can you clarify to me which 3 tasks are combinatorics?

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Well, a lot of stsfails at B again?

»
2 weeks 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.
  • »
    »
    2 weeks 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

    • »
      »
      »
      2 weeks 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.

  • »
    »
    2 weeks 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.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How to solve D?

»
2 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

Wowwww... Great contest <3

»
2 weeks 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.

»
2 weeks 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?

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

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

  • »
    »
    2 weeks 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$$$

»
2 weeks 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

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Was the diagram for the sample input/output for 1228D - Complete Tripartite added partway through the contest or after the contest? I don't remember seeing it when I solved the problem.

»
2 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

Thanks for the problem C test 3 overflow warning.

»
2 weeks 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.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

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

    • »
      »
      »
      2 weeks 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.

  • »
    »
    2 weeks 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.

»
2 weeks 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!

»
2 weeks 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 ;(

  • »
    »
    2 weeks 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 ;(

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Position Zero! This is Tendo Maya. (((

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

Thanks to McDic, I'm purple ^_^

»
2 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

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

»
2 weeks 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
  • »
    »
    2 weeks 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 :(

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it -67 Vote: I do not like it

      How is a simple sorry justified for those who lost rating due to more wrong solutions accepted for Problem D?

»
2 weeks 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?

»
2 weeks ago, # |
Rev. 2   Vote: I like it +24 Vote: I do not like it

McDic Thank you for this awesome contest.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve B. I could not find any idea

»
2 weeks 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.

»
2 weeks 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.

  • »
    »
    2 weeks 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.

    • »
      »
      »
      2 weeks 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.

»
2 weeks 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.

»
2 weeks 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...

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

It was a great contest although I didn't get to participate in it. Problem C was a very interesting and challenging problem. I feel bad for not participating this round.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

For question C of this Contest I have a Problem.In my editor the code is compiled and run succssfully and giving the correct answer but in codeforces editor it is giving wrong answer. I want to know why this is happening??

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi, How can I avoid overflow in question C?

  • »
    »
    2 weeks 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.

  • »
    »
    2 weeks 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).

»
2 weeks 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.

  • »
    »
    2 weeks 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

»
2 weeks 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...

»
2 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

This round is way better than the last one.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Could you please update tasks' ratings?

  • »
    »
    2 weeks 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.