McDic's blog

By McDic, history, 6 months 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
  • +1581
  • Vote: I do not like it

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

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

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

I like the compact statement part

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

This what they call learning from your failures :)

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

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

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

Wa! Another Korean round!

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

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

Congrats on your round McDic O_o

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

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

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

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

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

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

sounds like an awesome round Good Luck :D

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

GOOD LUCK

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

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

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

I hope it will be very good because it is hard

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

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

Welcome back McDic after 4 months with a new contest;

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

thanks for the improvement :)

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

It must be unrated,right?

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

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

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

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

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

McDic make me "out of competition".

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

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

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

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

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

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

    agree.

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

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

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

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

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

WTF? Why so many upvotes?

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

In ready to compete in excellent contest!

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

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

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

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

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

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

something new

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

nung nung

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

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

I like nice weather :)

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

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

I suspect too many hacks or fst for B

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

sorry

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

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

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

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

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

    you are salty

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

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

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

        Fully agree with you

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

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

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

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

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

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

deleted

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

damn wrong alarm about the good round. damn wrong.

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

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

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

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

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

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

        F is definitely not math.

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

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

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

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

    It is not understandable either way.

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

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

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

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

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

What was pretest 15 for C?

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

What the hell is pretest 5 in C

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

How to solve C ?

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

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

How to solve E and F?

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

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

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

Modforces :)

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

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

Whats B pretest 6???

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

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

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

What is pretest 4 in Problem B ?

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

    For instance :
    2 2
    0 0
    1 1

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

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

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

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

Pretest 12 in D? how to solve D?

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

13444 Registered users, new Record?

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

what is pretest 13 in C?

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

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

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

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

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

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

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

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

    My code: pastebin

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

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

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

    can you please explain your approach ?

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

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

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

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

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

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

        not your mind, whoever clicks on that.

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

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

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

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

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

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

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

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

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

    Can you clarify to me which 3 tasks are combinatorics?

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

Well, a lot of stsfails at B again?

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

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

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

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

    How to solve D?

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

Wowwww... Great contest <3

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

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

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

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

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

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

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

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

Thanks for the problem C test 3 overflow warning.

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

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

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

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

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

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

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

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

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

Position Zero! This is Tendo Maya. (((

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

Thanks to McDic, I'm purple ^_^

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

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

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

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

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

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

McDic Thank you for this awesome contest.

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

How to solve B. I could not find any idea

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

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

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

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

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

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

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

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

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

Hi, How can I avoid overflow in question C?

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

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

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

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

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

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

This round is way better than the last one.

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

Could you please update tasks' ratings?

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

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

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