Блог пользователя sshwyR

Автор sshwyR, история, 4 года назад, По-английски

Hello Codeforces! We (dqa2021, Xiejiadong, Retired_xryjr233, Z18 and me) are excited to invite you to take part in Codeforces Round 664 (Div. 1) and Codeforces Round 664 (Div. 2), which will happen on Aug/12/2020 17:35 (Moscow time).

Huge thanks to:

There will be 5 problems in Div.1 round and 6 problems in Div.2 round. You'll be given 2 hours to solve them.

The story of this round is about that man. Instead of displaying his name, I prefer telling one of his legends (or joke):

"I have a 'friend', who makes lots of money every day, earning a billion in the blink of eyes. With a wave of his hand, OIers all over the world will follow him."

You can post your guesses in the comments.

UPD: Score Distribution:

  • Div.1: 500 — 1000 — 1500 — 1750 — 2500
  • Div.2: 500 — 750 — 1000 — 1250 — 1750 — 2250

Good luck!

UPD: Congratulations to the winners!

Div.1:

  1. Benq
  2. ecnerwala
  3. nick452
  4. 244mhq
  5. neal

Div.2:

  1. C.S.T.T
  2. MyLoveKUN
  3. Rchen3
  4. Rainbow_qwq
  5. evilbuggy
  • Проголосовать: нравится
  • +583
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +60 Проголосовать: не нравится

    What's the point of declaring top 5 people in Div.2, after all they are just Div.1 guys who registered with their alternative account, isn't this unfair? for example just look at the person who is placed 3rd in Div.2, this guy was newbie, like seriously? This disrupts entire rating distribution.

»
4 года назад, # |
Rev. 4   Проголосовать: нравится +410 Проголосовать: не нравится

I am tester, please upvote for me! :)

( I'M CUTE, GIVE ME CONTRIBUTION )

»
4 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Is the man is Bill Gates? :D

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

is that man Jack Ma? just a random guess

»
4 года назад, # |
  Проголосовать: нравится +149 Проголосовать: не нравится

We don't want stories please, as they come in the way of easily comprehending the problem statement. :(

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +77 Проголосовать: не нравится

    Oh don't worry. The statement is not long and we just use the main character to describe it. The story itself is easy to comprehend :)

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      For me who is afraid of number theory, this is good news to be happy about. If there is a math problem, I am also ready to change to the alternate.

»
4 года назад, # |
  Проголосовать: нравится +280 Проголосовать: не нравится

Tester — Planning to participate in the next div 1.
sshwyR — You already tested it.
Tester -

Spoiler
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +65 Проголосовать: не нравится

    MeToo

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +78 Проголосовать: не нравится

    This contest was put on hold for a long time due to the difficult Di2A.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +70 Проголосовать: не нравится

      difficult Di2A

      Thank you , now excuse me while I go to sleep for 35 hours real quick

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +10 Проголосовать: не нравится

        Go for 40 , than that would be sacrilegious

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится +22 Проголосовать: не нравится

          Two set violin = small pp

          • »
            »
            »
            »
            »
            »
            4 года назад, # ^ |
              Проголосовать: нравится +4 Проголосовать: не нравится

            Bass = pp large

            • »
              »
              »
              »
              »
              »
              »
              4 года назад, # ^ |
                Проголосовать: нравится +2 Проголосовать: не нравится

              What? You bass gang, had some arguments before, but now is just butthurt, VIOLIN > bass. TwoSet responded to all Davie's videos, but Davie just ignored the "bass diss track" (which was asking for a livestream at the end) and the "davie fakes playing the violin". Brett played bass poorly, but it was REAL, but Davie, on the other hand, FAKED playing it. So what side is winning, huh?

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      Oops, difficult Di2A. So scary....

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Is this difficult div2A? Then what about the contest, which was for Russian elementary school students, with a 1700 rating problem A. (it was like 10 contests before) :D

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Feeling sad for such testers but they will get contribution.

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Well I knew I wont participate in one div1 when I was testing. Anyways I did participated but in unrated mode. Just that I didnt knew I wont be participating on 12 Aug.

      Spoiler
»
4 года назад, # |
  Проголосовать: нравится +60 Проголосовать: не нравится

Another Chinese Round! This round has special and interesting stories.Good luck and have fun for every contestants. Some information in advance:Those stories may all be about one mysterious person.

[O)]-[(O]/

»
4 года назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

Is the man @MikeMirzayanov ? <3 i have not any guess about his income but i love him and want to see his name in the problem statement ..

»
4 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Mukesh Ambani???

»
4 года назад, # |
  Проголосовать: нравится +32 Проголосовать: не нравится

Boss Cai!!

»
4 года назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

I am almost sure this man is Jack Ma.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I want to know what is Polygon platform ? Strange word for me

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I know! The man is Cai Rui[user:Boboniu]!

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +7 Проголосовать: не нравится

Intersting fact: tourist will set a new best rating ever on codeforces if he wins this round!

»
4 года назад, # |
  Проголосовать: нравится -18 Проголосовать: не нравится

Chinese Round?

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +199 Проголосовать: не нравится

Fun fact: seeing MiFaFaOvO can't participate in this round, if he doesn't in the next global round, he will vanish from the live standings xD

And "poof": he is gone xD

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Excuse my ignorance, but what is the rule exactly you're talking about?

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 2   Проголосовать: нравится +52 Проголосовать: не нравится

      Only the users which participated in a rated round within $$$6$$$ months will be included in the Rating Standing.

      The last rated round for him took place on $$$Feb^{17th}$$$.

»
4 года назад, # |
  Проголосовать: нравится +70 Проголосовать: не нравится

I guess it's CCF

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I do CP for fun.. What about you guys?

»
4 года назад, # |
  Проголосовать: нравится -118 Проголосовать: не нравится

BINOD !

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

It's Mr-Cai!!! Hahahaha

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

When I see Chinese round, I think of Mathforces.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

so... Yet another maximizing profit problems ... or Yet another guessing name problems :v

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Ronan Ryan?

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

interestingLSY Time for your picture about boboniu!

»
4 года назад, # |
Rev. 3   Проголосовать: нравится -14 Проголосовать: не нравится

Ah-oh, jqdai0815 as a tester, which means we can't see his competition with tourist this time. A huge pity!

»
4 года назад, # |
  Проголосовать: нравится +69 Проголосовать: не нравится

He must be Zide Du(杜子德) from the CCF.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Is him, right ?

»
4 года назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится

Please provide short statements for problems and understandable english,I am learning english .Thanks

»
4 года назад, # |
Rev. 11   Проголосовать: нравится -64 Проголосовать: не нравится

[Deleted]

»
4 года назад, # |
  Проголосовать: нравится +49 Проголосовать: не нравится

See this 89567737

»
4 года назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

What's happening to "timeanddate.com"? :|

»
4 года назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

Boss Cai -- boboniu

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

Makes lots of money everyday. That must be dzd from CCF(China Collecting-money Foundation)!

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I became psychopath because of the little pony, please make sure that the problems have short statements. with appreciation to your great story.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I really hope that the problems are not as hard as the quiz.....

»
4 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

How many number of common problems ?

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Richie Rich?

»
4 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

It could be suneo's dad from doraemon xD

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

is it jeff bezos ?

»
4 года назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

Olers?

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Is that man Mark Zuckerberg??

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится
The Man is:
»
4 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Is the man Mike Mirzayanov ?

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

JPow?

»
4 года назад, # |
  Проголосовать: нравится +41 Проголосовать: не нравится

If there are unnecessary stories, please, do mark them in Italic or any other way. I've faced a lot of issues about bad storytelling in Codeforces. :)

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

What are "Olers"?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +14 Проголосовать: не нравится

    The people like us. Take part in OI. OI, Olympics Information. OIer, the people learn OI. OIers is plural form of OIer. Understand? :)

    I'm not good at English. I hope you can understand xD

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    OIers are coders who participate in programming competitions (mostly used in China I guess). OI = Olympiad Informatics

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    It's what Chinese called people who participate in Olympic in Informatics contests.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    The goalkeeper of RCD Espanyol, click the link for more details.

    https://www.transfermarkt.de/oier-olazabal/profil/spieler/8176

    Since Wu Lei (the best football player in China) is also in this team, we use the word "Oier" to show our respect to RCD Espanyol so that they pay Wu Lei on time.

»
4 года назад, # |
  Проголосовать: нравится -14 Проголосовать: не нравится

i guess Jack Ma .

»
4 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

I guess he's kkksc03, head of Luogu(an oj in China). For every monthly contest in Luogu, if you want to watch the video tutorial, you must pay 10¥ first. And what's more there's lots of OI online lesson made by Luogu in every summer and they're not free! So he can make lots of money in this way.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Actually, according to himself, the money is not paid to him directly and a lot of money is spent in maintaining Luogu's website. And the lessons' money will be given to the teachers. So I'm very sure that it's not him.

»
4 года назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

Any hint about no of common problems or score distribution ?

»
4 года назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

Score Distribution?

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Obviously,the man is DUZIDE:P

»
4 года назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

Score Distribution?

»
4 года назад, # |
Rev. 2   Проголосовать: нравится -9 Проголосовать: не нравится

I have a request for MikeMirzayanov.. can we have TEAM contest at codeforces.

»
4 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

It's €€£

»
4 года назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

sshwyR how many problems will be common in both divisions?

»
4 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +36 Проголосовать: не нравится

Today's tester busy with increasing their contribution .

»
4 года назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Div2 Problem E with 1750 (^_^)...it should be solvable

»
4 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

iam not a tester, but please upvote for my pp :).......

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

The man must be, President of IOI: Richard Forster

»
4 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Zhengru IOI will be internationalized.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Karuna! :D

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

An off-topic question: how can I view the past contests right before contests?

»
4 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Too much if else... :(

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Normal Div1:

Try to solve more problems

Horrible Round #664 Div1:

Try to solve the first problem faster

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +27 Проголосовать: не нравится

    No,you should try to avoid FST instead of solving problems faster. It's my final standing: xjpbmbrm.png

    (I was rk128 before the system test...)

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

If I accept no question am i still rated?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +28 Проголосовать: не нравится
    if(submit any problem solution) Yes
    else No
    accept or not doesn't matter
    
»
4 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

why they set so hard

»
4 года назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

Was this the "Single Test Case" Contest?

»
4 года назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится

Really nice problems and clear statements. Enjoyed taking this contest :D

»
4 года назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

Codeforces rounds are great, they teach us how to look at a problem in a simple manner, without overcomplicating it. orz Great contest.

»
4 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Well well well, once again someone posted solutions on youtube during the contest, you can even see his username in the video, i wonder if these guys are shameless or what Video link Username: Khayrulmithu

»
4 года назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

I really liked d1 B, but...

Starting from any vertex u

This would be much more understandable if it said from all vertices. Wasted lots of time solving the wrong problem.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    That could confuse people into thinking that it's possible to start from multiple vertices simultaneously, I think the clearest is "for all vertices u, starting from u, ..."

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I'm pretty sure that "any" was actually used correctly here

»
4 года назад, # |
  Проголосовать: нравится -14 Проголосовать: не нравится

What was the point of swapping X and Y in Div2B?

»
4 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Does this works for Div-2 E — Make a graph $$$g[i][j][k]$$$ = how many edges exist such that its head is on node with $$$i$$$ outgoing edges and tail is in node with $$$j$$$ outgoing edges and it is $$$k'th$$$ smallest one. Then we brute force every $$$c_i$$$. That will be $$$O(k!k^2)$$$

»
4 года назад, # |
  Проголосовать: нравится +122 Проголосовать: не нравится

The whole round is like an ingenuous play of MiFaFaOvO to get back his first place in the rating (though unsuccessful). Chinese people are really good at the art of war. My respect.

(please don't take this very seriously)

»
4 года назад, # |
  Проголосовать: нравится +41 Проголосовать: не нравится

Why the "non-empty" in C? I guess it has to do with printing the output but it reduced problem quality by like 30%.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится -18 Проголосовать: не нравится

    could u plz xplain how to solve todays div2 C problem

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +35 Проголосовать: не нравится

      You do realize that I haven't read Div 2C?

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится -29 Проголосовать: не нравится

        ok..if someone other can help..bcz..i am very curious about it..that why my logic was wrong..even on sample test cases ..i know i was completely wrong.can not wait till editorial..xD

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +39 Проголосовать: не нравится

    Might as well allow output of negative length to boost problem quality?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    OH SHIT I missed it. Even my starting answer is an empty string. Luckily my code goes for large strings first when improving the cost in binsearch, so I got AC.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Is C checking if a cube like shape fits all of the given points by binary search / math?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Yes!But I am too weak at geometry,I come up with this idea quickly but don't know how to compute the area covered by several polygon...

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 2   Проголосовать: нравится +22 Проголосовать: не нравится

      Maintain the minimum and maximum values of $$$N$$$, $$$B$$$, and $$$N - B$$$.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +24 Проголосовать: не нравится

      Several polygons? I think it reduces to finding the minimum side length of the square in a shape like this that can fit all the points, which should be fairly easy. But I spent most of the contest thinking I had to minimize the sum of distances instead of the maximum, so I couldn't implement it in time.

      cube

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Rather diamond-like (with top-left and bottom-right edges cut). Math seems awful there.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

How to solve Div2C? Also, where does the N^2 check all pairs approach go incorrect?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    Final Answer can be at most $$$2 ^ {9}$$$, so just brute force for every possible value, and pick the smallest.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Thanks.

      Do you think there a polynomial-time solution in case final answer is large?

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        I have O(n^2 log m), where m is the size of the largest input integer.

        Figure out how many leading zeroes we can get by picking greedily the pairs where the bitwise-and has the most leading zeroes, using O(n^2) time. The next bit has to be a 1 in any solution, so we can add that bit the the answer. Since the bit will be a 1 in any case, we can ignore is from now on: we set it to zero and find out again how many leading zeroes we can now get. Repeat until we can get all zeroes.

        https://codeforces.com/contest/1395/submission/89696109

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Your implementation is too elegant :)

  • »
    »
    4 года назад, # ^ |
    Rev. 3   Проголосовать: нравится +12 Проголосовать: не нравится
    I solve this way
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Now I feel like an idiot,spend half an hour in implementing an dp solution..:/

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Hey can we solve problem C it using Dp??
        I tried some approach but its giving wrong ans.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Can you explain this approach?

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        My english is so bad.sorry.if you understand its my pleasure <3
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Very clean aproach, fix the answer and check there are N pairs a[i]&b[j] that has the same bit positions. I spend 1 hour until I reach my dp aproach...

»
4 года назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

Is 1C a geometry problem? I thought it just need to binary_search and compute the area covered by several polygon..

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I passed the pretests in Div2B with a backtracking solution, how is that a thing?

»
4 года назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Hints for $$$Div 2 E$$$ Please?

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

    Assume you have selected a tuple. Of course, you can now reduce the initial graph to one such that each node has out-degree of 1. Realise that for each node to be in a cycle in this resulting graph (and thus be possible to reach back to it in finite time), each node must also have an in-degree of 1.

    For each node (let it be Q), traverse over all nodes that point to it, let's call these set of nodes P. You can easily determine that for which value in the tuple will these nodes in P be pointing to Q. Also, this means that these values can not co exist in the tuple, since that would mean that multiple nodes point to Q in the resulting graph. Thus, you make a list of all these invalid combinations.

    Iterate over all K! tuples, and for each check if they consist of an invalid combination. If not, then it is valid.

    Sadly, was a bit late while implementing in contest :(

    Here's my AC code: https://codeforces.com/contest/1395/submission/89731507

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      What's the upper bound of the number of those invalid combinations?

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +16 Проголосовать: не нравится

        By an invalid combination, I mean pairs $$$((i, j), (k, l))$$$ such that value $$$j$$$ at index $$$i$$$ in the tuple, and value $$$k$$$ at index $$$l$$$ in the tuple, are incompatible. So the maximum number of such invalid combinations are $$$K!(K!+1) / 2$$$.

        You just have to store all these pairs in a $$$K*K*K*K$$$ matrix.

»
4 года назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

1250 not enough points for Div.2D

»
4 года назад, # |
Rev. 3   Проголосовать: нравится +8 Проголосовать: не нравится

Long Long in problem A just ruined my whole contest.I almost wasted 50min behind it.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

In Div2C, Sample test 3, what combinations get the final result as 147? The minimum I could get was 177.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I think you applied the dp approach. I did the same thing at first and waste a lot of time. just brute force the answer

  • »
    »
    4 года назад, # ^ |
    Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

    I think this was the combination

    Spoiler

    these are indices of the element from array a and b

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    I also got the same error during the contest but now I understand. Well, let's say our solution consists of two parts, 1 and 2. I am not going to explain the second part assuming you already know it.

    But in the first part, u must be choosing a minimum c1 among all possible c1 and then doing part 2 of the solution but we are doing a mistake here. Actually, part 1 of the solution has n possibilities. Choosing minimum c1 is just one of the possibilities. A second possibility, for example, can be choosing a minimum c2 and then doing part 2 of the solution. Similarily choosing a minimum c3 among all possible c3 can be the third possibility and so on. So there are n possibilities.
    So the solution is O(n^3) and not O(n^2). wicardobeth

»
4 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

i will fst in d,One detail was not considered,shit.

»
4 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

That was implementationforces, I like that. Should be enough to become blue again :)

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    What was the solution to D?

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

      Greedy.

      Edit, more understandable: We devide $$$a[]$$$ into set $$$a[]$$$ and $$$b[]$$$, where all $$$b[i]<=m$$$ and all $$$a[i]>m$$$

      Sort both sets biggest element first.

      Then choose consecutevly to use i elements from a[]. Foreach i we can calculate how much elements from b[] can be used then, and using prefix-sum calc in O(1) the funfactor of that i.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +4 Проголосовать: не нравится

        If only I had two more minutes to fix my implementation

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Figured that, but couldn't implement. Thanks, will wait till I can see your submission.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    I am used to see you in blue ;)

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

How to solve div2 D?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    1) Make 2 lists: one of all greater than m (let us call it gr), second all less than m(let us call it sm). 2) Sort gr reverse and sm normally. 3) Now compare highest unused of gr with sum of d consecutive of sm. If gr highest is greater than simply add that to ans(in other words muzzle d smallest elements of sm). Take care of these things: 1) Do the above only till you have atleast 1 element left in gr, cause you can add it in the end. 2) If you encounter condition like less than d elements remaining in sm, then dont compare with gr greatest element as you can add all remaining along with greatest, if greatest goes in the end. 3) In the end try to put all remaining elements of gr in the end of the permutation seperated by d elements each. For details see the code: 89725326 If I fail system test ignore this comment :D

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone please tell me what's wrong in my code? Problem A https://ide.codingblocks.com/s/308173

»
4 года назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

Can someone tell me why this solution to 1C is wrong?89722745

I can't find the mistake :(

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Boboniu stands nowhere in front of Binod

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Any Idea of Test 16, Div1 B ?

»
4 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

How to solve Div-1 B??

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Need help, why did my solution for Div2B did not pass ? I have used dfs- https://codeforces.com/contest/1395/submission/89714645

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Problem A: What is the problem with my this python code?

I decremented min(r, g, b) from r , g, b. Then count how many of them are odd from r, g, b, w. If number of odds > 1 the answer is "No", else "Yes".

Sorry for bad English.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    What if input is 2 5 7 3. Now if u decrement r g b by 2, then r b g will be 0 3 5 and w will be 9.

    No.of odds will be 3 (0 3 5 9)..so it return "No"

    But if I remove only 1 from r g b then r g b will be 1 4 6 and w will be 6. (1 4 6 6), we can form a palindrome.

    Decrementing min(r,g,b) is wrong step.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

Can someone give a small hint for 'B'?

As far as I understand:
1) The requirement "should be able to return back" is equivalent to:
= edges that satisfy Ci-rules should form loops
= every vertex should be a part of a loop
= every vertex should have an active edge coming in — this is what we need to check
2) k <= 9 so 1*2*3*4*5*6*7*8*9 = 362880 total sequences of Ci.
If we were able to somehow check whether a specific sequence is good fast, than we could just enumerate all sequences and count the good ones.

Am I correct with (1) and (2)? If no, a small hint would be appreciated.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Isn't the total number of sequences = k^9?

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      No, since c_i <= i, not c_i <= k

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      No, because 1 <= C[i] <= i

      Remember, C[i] — is the index of the edge you would take if there are 'i' outcoming edges. This index can't be say 7 if there are only 3 outbound edges.

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится

    Sufficient and necessary condition is that each vertex has exactly one incoming edge. Everything else in your (1) follows.

    I build a bruteforce on top of that with

    P.S. It's pretty standard Markdown, so use two spaces before newline
    like this

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      How do you prove that?

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Necessary is obvious — no incoming edge, no cycle for that vertex.

        Sufficient: start from vertex and start moving. At some point you will have to return to starting vertex.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится

        If a node $$$x$$$ has no incoming edge, it's impossible to reach $$$x$$$ starting from $$$x$$$.
        If a node $$$x$$$ has indegree $$$\geq 2$$$, let $$$a, b$$$ be two nodes such that edges $$$(a, x)$$$ and $$$(b, x)$$$ exist. But if you start from $$$x$$$ you can't reach both $$$a$$$ and $$$b$$$ (wlog, if you reach $$$a$$$, you return to $$$x$$$ and you haven't visited $$$b$$$); in this case, if you start from $$$b$$$ you reach $$$x$$$ at the next step and you can't go back to $$$b$$$.

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          what if there is an edge (a, b) along with (a, x) and (b, x) ? Then can't it be the case such that: x -> ......... -> a -> b -> x. ?

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Then how to check if some node has no incoming edge?

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +11 Проголосовать: не нравится

        Each assignment $$$c_i = j$$$ will guarantee incoming edges for some number of vertices. If you sum this up over all assignments you make, just check that it adds up to $$$n$$$.

        The issue is that this can double count, however note that each vertex should have exactly one incoming edge, not more, so each assignment $$$c_i = j$$$ will exclude some other list of assignments $$${c_{i'} = j'}$$$. Just make sure to never make two conflicting assignments like this.

      • »
        »
        »
        »
        4 года назад, # ^ |
        Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

        You have n edges, so it's enough to check that no vertex has two incoming edges. Precompute 'bad' pairs (i, c_i), (j, c_j), such that some vertex will have two incoming edges.

        Simple bruteforce after that.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    You are correct with both (1) and (2).

    Here's a good hint. Imagine that for a certain tuple of C, we get the edges 1-2,2-1,3-4,4-3. This is equivalent to saying that nodes [1,2,3,4]->[2,1,3,4] which is a permutation! How can you use this insight to solve the problem in general?

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      Agnimandur kilotaras thanks! Solved!

      The core idea is to:
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I thought the exact same thing and could not determine how to check every possible sequence in an optimized way.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Does anyone know if there is a testcase on Div1B which breaks the hashing solution for the MOD 1e9+7?

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Very nice problemset, reminded me to practice.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +99 Проголосовать: не нравится

[deleting this because it came out wrong. I'm referring to Chinas efforts in testing all of Wuhan, which is amazing, not them experimenting and creating the virus (which I think is false).

I can't delete this, so if some CF mod could for me that'd be great.

»
4 года назад, # |
  Проголосовать: нравится +103 Проголосовать: не нравится

the use of "muzzle" in problem A felt rather odd.

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

tourist RIP rating

»
4 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

FAILED TEST 31 IN C? GOING BACK TO DIV4.

»
4 года назад, # |
Rev. 4   Проголосовать: нравится +74 Проголосовать: не нравится

I am surprised by the number of high-rated coders who do not realize that in Div1B, the in-degree of each node can be up to O(n), and iterating through pairs of nodes which go into a particular node can take quadratic time in the worst case.

I am also surprised that there was no pretest against such solutions. But I think this is fair. Contestants are responsible for ensuring that their solutions' time complexities are acceptable.

»
4 года назад, # |
  Проголосовать: нравится +41 Проголосовать: не нравится

Pretests were way too weak, just look at the amount of failed submissions in Div1 ...

»
4 года назад, # |
  Проголосовать: нравится +30 Проголосовать: не нравится

What the hell were you guys thinking. I don't usually get mad, but now I am mad. This contest honestly has made me not want to do cf anymore

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +22 Проголосовать: не нравится

Absolutely disappointed

»
4 года назад, # |
  Проголосовать: нравится +37 Проголосовать: не нравится

my disappointment is immeasurable and my day is ruined

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

My only question is why?

»
4 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Weak Pretests :(

»
4 года назад, # |
  Проголосовать: нравится +35 Проголосовать: не нравится

WHYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY

»
4 года назад, # |
  Проголосовать: нравится +29 Проголосовать: не нравится

So many main tests failing

»
4 года назад, # |
  Проголосовать: нравится +42 Проголосовать: не нравится

Worse pretests ever.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится -9 Проголосовать: не нравится

89726386 here is my solution for D, it for some reason gave no output nor any errors. its probably a silly mistake, but i cant find it. could anyone help please?

»
4 года назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

I was so happy after giving the round but Wrong answer on test 31.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Going to Specialist~~~

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Even though the round was great with short (and to the point although a bit unclear initially) problem statements, I found the pretests to be weak..lots of solutions are failing the system tests.

»
4 года назад, # |
  Проголосовать: нравится -15 Проголосовать: не нравится

Very weak pretests for Div2 D , even the most simple side cases werent inside the tests.

»
4 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Am I the only one who solved Div2 C with dp? 89700923

»
4 года назад, # |
Rev. 5   Проголосовать: нравится +303 Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +70 Проголосовать: не нравится
Mood
»
4 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

( ཀ ʖ̯ ཀ):

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Alot of solutions are getting rejected after passing pretests i think

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why doing nested ternary search is correct in problem C?

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why is brute force O(n*m) failing for div2 C ?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    No it doesn't. My O(2^9 * n * m) worked fine.

    I can't see a div2 C submission on your profile. Can you share your code

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится
      #include <bits/stdc++.h>
      using namespace std;
      typedef long long ll;
      #define mod 1000000007
      
      int main(){
          int t=1;
          while(t--){
              ll n,m;
              cin>>n>>m;
              ll a[n];
              for(int i=0;i<n;++i)cin>>a[i];
              ll b[m];
              for(int i=0;i<m;++i)cin>>b[i];
              vector<ll> c;
              for(int i=0;i<n;++i){
                  ll minn = INT_MAX;
                  for(int j=0;j<m;++j){
                      minn = min(minn,(a[i]&b[j]));
                  }
                  c.push_back(minn);
              }
              ll ans = 0;
              for(int i=0;i<c.size();++i){
                  ans = (ans|c[i]);
              }
              cout<<ans;
          }
          return 0;
      }
      
      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        It's not always optimal to take $$$min(a_i$$$ & $$$b_j)$$$. Which bits you are taking matters.

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          can you elaborate with an example please?

          • »
            »
            »
            »
            »
            »
            4 года назад, # ^ |
              Проголосовать: нравится +1 Проголосовать: не нравится

            Let's say the answer has a particular bit set to 1, so it means that atleast one of c1,c2...cn will definitely have that particular bit set to 1. In that case we don't need to try and set that bit to 0 for other values in c1,c2...cn by doing the AND operation since the answer would still have that bit set to 1. Guess that makes it clear why taking the minimum won't help here, it's the bits you are taking that matter.

          • »
            »
            »
            »
            »
            »
            4 года назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            3 2
            13 5 8
            4 9
            

            Your code's output is $$$5$$$. But the answer is (13 & 4) | (5 & 4) | (8 & 4) = 4.

»
4 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

When you're feeling good after a contest getting A B and C, and it's looking like you're going to gain a lot of rating, and it just all gets crushed by failed system testing due to weak pretests :(

»
4 года назад, # |
  Проголосовать: нравится -16 Проголосовать: не нравится

PLEASE MAKE PRETESTS STRONG !

»
4 года назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

My div2A failed test 10 ,and div2B failed test 39 :( Why these tests were not used in contest ?

»
4 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Everyone to their before system testing score: Those son of bitch lied to me!

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

in B div1 I don't get why the 9!*9*9 ~= 3e7 should not pass the tests but with some optimizations it should pass. the 1s time limit is so stupidly chosen.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Your code seems to have complexity not 9!*9*9, but way more. If there is a vertex, with $$$O(n)$$$ incoming edges it will be quadratic.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится

      Ow right. but it need just a sort and unique and it will be ok. pretest must include these kind of tests i think.

»
4 года назад, # |
  Проголосовать: нравится -20 Проголосовать: не нравится

Pretests just ruined this (I don't think it is supposed to be that many "failed on systests"). Your contest suck!

»
4 года назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

Over 850+ System test failed in problem C. Including me :(

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

The following submission https://codeforces.com/contest/1394/submission/89716136 gives runtime error on pretest 3 on the judge server but it works fine on my local pc and on ideone when tested now. Can anyone tell me why this is going wrong? Is it because codeforces uses the CLANG compiler?

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

    It will give runtime error when less.size() == 1, because you are accessing less.size() - 2 (-1) but unsigned int can't be negative so it becomes UINT_MAX.

»
4 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

The pretests were kinda weak:((

»
4 года назад, # |
  Проголосовать: нравится -15 Проголосовать: не нравится

I think it's not just that getting faild on sample tests decrease our point, because sample tests are for testing our code. In this contest, I get 2 or 3 WA's on pretest 2 of problem A that is a sample test, and it decreased huge points from my solution.

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

I did Div2 C like this: https://codeforces.com/contest/1395/submission/89706416 with O(n^2) complexity but I'm not able to think of a proof exactly for why this is right, can someone help me out?

»
4 года назад, # |
Rev. 3   Проголосовать: нравится +26 Проголосовать: не нравится

Weak pretests! and testers asking for upvotes

me

»
4 года назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +163 Проголосовать: не нравится

To not keep you waiting, the ratings updated preliminarily. In a few hours, I will remove cheaters and update the ratings again!

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

My brute force solution passed Div1B.

Can anyone hack it? :)

this

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hi everyone, I was stuck in Div2-C for more than half an hour. People say if you are stuck for more than half an hour, you shouldn't try more and just wait for the editorial. So, I gave up. Later when only 15 mins were left, the idea struck my mind. And I couldn't implement within those 15 mins. But after the contest, I submitted and it was correct. So, how should I decide whether I should give up or not?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +26 Проголосовать: не нравится

    Never give up in a live contest. Try the other problems, and keep thinking until there's no time left.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

It's so unfair when pretests are too weak, especially in problem C, D. Luckily, I've passed the system test, still, I would say it's not fair.

»
4 года назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

code
Why this solution of O(n*m) for problem C is giving TLE on test 10

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Weak pretests in D. It hurts.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Oh... I get it. They didn't write "we tried to make strong pretests" so they aren't.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone tell why my code for div2 C is giving TLE. code

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

During the contest in Div.2 C, the verdict was pretests passed and after system testing, it became wrong answer on test case 9. Can someone explain me why?

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Failed system test in problem C. And finding out that it can be solved using brute force. Just disastrous.

»
4 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

http://codeforces.com/contest/1394/submission/89728986 A hack for Div1 B

I enumerated all incoming-edge pairs of every vertex in this solution, which has a complexity of O(n^2) in the worst case.

However, it got Accepted when I submitted after contest :(


By the way, I improved my solution and resubmit for 3 times during the contest in order to fix the bug. And, my new code Failed System Test because of another mistake TAT

Wish for stronger system tests :(

»
4 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Ok, I have been trying to debug my code for Div1B for more than 2 hrs, but I am still not able to find why this is failing. Its just a simple brute force. Can anyone point out where I am going wrong?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Your solution undercounted because "cnt == n — 1" ... a valid solution can result in more than one cycles being formed.

    Here is a simple test case to illustrate:

    4 8 9 1 2 1 2 1 3 3 4 2 4 3 4 1 3 10 3 1 30 2 4 20 4 2 40

    The answer is 362880 (equals to 9! which means any valid combination works). Your code ouputs zero.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Ok, I got it. I assumed it will always be one big cycle. My bad, I was mislead by the test cases. Thanks a lot.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

https://codeforces.com/contest/1395/submission/89733714

Can anyone help me out with Task A div 2

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Removing the min from r,b,g is not always correct. If you have more than 1 odd number you only need to remove 1 from r,b,g and add it to w. And if you still have more than 1 odd number the answer is no.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What is test case 16 of div2 D can anyone help:(

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

System tests ate my rating!

»
4 года назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

int main() { ios_base :: sync_with_stdio(false); cin.tie(NULL); auto startTime = curTime();

int n,m;
cin>>n>>m;

vi a(n);
vi b(m);
rep(i,n) cin>>a[i];
rep(i,m) cin>>b[i];

ll mx=0;
rep(i,n)
{
    ll mn = inf;
    rep(j,m)
    {
        mn = min(mn, a[i]&b[j]);
    }
    mx = max(mx,mn);
}
ll ans=0;
rep(i,n)
{
    ll mn = inf;
    rep(j,m)
    {
        mn = min(mn, mx|(a[i]&b[j]));
    }
    mx=mn;
    ans = max(ans,mn);
}

cout<<ans<<endl;

Can anyone explain the logic of this solution? I saw same thing in many accepted solutions.

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    In the first loop, $$$mn$$$ is the minimum $$$a_i$$$ & $$$b_j$$$ for each $$$i$$$ and $$$mx$$$ is the maximum $$$mn$$$. This indicates that after performing $$$OR$$$, the answer will be at least $$$mx$$$ and it can be more than $$$mx$$$ if other $$$mn$$$ has some on bits which are off in $$$mx$$$. In the second loop, we are just turning on those off bits of $$$mx$$$ to find the final result.
    UPD: This solution doesn't provide correct output for all cases.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      How can you say that answer will be atleast mx?

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Because $$$OR$$$ of $$$x$$$ and $$$y$$$ is never less than $$$x$$$ or $$$y$$$. That's why after performing $$$OR$$$, the answer will be at least $$$mx$$$.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Submissions with this solution is getting uphacked.

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      This solution seems to have a wrong output on Test 32

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Which test case?

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
          Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

          On Test 32, which inputs : 54 12 435 115 422 469 19 176 292 395 273 217 160 343 277 500 124 360 315 59 2 477 465 138 175 392 146 438 4 96 231 182 257 183 51 117 430 125 167 107 238 66 236 96 319 62 365 186 83 414 166 198 224 129 60 195 327 62 310 278 300 228 295 113 502 320 463 223

          we should output 63, but this code runs with an answer 62 .

»
4 года назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

Problems from this round are really nice ones! Maybe the pretests could have been stronger. My friend's code for problem Div1C is $$$O(n^2*log(n))$$$ and it passed pretests. I'm not sure if it is a good idea to use such weak pretests for CF rounds. Besides that, this was an interesting round. I enjoyed thinking Div1B. Thank you for your effort! :)

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +132 Проголосовать: не нравится

In 1394C - Boboniu and String, there was no test with a string longer than $$$200\,000$$$ (while the limit was $$$500\,000$$$). People could use too small arrays or iterate/binarySearch in much smaller range. Come on, doesn't Polygon warn you automatically if you don't hit some min/max value?

My sad story is that I noticed my own mistake during a contest, resubmitted and thus dropped 5th -> 20th place. My first code gets AC though, and only now I uphacked it with one long string.

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

I develop app , CP helps me build logic and thinking capability.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится -18 Проголосовать: не нравится

Thanks for the contest! But a little overkill B :( Many people complain about pretests, but I think pretest were actually good (upd: good means not strong, good — finally allows to hack).

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится -8 Проголосовать: не нравится

    Dude, are you nuts ? How can you call the pretests strong ? Every other solution is failing in system testing. Many solutions even failed A and B in Div 2

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I know it is hard skill to read, but try it again. I said "good", I did not say "strong". Also "pretests" is not the same as "tests". And good, because hacking this round was not useless feature again. But I was talking about Div 1. Div 2 A or B probably should have all tests in pretests.

»
4 года назад, # |
  Проголосовать: нравится -34 Проголосовать: не нравится

Is the guy Binod?

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

Any reason why the multiple testcases within a single test format was excluded today? Believe recent rounds had fairly less systest fails cause of that. Might be difficult / annoying for both parties but is still the better & safer choice imo

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Yes and also when I am going through the test cases it seems that the pretests were just randomly made safeguarding the actual main tests.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      How do you know which of those tests were pretests ?

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Just before system tests try using side bar filters present try looking for maximum test on which most of the submissions failed, that number is a good idea of the boundary condition for number of pretest. You have to do these stuffs during the contest.

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Ohh..so u mean out of the N tests that are visible now (after system testing), the pretests are the first K tests ?

          I initially thought that pretests are randomly shuffled in the system tests.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Your profile picture paired with your comment is perfected :o

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Thank You for the Contest, I have finally become candidate master.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In div2 A problems, I found my code is wrong.

input >

1
1 2 2 4

In the above test case, The answer is 'Yes' but my code prints 'No'. 89667141

(If the test case is added, Will the standings be affected?)

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

It is not easy to prepare a round in CF. This round is good except the test cases(not pretest but all test cases in some problems). For instance,in Div.2 C,many participant failed on test 31 which was emerged during the hacking phase. Except that,I am still greatful for the effort of writers and coordinators.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

https://codeforces.com/contest/1395/submission/89766628 This is my answer to div2 E question. But there is a problem. This program cannot be guaranteed to be accepted. So here comes the question. If the program is submitted multiple times during the competition and all pass the pre-test. Which program will you use to run the system test? It is the last submitted program. Or do all programs that pass the pre-test run a system test?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    The last correct submission is judged always.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      OK, thanks a lot. Therefore, if a random algorithm is to be guaranteed to be accepted, it has to run multiple times. It’s just that there is a theoretically wrong probability, even if it’s small

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I'm unable to understand the editorial for div2- C. Can someone explain to me clearly?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    If X|Y = X then no new set bits are introduced in Y. If we have to check whether the answer is atleast X then for every i there should be a j such that (a[i]&b[j])|x = x, we iterate over x and find out which is minimum

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

editorial?

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to prove that the function is unimodal in Div1C(Div2F)?

Thanks

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Btw did nobody notice that div1D had pretests = systests? There were some "WA on pretest 71" during the contest.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In problem 2 the vertical coordinate was X and the horizontal one was Y. Why?

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In Div2 problem E, why aren't the tuple's length equal with the cycle's edge number?

Like in example one, one of the cycle is from node 1 to 2, to 4, to 3, then back to 1 with 4 edges, so the tuple should be (1,1,3,1), right? But the answer tuples are (1,1,3) and (1,2,3). Is there something that I missed about this problem's statement?

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

code why this code for problem C won't get TLE