Sulfox's blog

Codeforces Round #635
By Sulfox, 5 years ago, In English

Riichi...Tsumo! 2 han 2000 points!

Hi! Have you ever heard of the game called Mahjong Soul? It is a Japanese Mahjong game that is famous for the adorable characters.

We are excited to invite you to take part in Codeforces Round #635, where you can help the characters in trouble. This round will be held on Apr/15/2020 17:35 (Moscow time). Most importantly, it is rated for both divisions!

Each division will be given 6 problems and you will have 2.5 hours to solve them. An interactive problem may be found in this round. If you are not familiar with interactive problems, you can learn about them here.

The problems were prepared by EternalAlexander, ustze and me Sulfox.

We sincerely thank isaf27 for reviewing and coordinating the round, and MikeMirzayanov for providing such a great contest preparing environment.

Also thanks to the following testers:

Good luck to all the participants! Oh, one more thing, you can enjoy Mahjong Soul here!

UPD 1: The scoring distribution will be:

  • Div.1: 500 — 750 — 1500 — 2250 — (1750 + 1500) — 3250
  • Div.2: 500 — 1000 — 1500 — 1750 — 2500 — 3250

UPD 2: Protips:

  • There will be a sticker in each problem statement except 1F. If you are not interested in the story of the characters, you can skip the sentences above the stickers.

UPD 3: Congratulations to the winners!

  • Div.1
  1. boboniu (First to solve 1E!)
  2. maroonrk (First to solve 1F!)
  3. Golovanov399 (First to solve 1B!)
  4. Endagorion (First to solve 1D!)
  5. FizzyDavid
  6. faebdc
  7. lzr_010506
  8. yosupo
  9. Isonan
  10. Um_nik
  • Div.2
  1. Bojangles (First to solve 2E!)
  2. JbopkynyRubkLuxSR
  3. 01191020csl
  4. DreamLoIita
  5. hfyzw
  6. -45
  7. soltanmv
  8. Aquaa
  9. 18101130I3 (First to solve 2C!)
  10. DeD_TihoN

UPD 4: Thank you all for joining us! Editorial is out!

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

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

I've been looking forward to this contest for a long time!

Problems provided by EternalAlexander have never let me down.

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

GL & HF!

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

It says there that there will be 2.5 hours to solve 6 problems but on the contest tab it says 2 hours. Which one is correct?

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

Mahjong Soul? Great!

I'm guessing what interesting problems we'll solve. GL & HF !

(づ￣3￣)づ╭❤～

(110 means the phone number of police station，911 in US)

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

You may have already heard of Mahjong Soul here.

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

    Must I use my e-mail adress to register in Mahjong Soul?

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

      That's the case for the English version. Chinese version is down and Japanese version is too slow. You can try to use Google and Facebook if you like.

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

Hey,Sulfox.

What is the score of each question?

Forgive me for my rusty English,QAQ

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

Don't know about other authors, but previous problems by Sulfox were great, looking forward to this round :)

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

Came here for practicing CP and now end up playing Mahjong Soul :3

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

Hope you like our problems. GL & HF!

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

GL & HF. I'm sure you will like the problems lol.

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

Hope the problem statements will be as short as the announcement. Thanks.

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

Hope Strong Pretests .

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

Riichi & Tsumo with just 2 han 2000 points? Why are you willing to choose Riichi nomi? (?)

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

    btw plz no duliu mahjong problems. (Although I know it's impossible lmao)

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

    Riichi-Tsumo-Yifa-Udora10! yakumann! (How Lucky :D

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

      How did you get Udora 10? That's as unlikely as being snapped by lightning

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

what is GL & HF???

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

Hope it will be a great contest!

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

No Mahjong Soul over two weeks. :(

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

I really smiled when I realized that the contest is made by someone from Wuhan , And I hope to see Italians preparing a beautiful round for us very soon <3

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

EternalAlexander is an intelligent problem provider, hope to enjoy more contests prepared by he together with his team.

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

All I know about Mahjong is that its terminology is countably infinite.

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

    Don't worry, the problems won't relate to Mahjong basically ;)

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

Oh godness! Hope the contest will be interesting and not very hard to solve(not AK).

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

Wow, another Chinese round!

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

Chinese round begins at 22:35 in China...

Writers are so considerate for others :)

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

    Not saying this is not OK, as this round is longer than a normal one and prepared by Chinese, why not arrange it to a more convenient time for Chinese while not bringing inconvenience to others? Such as 21:00 in China...I like participating in codeforces round even with the cost of staying up late, but I do hope there are some rounds in a comfortable time for me. And after all, I guess judges also need sleeping.

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

      A lot of rounds at the beginning of the year were at 16:05 UTC or earlier. Even this 14:35 UTC isn't that late in China. Tbh I'd rather have rounds mixed at very inconvenient time and very convenient time for Europe (early morning and evening, e.g. 5:05 UTC and 17:05 UTC) rather than at what's work/schooltime for Europe and late evening for China, like we have here, but it's not like you have it really bad the way it is now.

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

        Sure, I agree with you and I am not commenting to ask for a change but just providing a thought. I remember many Chinese rounds were scheduled to a slightly earlier time.

        And I also agree that contests set in work/schooltime are almost the worst thing to be seen...I prefer staying up late...

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

    I think so. This round will end at 1.05 am. It's a little late for me!

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

Riichi...Tsumo! 2 han 2000 points! what it means?

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

    Both Riichi and Tsumo are kinds of Yaku in mahjong, which are specific combinations of tiles or conditions that yield the value of hands. And 2 han 2000 points is its score.

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

    There is a game called mahjong. These words can be heard when its round ends (and the winning player earns 2000 points).

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

    Only 2000 points is solvable.

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

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

    Have you mentioned that Before quarantine days there was about 10k participants in Div.2 now it is about 20k?

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

Will there be an interactive problem in div 2 also?

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

Although we can't play majsoul in China now, we can take part in a contest of that XD

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

    Use the link provided in the description. It somehow works. Wheeeeeeeeeeeeeeeeee

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

For that '2 han 2000 points' you just have 20 fu. That's quite a bad hand.

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

    Suddenly realize that this is impossible? cuz 20fu + 2fu (tsumo) is at least 22fu. Or Pinfu + Tsumo can be 20fu, but it should be 3 han if there is Pinfu.

    upd : sry, 2 han 30 fu can be 500/1000 when the non-dealer win so it's possible..

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

    No. you will get 1300 in 2/20 and its possible. 2/30 is 2000 and when you are rong, it will be 1/40(no Pinfu)

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

      Argh. I'm just a Adept 2 in Majsoul. I'm Garbage

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

iSulfox

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

The picture is so cute >.<, i think it's will be a good contest :3

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

I'm a very simple guy, I see an anime girl, I upvote """D

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

Japanese Mahjong game-based round? I tried to get 48000pts on this round!

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

    Majsoul admits multiple yakumann :D So we can strive to 288000 in total!

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

      大四喜 + 字一色 + 四暗刻単騎 + 天和(or 四槓子) isn't it? (BTW,I like 国士無双(13門)!)

      (Sorry for using kanji)

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

        Yup. In Majsoul`s Old Yaku Room,you can get 7-yakumann. Because Three years on stone(?

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

          It's called 八連荘 in Japan, achieving 8 straight 和了(done one's hand)

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

            Not this.

            There is no Eight Qin in majsoul :D

            I meant 石上三年， which is double riichi with haidi

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

              Oh, I don't know the hand,thanks!(I haven't heard that ever)

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

                BTW Its too hard to get that. Even harder than Eight Qin.

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

I like these sweet animes with the problems.

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

[deleted]

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

I'm a simple man: I see anime — I skip round

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

I hope it will be a great contest as one of the problem setter Sulfox is a good problem setter. Looking forward to it. CP in quarantine is fun and I am glad that codeforces is good number of contests.

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

what was the last contest by EternalAlexander??

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

    Oh I didn't make contests on codeforces before but on some Chinese cp platforms.

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

As a loyal mahjong player (振り込み automaton), I'm really looking forward to this round.

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

    Can Japanese play Japanese Mahjong conveniently?

    As a Chinese, If I want to play it,its hard to finding a place which have Japanese Mahjong

    Too sad.

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

I've been curious about where Sooke is these time.

Then I see this!Wow!I really want to take part in this contest!

But I'm not sure if I have enough time.That doesn't matter,lets % Sulfox !

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

I love how EternalAlexander is from Wuhan, China and has a bat as his pic

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

    That's Azazel, not a bat!

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

    That's not a bat!

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

      Thanks, I didn't quite catch it when 3 others replied the same thing

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

      From perspective of healthy white heterosexual cisgender patriotic male who doesn't play stupid anime games it looks like a bat.

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

    This is not a bat

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

    That's not a bat!

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

    Jesus I'm sorry I don't recognize Azazel . You guys make me feel like a criminal for not knowing him

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

      I'm sorry that I say it again,because I don't like bat especially at this time.Please forgive me for being impolite

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

        I mean come on, I wasn't being rude. I just thought that was a bat and pointed it out.

        If my comment did seem rude to anyone, I'm sorry

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

          .

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

            Who is Azazel? /yiw

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

              A playable character (extreme attack power and agility, but have weak hit points) from the video game series The Binding of Isaac

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

I hope this will be a good contest

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

Hope everyone will get a YAKUMAN in this round!

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

[deleted]

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

I am very interested for the problems made by Sulfox.I hope pretests should be strong to avoid hackforces.

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

    Why you hate CF??

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

      His id name is(i_hate_cf) ..so i asked that..but why others are down voting :'(

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

an announcement without almost copy and paste part......is it even possible to learn this power?

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

awww, so cute that it'll be 'bout Mahjong Soul characters :3

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

Have there(in codeforces) more problem about interactive problem without this ( https://mirror.codeforces.com/gym/101021/problem/1 ) ??? ..If have..please suggest...I am so poor in interactive problem so need to practice..Thanks in advance. Sorry for my poor english.

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

    You may try it on other platforms also... simply search interactive problems on google and you will get lot of problems to practice.

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

    You can go to problemset and use interactive tag to find them.

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

Interactive problems are so boring.. change my mind

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

I hope everyone will enjoy this!:)Thanks!

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

Yet Another Chinese Round?

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

Yostar round pog Can't wait for Arknights round

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

I hope I am able to help as many as characters as I can. Sulfox hoping for good and interesting problems. And Thanks for providing Yet Another Chinese Round.

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

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

    When I load this page, I find this interesting pic flashing but soon I can not see it. After some search I find it again from hidden comment. Why this get so many down vote?

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

Who would like to play Majsoul before this round?

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

I was graduated from WFLS in 2018 and ... so glad to see awesome OIer from WFLS ...

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

Why is this contest longer than the usual ones?

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

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

We will upsolve the Div.2 round live on Youtube after the contest is over: https://youtu.be/FgrB_bvZJ_A

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

Contest... End! A FST! B Hacked! -500 rating points! Become Newbie!

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

Is it not a remarkable coincidence that our question makers are from Wuhan, China?

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

I have registered for the contest, if i do not participate in it. Will my ratings get affected?

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

    no, but be responsibility. avoid register contests that u won't participate

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

    I don't know, but I think you'd better not try it. If you have registered in a contest, you can cancel your registeration here, and click the red button after your name.

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

    If you have no submissions, then no.

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

    If you dont submit, your ratings wont be affected. You may even read the question and not submit, you will receive no rating changes.

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

Hello HNV.

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

will this round contian a problem like 'give you a set of 14 Mahjong cards,output whether you can ron' XD

if so,that will be really interesting XD

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

    You can't ron because you can only tsumo with 14 mahjong cards on your hand. so output 'no'.

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

Waiting for a Mahjong problem :)

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

    dude i literally thought there is gonna be a mahjong problem and went to wikipedia to read about it

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

I am a fan of Sooke！

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

Thanks for the site :D, quite complicated game, hope statements are not complicated as that.

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

great Sook orz

There will be a hackforces whenever one of the problems maker is Sook.

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

A nice fact about Sulfox, he has only one blog and couple of comments, his comments are upvoted about 30-50 in average, and his only blog is upvoted 1000 times, also his contributors are more than 120, and its truly too much for one blog and 5 comments.

So what does that mean?, it actually means people loves him and he is a good problemsetter(probable).

Also hope everyone will learn something from this contest and enjoy it(iam not hoping high rate for everyone as it's impossible :])

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

"There will be a sticker in each problem statement except 1F. If you are not interested in the story of the characters, you can skip the sentences above the stickers."

Not all heroes wear capes.

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

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

Another day in Div1.

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

My solution to C gives 9 in 3rd test case on my PC and gfg IDE but giving 7 when submitting on Codeforces

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

I just downvoted your contest.

FAQ What does this mean? The amount of contribution (points) on your comment and codeforces account has decreased by one.

Why did you do this? There are several reasons I may deem a comment to be unworthy of positive contribution. These include, but are not limited to:

Rudeness towards me,

Making bad contest,

Being a weeb,

Sarcasm not correctly flagged with italic font.

Am I banned from the Codeforces? No — not yet. But you should refrain from making contests like this in the future. Otherwise I will be forced to issue an additional downvote, which may put your commenting and posting privileges in jeopardy.

I don't believe my comment deserved a downvote. Can you un-downvote it? Sure, mistakes happen. But only in exceedingly rare circumstances will I undo a downvote. If you would like to issue an appeal, shoot me a private message explaining what I got wrong. I tend to respond to Codeforces PMs within several minutes. Do note, however, that over 99.9% of downvote appeals are rejected, and yours is likely no exception.

How can I prevent this from happening in the future? Accept the downvote and move on. But learn from this mistake: your behavior will not be tolerated on CodeForces.com. I will continue to issue downvotes until you improve your conduct. Remember: Codeforces is privilege, not a right.

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

    Being a weeb is the worst reason to downvote a contest

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

Everytime I take part in contest with 2.5 hours, I become aimless in the last 0.5 hours, just refreshing the dashboard again and again, watching others solve some problems and my rank get lower and lower :(((

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

Not gonna lie I ignored everything before stickers but couldn't ignore those cool stickers! Thanks for strong pretest in Div2D. Nice round.

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

https://mirror.codeforces.com/contest/1337/submission/76887917

Can anyone help me find out why the last testcase wasn't printed? (locally it does)

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

    Why are you make complicated ? just print b , c , c .All done.

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

    I haven't read your full solution, but I can see you are using pow, which is a floating point function, subject to floating point precision errors (especially since you are then checking equality of two floating point numbers with ==).

    Always avoid using floating point numbers unless absolutely necessary.

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

      So what is the recommended method for checking say a number is equal to a^k.

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

        Compute $$$a^k$$$ (without using the pow function) and check if they are equal :)

        For powers of 2 in particular (as in the example above), you can compute $$$2^k$$$ by noting that its binary representation is 1 followed by $$$k$$$ zeroes. As such, you can compute it by simply 1 << k.

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

How to solve Div 2 C and D?

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

    Div 2 C: **** Considering that all paths end at the root(node 1) you may want to put the other end of the path as far as possible from the root. Therefore, starting with the highest depth node of the tree, place the nodes to get the highest possible answer using the following equation:

    answer[node] = depth[node] - sizeofsubtree[node].

    The size-of-subtree part is because adding an industrial city in the node will decrease the number of tourism cities of all its children. Using a priority queue with a key of the equation above, choose the highest k.

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

      During the contest, I wrote the following algorithm.

      1. Create a max priority queue of leaf node vertices as keys and value as dist[v] — size_subtree[v](distance of v from root and size of subtree rooted at v).

      2. while k > 0, pop from v(we push v to final answer) max heap and push v's parent to max heap(again with same values as dist[p] — size_subtree[p]).

      This gave me wrong answer on pretest 6. However, when I just created a vector of these vertices and sorted it with key dist[v] — subtree[v], it got accepted. Here is my submission for priority queue method https://mirror.codeforces.com/contest/1337/submission/76925284

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

        Your code can visit a single node multiple times, mark the node as visited when pushing it in the priority queue.

        Edit: forgot to mention that you should just add the depth[node] — subtree[node] to the answer with no need for another DFS which I believe isn't working properly..

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

          I agree the other dfs code is redundant but it is logically sound. I didn't realise that my code might have a node being visited mutliple times if it has multiple children. Thanks for your help!

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

    for D, you can sort and use binary search to find the best tuple of three numbers.

    my submission

    I could not solve C :(

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

      same here!

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

      That's ternary search not binary search.

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

        actually it's binary search only, just check r->b, r->g or r->b, b->g choose min one , and repeat it for each one as 1st element (b, r, g) and (g, r, b) and that's enough.

        my sol — 76867720

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

          I'm referring to codersanjeev solution. It's just modified ternary search to compress the two mid points so that they are adjacent. That doesn't make it magically "binary search".

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

    Div 2C : Here's what I did — Perform simple dfs to find the depth of each node(d[i]) and to find the number of nodes lying below each node(n[i]). Now, choose k nodes with largest value of d[i] — n[i] and mark them as industries. Then, simply find the answer with another dfs.

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

    C: compute the size of the subtree of each vertex as well as its depth (distance from root). Now for each vertex compute depth[i] - subtree_size[i] + 1. Sort the values in non-increasing order. The sum of the first k values is the answer.

    Proof: notice that when you add a vertex, you gain its depth, but lose 1 from each vertex in its subtree (apart from the one in question). So, it's optimal to add vertices so that vertex i is only added when all subtree of i except i itself has been added already, and the described order is optimal.

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

      The +1 doesn't matter, because it's constant.

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

        It doesn't matter in terms of which vertices we choose, but it matters when we compute the answer.

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

      Hi, tell me if I sort according to subtree size and take smallest subtree size node first is that correct?

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

        It is level of node minus subtree size.

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

        Hi, if I understood you correctly, it isn't. Consider a tree consisting of two paths: one big and one small. Your algorithm will take the vertices from two paths in turns, but it might be optimal to take several vertices from the longer path first before even starting the second.

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

          Oh so are we subtracting depth[i] because of taking into account the happiness of newly added industry? And subtree_size[i] is acting as loss due to newly added industry?

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

            Yes, depth is what's added, and subtree_size — 1 is the combined loss.

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

      https://mirror.codeforces.com/contest/1337/submission/76866312

      My code failed on test 25 and I am not understanding what can be the issue.

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

      Nice solution. Short and easy.

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

      Thank you very much for the proof! I finally understood it.

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

    Refer here

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

    For D, I had iterated over red and select green by using lower_bound over red and then select blue with lower_bound of (r+g)/2. I make all combinations possible.

    here is link to code.

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

      i also want to solve in your solving way..but in the middle feel that code will be big.then stop to write..

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

        I was not able to submit for C question because of this. When I am about to submit solution, contest was just over.

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

        If you make the code modular, its much easier to read / write the code. [submission:76880283]

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

    Div2 C This could be helpful i guess See Here

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

So I think 1337C - Linova and Kingdom is one of the nice problems. We need to find where to start the pathes in a way that the number of unused vertices on the paths is maximized.

It is obvious that we should choose the cities most far away from the root. But after these are used, which ones continue? It turns out that the number of happiness a city contributes is equal to the level of that city minus the number of children of that city. This is because we add children before the parents, so if we choose a city with children, that envoy will increase happines by the level of the city, but all envoys from child cities will get one happiness less.

To implement we do a DFS collecting the levels and number of children of all cities, and sort that list of numbers, then building the sum of the $$$k$$$ biggest ones.

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

    but I got tle on pretest 7 I implemented the exact same solution!

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

    I came up with this idea too, and as i thought i implemented it correctly, but my solution failed test #7, can you help me to find the problem in the code? 76890614

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

      It seems you are counting the direct children only, but you should count all nodes in the subtree, ie, children of children, too.

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

    I implemented this solution i get wrong answer on test 9

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

    I got 5 wrong answers in this problem, all because i used set instead of vector, also it took about 10-15 minutes from me to try changing set to vector, in Div. 1 contests its very important if you lose 50 points and i actually lost 200 points for truly no reason :(, problems were very nice but sadly i got too many wrong answers in the contest.

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

    number of happiness a city contributes is equal to the level of that city minus the number of children of that city.. Shouldn't it be muliplied instead of minus or did i miss something?

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

      The children (and grandchildren, recursive) get choosen before any parent. So, at the time a parent is choosen it contributes its pathlen to root, and makes the contribution of all children (and grandchildren, recursive) each one one less.

      One less because the parent is in the path of each child.

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

what was pretest 5 in C I thought for 2 hours but couldnt get it!

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

Great Round! Solved A and B pretty quickly. Started doing D and ended up wasting an hour. I thought it was pretty easy to do D, and I believe it is, but I didn't get the right idea going. Managed to solve C in the last 30 mins (PS: this is the first graph question I've solved in a contest). Cheers! Looking forward to participating in more contests by Sooke and the other problemsetters.

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

Pretest 5 of C?

I was selecting cities based on greater depth and if the depth is the same, I choose the one which has fewer cities in its subtree. Is this approach wrong? Submission

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

    I think n=k

    Oh my bad sorry

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

      actually, k<n is a condition of the problem, read statements carefully

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

      I was getting pretest 5 wrong when I was applying only DFS to get all the depth of each nodes and getting the maximum K values, which was a wrong approach. Don't know about you though.

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

        Me too. You can have a look at my pretest AC solution. I used DFS too at start and failed pretest 5. Then implemented a BFS solution. I think you can solve it with DFS, just that I couldn't think of how I'd implement it number of leaf nodes is lesser than K.

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

          Yes, I did it with DFS only. The thing was I was just using depth of the node instead of depth — number of children in subtree

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

          I dont understand your approach :<

          Can you hint me ?

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

            Hey! Sorry for the late reply. After dinner, I wasn't in the mood to type and explain my solution and I slept for a few hours. Here's my explanation: (note that this is similar to most solutions shared using DFS. I just thought BFS approach would be a lot cleaner compared to my DFS solution which failed pretest 5, well because I didn't accomodate for all cases and implemented it wrongly).

            Firstly, this is what each important variable means.

            $$$G$$$: The adjacency list. Takes $$$2*(N-1)$$$ memory.

            $$$L$$$: Stores which nodes are present at some depth CurDepth when built. Takes $$$N$$$ memory.

            $$$D$$$: Stores the depth of each node. Takes $$$N$$$ memory.

            $$$C$$$: Stores the number of children for every node when processing the nodes. Later, I subtract the depth $$$D [i]$$$ of the i'th node from each $$$C [i]$$$. Takes $$$N$$$ memory.

            $$$V$$$: Stores if a node has been visited or not in bfs. Takes $$$N$$$ bits of memory.

            Now, the relevant part of the explanation. Once I have the tree built, I process the nodes of the tree layer by layer and store the depth of each node starting from 0 (or 1, if you like 1-based indexing more). This is simple implementation with BFS and saves you from recursion of DFS. After finding the depth of all nodes, I also happen to know the max depth (which is what CurDepth holds after processing). While processing, I also store all nodes in $$$L$$$ that belong to the same depth level. Then, I iterate over all depths starting from the maximum depth using $$$i$$$ as the loop variable, and for each node $$$j$$$ at depth $$$i$$$, which is what $$$L$$$ tracks, I iterate thorugh all its neighbours $$$k$$$ and check which ones are it children. Basically, the three nested loops you see are finding the number of children of each node. Finding the number of children doesn't suffice because there might be a case when the number of leaves are lesser than K. So, the optimal strategy of picking nodes for industries is to greedily choose those nodes that are the deepest as well as have the least number of children. Or in other words, choose tourism cities to be those that have the highest number of children and have the least depth. This is why there's another loop subtracting the depth from number of children of each node. You need to remember to sort this data for having all best cities ending up towards the end (or beginning, doesn't matter as long as you know what you need to do). Once, all of this is done, you can calculate the answer by summing up the $$$NumberOfChildren - Depth$$$ for the best $$$N-K$$$ nodes.

            I'm not sure about the time complexity but I think it is $$$O ((N^2)*MaxDepth)$$$, which I thought would be hackable or will fail Systests, but it passed to my surprise. I might even be wrong about the time complexity, don't really know because I'm new to this stuff.

            Good luck for future contests!

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

              another way getting depth

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

    Yes it is wrong, you should calculate $$$x = depth - subtree$$$ and sort vertices by x and greedily choose the first $$$k$$$ vertices with maximum $$$x$$$ and increase $$$ans$$$ by $$$x$$$.

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

    12 6

    1 2

    1 3

    1 4

    1 5

    1 6

    2 7

    3 8

    4 9

    7 10

    10 11

    8 12

    ans should be 13

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

    This will fail .

    First let`s establish a relation

    Consider a city X with depth D+1 and sub-tree size ( excluding itself ) S (containing all industries ).

    Now if we choose to place industry at this city X then the number of industries will be increased hence S = S + 1 and the potential tourism cities on path from X to 1 will be now D .

    So total answer for this case = D * ( S + 1 )

    Now if we choose to place tourism at this city X then the number of industries will be same and the potential tourism cities on path from X to 1 will be now D + 1 and subtree size wont increase.

    So total answer for this case = ( D+ 1 ) * S

    Now to decide if we should place industry at city X we should have a profit thus first case should yield higher value than second .

    So profit = D * ( S + 1 ) — ( D + 1 ) * S

    profit = D — S

    This is the profit we obtain if we decide to place industry at city X

    Now to we have to maximize the total profit so we have to choose cities with highest profit , thus we can calculate D and S for every city and sort them according to D — S


    Now coming at your logic :

    Consider 2 cities A , B .

    Depth(A) = 10

    Subtree_size(A) = 10

    Profit(A) = 0


    Depth(B) = 9

    Subtree_size(B) = 8

    Profit(B) = 1

    Ideally we should choose the city B as it has highest profit but your algorithm will choose A.

    Hope this helps.

    Now choosing city A will imply that the

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

F seems hard for div 2. Nobody in div.2 solved it :))

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

    I found a way to find all a_i>=2 in the beginning, but didn't know how to use the straight count to figure out if a_i = 0 or a_i = 1

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

      Hopefully correct, but I found that for given index u < n,

      if a[u - 2] > 0, a[u - 1] > 0 , then if you increase a[u] by 1, the number of increment for consecutive tile is x = a[u - 2] * a[u - 1] + a[u - 1] * a[u + 1] + a[u + 1] * a[u + 2], which is a[u - 2] * a[u - 1] iff a[u + 1] = 0, then you can judge between 0 and 1 somehow

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

    I think it's just cause there were a bunch of problems, so there wasn't enough time to finish E. I don't think it was actually that hard, in div1 E just looked like a really good way to get points so maybe that's why there aren't that many solves. I finished it about a minute after the contest ended (maybe) but it took a while to think of a good strategy. Like others have mentioned, if you query each from 1 to n you can determine the exact value by checking the difference of the triplet counts, except you can't distinguish 0 and 1.

    To solve this, query the first thing twice, then query from 2 to n-1. Since you query 1 twice, you can then figure out it's true value. Suppose that when you query the ith stone, you know the number of stones in i-1 and i-2th position. Call the number of stones in the i-2,i-1,i,i+1,i+2 position a,b,c,d,e respectively, for the straight count we have c(ab+bd+de). If we just look at the difference before and after adding the stone, this is ab+ d(b+e). Since we know b and a, and b>0 (since we've already queried previous stones at least once), we can determine if d=0. Continuing this we can get all the stones up till the last. For the last query (on the second to last stone), e=0 so we can easily determine the number of stones in that pile.

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

    It seems hard for div.1, too. Only few of them solved the problem.

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

Is Div1 E1 just finding a basis and then just going through all linear combinations of the basis (or, if basis is too big, go through the complement and subtract these)?

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

    That certainly works, I also found this solution. Too bad it took too long so I didn't have time to write it (rip LGM ;_;)

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

      Yeah I also did try to write something in the last few minutes but WA#4 ...

      Do you know if this approach can be extended somehow for E2 ?

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

        I didn't realise that we can do the thing with the complement so I only have E1.

        My approach for E1 is meet in the middle with FWHT which works in $$$O(n*m + m*(\frac{m}{2})*2^\frac{m}{2})$$$ and if we use the complement idea this can be easily extended to E2.

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

          How do you use meet-in-the-middle? I did spend some time thinking about this (+FWHT) but in the end, I couldn't really bring these two together.

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

            So first we build the basis in $$$O(n*m)$$$ and after that we split the bits into two groups — the first $$$m-h$$$ and the last $$$h$$$.

            Well we will simply do brute force on the first $$$m-h$$$ bits and this way we will generate some pairs of a fixed number $$$k$$$ of set bits that will be in the range $$$[2^{h}, 2^m)$$$ and also some number $$$x < 2^h$$$.

            Similarly we do brute force on the lower $$$h$$$ bits and generate some numbers which are again less than $$$2^h$$$. Clearly this will be one of the polynomials for which we will do FWHT.

            So here comes the FWHT — we will generate another $$$m$$$ different polynomials for the different $$$k$$$ values mentioned above. Now we simply convolute these newly generated polynomials with the on for the lower $$$h$$$ bits and the final popcount will be $$$k + popcnt(x)$$$, where $$$x$$$ is the index in the convolution.

            If we choose $$$h=m/2$$$ we will get the above-mentioned complexity but smth like $$$h=16$$$ was a better choice for E1, as the heavy part of the solution was the convolution after the brute force.

            To extend this, we simply use that idea with the complement, but the details seem to be quite annoying.

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

    I don't really get it. What exactly is a complement of a basis?

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

      Ehm you are probably right, it is not the exact term. I meant a basis of the complement of a vector subspace.

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

        Ok, yeah. But why can it be smaller than the basis itself? Like I think that in the first example both basis and basis of a complement have size 3, right?

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

          The thing is, we can handle the two cases differently. If basis itself is at most 20 numbers, then we can almost brute-force.

          If the basis is larger than 20 numbers, since m is at most 35 we know that the complement is at most 15 numbers. We can now "brute-force" on that.

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

            Yes, I get what to do if the size of basis is small (including the subtraction thing for complement).

            I think I don't understand what a basis of a complement is. So like we want something that can represent all the values original basis can't?

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

              Actually, the more I think about it, the more unsure I am how I intended it all to work together, so my idea is probably wrong (at least the complement part), because a vector space complement is not the set complement (and we want the set complement if we're to subtract, maybe?)

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

    Actually it is a cool idea about the complement of the basis. However, I don't know how to find the complement of basis.

    During the contest, I created an easier idea. Let's just honestly find all numbers we can generate by basis. It will cost $$$2^m$$$. However, let's use some DP here. What we can do.

    Iterate over first $$$i$$$-bit, and use or not use the vector on the $$$i$$$-th position in Gauss. What we know, that after this all bits on position 1-$$$i$$$ will not change. So we can just store the number of 1s. And for the rest, we need to store all possible masks. Dp [i][cnt][mask] it is easy to show that we can solve it in O($$$ m ^ 2 * 2^{m/2})$$$. If I am not mistaken it will even O($$$ m * 2^{m/2})$$$ However it not passed E2, probably because of big constant. I used hashmap.

    76888381

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

      Can you explain please what is the complement of the basis?

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

      After reading your comment, I thought of a slightly different idea.

      Generate all the masks using the first $$$m / 2$$$ vectors, and then do the dp using the other ones, with the least significant $$$m / 2$$$ bits of each mask. That way, the dp will not need hashmaps, and the total complexity will be $$$O(m^2 * 2^{m/2})$$$.

      77216975

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

How to solve div2C? It seemed really simple, but I missed the observation and messed up bigtime. Silly me.

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

How to solve problem C? I was thinking to calculate level and no of the child below it for every node and then placing the developer's city in the tree from the bottom and also taking consider no of the child below it and iterating it in increasing order of children.

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

    When you make a city an industry, all of the cities inside its subtree change, not just its children. You need to sort your array by depth-subtree size essentially and iterate over that.

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

I have made 3 submissions of problem D, and all of them passed the pretests. Can anybody tell me why am I getting penalty of +2 on D?

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

For D, if x and z are fixed, then y = (x+z)/2 is optimal. WLOG let x<=y<=z. You can use 3 pointers after sorting the 3 arrays to go through them and find values of x,y,z, where |y-(x+z)/2| is minimal and z is the closest integer greater than x. But there are 6 possible permutations for the order of x,y,z. Simply iterate through all 6 possible array combinations (r,g,b, r,b,g...,g,b,r) and take the minimum of all of these.

I don't know if this works though, I spent the last 20 minutes coding it up and didn't have time to finish because it wasn't working with longs (probably due to me writing integer instead of long somewhere), but it worked for all the other sample test cases.

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

    I did the same thing and got Accepted.

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

    Same here, feels bad :(

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

    It can be proved using calculus by finding the zero of a derivative. Note that the derivative at 0 is when you have a slope of 0 (i.e. horizontal line) and this is where the minimum (or maximum but we know maximum doesn't exist) occurs. When you fix two numbers x and z (but can also work for any two pair), the resulting function is y^2 - (x +z)y + C. where C is every term that becomes constant when you fix x and z. The derivative of this function is 2y - (x + z), not that x+z is constant. Now, finding zero of function means doing this: 2y - (x + z) = 0 -> y = (x + z) / 2. So y must be the minimum.Because we are not working in the set of real numbers, we probably need to find the two closest integers (from left and right) if (x + z) / 2 doesn't exist.

    But I think it can also be solved using two nested ternary search if you don't know this.

    Code: 76902407

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

      I think calculus is a bit overkill for this. If you know about quadratics, you will known that the tip of the parabola $$$ax^2 + bx + c$$$ is $$$(\frac{-b}{2a}, \frac{-\Delta}{4a})$$$, (where $$$\Delta^2 = b^2 + 4ac$$$, of course).

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

        Maybe... I guess it depends on what you are familiar with. 'Cause personally I forgot about the quadratic minimum derivation.

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

Video Editorial for 1A/2C

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

There should not be such huge gap between the difficulty level of D and E....

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

Had to resubmit in last minute on Div1B because of this case:

1 3 3 3 1 6 9 1 6 9 2 6 10

After WLOGing that the middle number was in array A and was A[i], I was trying to find the first number in C strictly greater than A[i], not greater than equal to A[i]. This passes pretests somehow

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

E is so hard

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

Does anyone know how to solve E? I found an O(m^2n) approach with dp but that's too large given the bounds of 3000...how do you do it in O(mn)?

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

    Let $$$dp[l]$$$ be the number of ways such that you've determined the substring $$$l, l + i-1$$$ of the final string. Say we're adding the ith character of $$$s$$$. It can go at the front or back, and it's easy to check if you're able to do so: if you're adding in the first $$$m$$$ characters, check if it coincides with the character in $$$t$$$, otherwise you just proceed with the dp. Each time just add $$$dp[0]$$$ to $$$ans$$$, and output $$$ans$$$.

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

In my opinion div2 D was easier that C (or maybe I'm just bad at trees).

I was literally migrating between C and E for the last hour of the contest looking at my rank get reduced slowly. On the sidenote, how to solve C?

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

    For C, the value of node n is val[n] = dep[n] - child[n]. The dep[n] represents the depth of node n, which can be solved by BFS(or DFS, thanks to hata_saa). The child[n] represent how many nodes are in the subtree of node n, which can be solve by DFS. After that, sort the vector val and take the maximum k elements of it.

    Sorry for my poor English.

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

    Refer here

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

How to solve D2D/D1B??

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

    I solved it using lower_bound and upper_bound. First sort a,b and c then iterate over a and find the lowerbound and upperbound of a[i] in both b and c. Hence we have b1,b2,c1,c2. Now get the minimum of the given function among the 4 choices. Similarily iterate over b and c too and you'll get the answer

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

MikeMirzayanov Please investigate this possible cheating case : NeiH. Rank 68. 13 hacks to same person.

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

How to solve C ?

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

Why my C gives WA on pretest #9 link -> https://mirror.codeforces.com/contest/1337/submission/76877082 for each node, I created the state (node, level — no. of children it has) then put all these states in an array and sort them according to the second part of the tuple. Please help with which test case I am missing.

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

    What a wired programming language... ;)

    I think your childcount is wrong.

    downside[node] += dfs(child, visited) + 1

    But dfs returns the whole subtree count. So, the $$$+1$$$ is to much.

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

      I guess it is working fine, I used it to find the no. of children present in its subtree and I also print them it is showing me the correct answer For ex — # testcase # 1 node 1 - 6 node 2 - 0 node 3 - 2 node 4 - 1 node 5 - 0 node 6 - 0 node 7 - 0

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

        It would show a wrong number for a node have more grandchildren.

        It is concidence that it seems to work correct for the example.

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

          So, you mean when a node has (no. of grandchildren) > (no. of children) then, in that case, it would give me the wrong answer. Shit I missed this, I have to work upon my implementation skills

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

            I would count that as an of by one error. The $$$+1$$$ is on the wrong line. Summing the children is correct, and adding 1 after the loop would be correct.

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

    dont use int

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

Does Codeforces do -50 for submitting Correct Answer Again??

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

I just downvoted your contest.

FAQ

What does this mean? The amount of contribution on your blog and maybe codeforces account has decreased by one.

Why did you do this? There are several reasons I may deem a blog to be unworthy of positive contribution. These include, but are not limited to:

Rudeness towards me,

Making a bad contest,

Sarcasm not correctly flagged with italic font,

Giving me negative delta.

Am I banned from the Codeforces? No — not yet. But you should refrain from making contests like this in the future. Otherwise I will be forced to issue an additional downvote, which may put your commenting and posting privileges in jeopardy.

I don't believe my comment deserved a downvote. Can you un-downvote it? Sure, mistakes happen. But only in exceedingly rare circumstances will I undo a downvote. If you would like to issue an appeal, shoot me a private message explaining what I got wrong. I tend to respond to Codeforces PMs within several minutes. Do note, however, that over 99.9% of downvote appeals are rejected, and yours is likely no exception.

How can I prevent this from happening in the future? Accept the downvote and move on. But learn from this mistake: your behavior will not be tolerated on CodeForces.com. I will continue to issue downvotes until you improve your conduct. Remember: Codeforces is privilege, not a right.

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

Do you have any idea about what is Div2 C / Div1 A test case 6?

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

    maybe you changed the root to industry city which is not optimal

    it is just a guess

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

    In my first attempt, I create the state of nodes like (node, level, no. of children in subtree) and then store it in array and sort according to level in increasing order and no. of children in decreasing order, So I got WA on test 6 but after changing the state to (node, level-no. of children in subtree) and sort according to second element I got WA answer test #9

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

    Try this test case: 6 2 1 2 1 4 2 3 3 5 5 6 Answer should be 6, not 5

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

      Answer should be 5...

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

      How is it 6? We choose 5->1 (dist=3) and 6->1 (dist=2). So shouldn't the answer be 5?

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

        It was a typing mistake, I corrected it now

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

    Try this

    14 11
1 2
1 3
1 4
2 5
2 6
3 7
3 8
4 9
4 10
5 11
5 12
11 13
13 14

    Your code is giving output 19, it should be 20

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

How can I solve D guys. Can someone show me my mistake in my approach ?

Main part
My code
→ Reply
»
5 years ago, # |
  Vote: I like it +72 Vote: I do not like it

My solution to D:

  1. Find first three values in $$$4$$$ operations: ask 1 2 3 1. The second query on 1 gives $$$a_1$$$. In the query on 2, the number of triples increases by $$$(a_1 + 1) a_3 + a_3 a_4$$$, which is zero IFF $$$a_3$$$ is zero, and if $$$a_3 > 0$$$, we get it from the first query on 3. Then the second query on 1 gives $$$a_2$$$ from the increase in the number of triples, which is $$$(a_2 + 1)(a_3 + 1)$$$.

  2. Find the other values in $$$n-4$$$ operations: by induction we know $$$a_1, \dots, a_{i-1}$$$ and $$$(a_{i-2} + 1) a_{i} + a_{i} a_{i+1}$$$. The second tells us if $$$a_i = 0$$$. If $$$i = n$$$, then it is just $$$(a_{i-2} + 1) a_{i}$$$ and we get $$$a_i$$$, otherwise we ask on i to get $$$a_i$$$ and $$$(a_{i-2} + 1) (a_{i-1} + 1) + (a_{i-1} + 1) a_{i+1} + a_{i+1} a_{i+2}$$$, from which we subtract the first term, which we already know.

Code: 76874617

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

There is a guy (NeiH), who wrote the contest from two accounts in this room and he made 13 successful hacks by hacking his own solutions from another account(HIE) using code like this:

if (a==47&&b==74)
print("WA");

I hope this idiot will get banned.

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

Radewoosh is totally satisfied with problem F.

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

    Yeah, some shite tree, we know.

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

      It wasn't shitty, there are no centroids nor HLD which you are sooooo afraid of ;_;

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

This is suspicious .

MikeMirzayanov What if a person with handle A creates a fake account with handle B, and now A submit wrong solution using the handle B and then hacks it?

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

    This is the reason there are rooms :) You can't view ans hack everyoneone's code. You can only hack code of people in the same room.

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

      I am talking about the case when luckily A and B fall in the same room which is most unlikely but I think today it happened.

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

      Hey, I've locked my solutions but can't hack anyone. Do you have an idea as to why this maybe happening? I'm only able to view the solutions.

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

in problem c, by dfs i calculated the distance of ench node and number of child of each node and then sorted it in order of dist from root node . and ans is equal to for(0 to k) sum of dist[i]-child[i]. but i am getting WA on pretest 5. can someone help. here is my codehttps://mirror.codeforces.com/contest/1337/submission/76891649

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

    Sorting on distance is not always correct: ind-capital(tur)-tur-tur-ind*100 is better than tur-capital(tur)-tur-ind-ind*100.

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

For C, here are my Observations and Solution:

1) The objective is to label each city in one of two categories: a tourism city (i.e. it contributes towards the total score but is not a starting point), or as an industrial city (i.e. it is a starting point and doesn't contribute towards the total score). From an implementation standpoint, the solution is to find the sum of the k longest paths from any node ("industrial city") to the root node (the "capital city" which is numbered 1) while visiting as many interim nodes ("tourism city") as possible.

2) We may be tempted to go for greedy by taking all the leaf nodes first, but that would be incorrect. If the root node has one path that's 10 deep, and another that's just 1 deep and k = 5, then you have to take the 5 deepest nodes from the path that's 10 deep, and ignore the leaf node altogether. However, for the same path, you would always take a child node before you consider the parent node.

3) The complexity gets introduced when you've already taken a leaf node but also need to take its parent node. How can we account for that? Observe that when you add any parent, you could simply deduct 1 for each child it has (since that city is no longer a "tourism" city for each of the child nodes, and is instead an "industrial" city). So if you have to take a parent node, then its contribution is: (distance to root node) — (# of children)

4) So at each node, you need to know two things: the distance from root, and the number of children it has. In terms of the implementation, run a dfs that increments depth by 1 for each child node, and returns the number of children at each stage back to the parent node.

5) Store the (distance — # of children) value for each node in a vector (could also use a priority queue, but there's no need, really)

6) Sort in reverse order. Sum up the first k values and that's it.

Reference Implementation

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

For Div2 C, I tried the following and was not able to solve it.

  1. Tried the greedy approach of "is choosing K nearest nodes from node 1 as tourism cities good" -> quickly found a counterexample

  2. Tried the greedy approach of "Maintain a set S of current tourism cities, initially just city1. is selecting a new node not in S but reachable from S with the highest subtree size good" -> this had a counterexample I found only after an incorrect submission.

  3. Noticed that approach #2 could be wrong because each time I select node N with its subtree size K, a gain is K — 1 (subtree — itself) — (any number of already tourism cities along its path to node 1). When I implemented this greedy approach, the solution seems to work but TLEs.

This is where I am stuck. Where did I go wrong?

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

    9 2 1 2 1 3 1 4 4 5 5 6 6 7 7 8 8 9 in this example, is your code going right?

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

      Is the answer 10?

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

        Yes

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

          Thanks for the counter example. I was more stuck conceptually than implementation wise. I have now figured out. My O(N^2) TLE solution can be improved by sorting descending according to "subtree_size(node) — 1 — length_from_node_1(node)". I know this is identical to the greedy approach because

          1. any optimal solution must include node1 and the tourism cities must be connected.

          2. the sorting criteria makes it s.t. a child is never selected as a tourism city before its parent has already been selected

          3. knowing 2 is true, "length_from_node_1(node)" is identical to "(any number of already tourism cities along its path to node 1)"

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

I literally used dynamic programming on Div2B :)

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

    I wasted 10 minutes for thinking and coding it with DP then suddenly I realize so many ACs on 2nd, so I just code the kinda brute force and it passed the pretests

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

      Can you explain your DP approach?

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

        simple recursion with memoization : from n we can go to 2 states wither (n//2) + 10 or (n-10) And memorize them but as I didn't submit that so I can't say it is perfectly correct or not.

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

    When it's a basic math and you're trying to solve by DP:

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

    I saw Div 2B and started to think of some optimal approaches and trying to prove them, when I saw that WTF there are 5k submissions for it and I just coded some random garbage and it passed systests.

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

What is wrong with my solution to Div2C 76863371?

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

    sorting comparison: depth[u] - sz[u] > depth[v] - sz[v].

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

      Make sense, although i'll be glad if you can provide some counter example for this implementation, cannot think of any?

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

        Sure!
        7 4
        1 2
        1 3
        3 4
        4 5
        4 6
        4 7
        Yours -> 8
        Correct -> 10
        To be specific, your solution picks [5, 6, 7, 4] while the correct solution picks [5, 6, 7, 2].

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

          Got it, that was really dump, thanks again!

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

            Your welcome

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

              My code gives correct answer for above test case and all test-cases mentioned in this blog. Still I got WA on pretest 5.

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

          i was thinking of a greedy approach of choosing tourism cities by sorting nodes subtree size can u please tell me why this wouldnt work

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

            This will work, but it will need recalculation after every insertion. That is why people choose (subtrees_size — node_height) as sorting value — it automatically decreases the final value.

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

        The burden of proof is always on the person who brings a claim in a dispute.

        As a general rule of thumb, try to prove that your solution is correct instead of blindly looking for cases on which it is not. The reason why you will fail the proof will then lead you to counterexamples, if you really need them.

        This will generally be more instructive than if someone simply feeds you the counter-example :)

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

          In some cases blindly looking for counterexamples isn't unreasonable idea. You may stress test the solution and figure out what's wrong with your logic by looking at counterexample that breaks it.

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

    Look`s like you are grabbing vertices in bfs-style — sorted by depth. That is not always correct: ind-capital(tur)-tur-tur-ind*100 is better than tur-capital(tur)-tur-ind-ind*100.

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

So, solution to E1 works in $$$O(2^\frac{m}{2} m)$$$ or even in $$$O(2^\frac{m}{2} \sqrt{m})$$$. But that looks like it could work for E2 or at least be very close? Is E2 just optimizing some small polynomial factors in m somehow making it $$$O(2^\frac{m}{2})$$$?

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

    There seems to be two ideas in problem E: meet-in-the-middle and using the complement of the basis when the basis is too big. Any of them should give a solution that works in $$$O(2^{m/2})$$$, and combining them should give a solution in $$$O(2^{m/4})$$$, or maybe $$$O(2^{m/3})$$$.

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

      can you explain the meet in the middle idea?

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

        I now notice that I got the complexities wrong.

        Compute a basis in upper triangular form. Split the basis into two subsets A and B, where A contains vectors with only low bits (say that they can only use the lower k bits, we will choose k later) and B contains the other vectors. The size of A is at most k, and the size of B (I write it $$$\sharp B$$$) is at most $$$m-k$$$. Compute all linear combinations for A and B. In the vectors generated by B, only the lower k bits and the number of higher bits matters. Thus we can compress things a bit, and compute the final answer in $$$O(2^{2k}m)$$$.

        The total complexity is $$$O(2^{\sharp B} + 2^{2k}m)$$$, so if we pick $$$k = m/3$$$, we then have $$$\sharp B < 2m/3$$$ and the solution works in $$$O(2^{2m/3} m)$$$.

        If we combine this with the idea of replacing a basis with its complement we have $$$\sharp B < \frac{m-k}{2}$$$. We can then pick $$$k = m/5$$$ and we get a solution that works in $$$O(2^{2m/5} m)$$$.

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

          How to compute the answer after replacing a basis with its complement?

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

      I described the third idea with DP for E1 in comment above. The proof of complexity is very similar to meet-in-the-middle.

      link

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

      Can someone please explain how to find xor basis complement?

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

How to solve Div-1 C??

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

I saw several uers are cheating on div2 contest , they used the trumpet to score more points ，They set special judgment conditions in the trumpet's program, and then hack it to get more score.

His id :NeiH

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

I think the pretests of Div2 D are weak. My first solution was failing on the input 1 1 2 1 4 3 5 5

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

What is wrong with this solution for Div1B? 76851469

The main idea is for all values of r_i choose the best possible g_j i.e. best of upper and lower bound of values r_i in g. Now choose the best possible value of b_k i.e. best of upper and lower bound of values (r_i + g_j)/2 in b.

Repeat the above exchanging the arrays r,b and g.

Return the min of these possibilities.

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

    I was thinking the same solution, after i implmented only the part for red values but now i'm intrigued why yours don't work?

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

    Can you prove it? No. This is random greedy garbage which is destined to fail. The correct solution is to fix the middle (can be any of the three colors, iterate over all), and for each middle color, select the highest lower bound and lowest upper bound from the remaining two colors, twice.

    So consider all 6 possibilities of $$$x<=y<=z$$$, fixing $$$y$$$, take the closest possible values of $$$x$$$ and $$$z$$$, twice for each fixing of $$$y$$$: since $$$2$$$ colors go into $$$x$$$ and $$$y$$$ in two ways.

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

      Sometimes it comes as a surprise when random greedy garbage turns out being correct solution :)

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

      Why would you need a binary search? Wouldn't 6 linear 3-pointer iterations be "cheaper"?

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

        Yes, and also more difficult to implement. You can make the binary search approach into a function which significantly reduces the code length.

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

    This may not work, however I did something similar. Suppose you fix the smallest of the three, say x. Now find the next greatest elements in the other two arrays, say y and z. Now suppose y > z. The other case can be handled similarly. It is easy to see that it is optimal to choose z (follows from the property of the function). and choose the remaining color closest to (x + z)/2.

    Of course, fixing the middle element is much easier, however I didn't think of it.

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

    What you are doing in the code doesn't match your description of the algorithm. Just in case: lower_bound gives you the first element that is larger or equal, upper_bound gives you the first element that is strictly larger. You don't have any handling for the "the last element that is smaller or equal" part.

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

      I_love_Tanya_Romanova I don't get the error.

      For the case where upper_bound or the lower_bound gives me an index which is greater than the size of the array I just take the largest possible value.

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

        You're saying "let's check the element that is closest to the middle point", and then you are making an assumption that the closest element will always be on the "higher" side.

        See 76904729. Further simplifying it by removing unnecessary code duplication: 76904943.

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

    I got accepted using same approach https://mirror.codeforces.com/contest/1336/submission/76857894. You dont need to take lower bound and upper bound. you need lower bound and lower bound -1.

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

Now i'm reading above stickers. :)

U people from wuhan I pray for you.Stay safe and make good problems for us.

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

The observation of div2-C is so cool.

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

Images are so charming, but why does problem F have no picture?

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

Can anyone please share the idea of div-2 E?

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

Why not allow O(N*30*30) DP as an alternate solution to div2B?

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

    Actually we allowed it to pass. Check my code below.

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

      Not sure why this solution got MLE.

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

        Because you used int instead of bool which takes four time more memory. The array size is ~90 000 000 elements. For bool that's ~90MB, for int that's ~360MB

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

Can anyone tell me how did this submission passed all the testcases for A[submission:76846944]?? https://mirror.codeforces.com/contest/1337/submission/76846944

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

    If I had to guess, I would say modern compilers are smart enough to look at that loop and know they can transform it into a simple subtraction :)

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

      I tried that with 100 1 1 1 1000000000s and it passed. What's more, when I added #pragma GCC optimize(0) at the beginning of it, it got TLE.

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

        Makes sense. That pragma tells the compiler to turn off optimizations.

        If anyone is further curious, here is how Visual Studio 2017 compiles the code, first on Release (optimizations enabled), then on Debug mode (no optimizations). You can see there is a sub in the first case and a loop in the second one.

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

    Time-wise the compiler probably optimises it to $$$O(1)$$$.

    Correctness-wise the output is $$$b, c, min(b+c-1, d)$$$, which satisfies all conditions.

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

    I tried hacking it with with 60 testcases of 1 1 1 1 1000000000 MikeMirzayanov please look into this

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

      Compiler optimizations are part of the game, even if they're very tricky. There's nothing to look into.

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

      Hate to be blunt, but you lost points in hacking because of incorrect hacks. You not understanding how the compiler works is your fault, not Mike's, Codeforce's or anyone else's.

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

    Lol, one needs to have balls of steel to write if (d >= b+c) d = b+c-1; in that way xD

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

Did anybody try simulating the whole process K times using segment tree with lazy prop in div2C?

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

Thank you for the problem C

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

This contest was great and have lots of great and interesting problems to solve i want to thank to codeforces and their team such that they are creating/hosting the amazing contests for us so that we can learn and enjoy in this situation.....THANK YOU CODEFORCES....!

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

Many div2Ds/div1Bs are failing system tests :(

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

Problem A Why would answering "b b c" if b + b >= c and "b c c" if else fail problem 2A?

sorry for bad english.

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

    It should be b+b>c not b+b>=c. For a triangle sum of any 2 sides should be GREATER THAN the third side

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

    if b + b = c and you answer "b b c", then area of the triangle formed is 0.(A straight line would be formed.We need to have non-zero area.)

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

    Deleted.

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

I didn't solve a single problem, the only thing I comprehended well were the chronicles of Mahjong Soul.

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

I managed to pass the systests of Div2D by nested ternary searches https://mirror.codeforces.com/contest/1337/submission/76872794 :D Anyone solved the same way?

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

What is the proof of Brute Force solution of Div2B?

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

    Observe that when X is 20 or lesser, it ends up in a cycle if you do [X/2]+10. So, the least you could get X down to using 'N' is 20. Then, you need to check if the remaining health minus M*10 is positive or not. This is because 'M' will always end up reducing the health.

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

    $$$m=30$$$

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

    I think you taking about the greedy solution not brute force

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

Very nice problems, thank you for the contest!

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

The sticker idea is great! Although I ended up reading those stories otherwise where's the fun.

Also great problem C!

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

    Just wondering why there is no sticker in 1F :)

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

Who else got WA on test #93 on Div2 D? :)

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

    Me too.. Used Ternary Search. Any idea why?

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

      I used ternary search too… I only know that if you do brute-force when $$$n_r, n_g, n_b \le 10$$$ it passes.

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

        Ternary search works if the fonction is convex, but is it here ? I doubt it...

        You use the function : $$$y \rightarrow f(x, y ,z(x,y))$$$ where $$$z(x,y)$$$ = best z possible relatively to x and y ; but this function should variate quite randomly because z is quite random ?

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

          If you have $$$x$$$ and $$$y$$$ fixed, than the only thing that varies in $$$(x-y)^2 + (y-z)^2 + (z-x)^2$$$ is $$$2z^2 - 2z(x+y)$$$, which is of course a unimodal function in $$$z$$$. I have sorted all the arrays, so you can use ternary search.

          In fact, my solution was the following: For each $$$x$$$ in $$$r$$$ I've binary searched the closest ~20 elements to $$$x$$$ in $$$g$$$, and for those $$$x$$$ and $$$y$$$ I've ternary searched $$$z$$$ in $$$b$$$. And I've even did this for every permutation of $$$(r, g, b)$$$ and still got WA on test #93…

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

Lovely problem set, clean and brief descriptions, nice examples (sufficient without giving too much)!

This contest reminds me that I need to catch up on my anime — it's been a while!

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

I remember E from topcoder (with n up to 50). Was the intended solution then the same as today's E1 or E2? Also, can somebody find it?

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

When can we submit solutions again?

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

Solved ABCD in a Div 2 contest for the first time !! :D

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

    Congrats! Been feeling that feeling too. First time ABC in Div2, and first time ABCD in div3 of vovuh day before yesterday.

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

Awesome contest! Thank you for problems and clean descriptions.

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

tourist :( it's a bad day -192 rating https://cf-predictor-frontend.herokuapp.com/roundResults.jsp?contestName=Codeforces+Round+%23635+%28Div.+1%29&contestId=1336&sbm=Get+rating+prediction

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

https://mirror.codeforces.com/contest/1337/submission/76862427

Its failing at pretest 6 any guess why

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

How to solve div1 C?

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

    The key idea is to fix T and change the position character add.For after each operation,String is continuous and added character is rightmost or leftmost position in the String. Considering you can calculate what number you have made operation from the length of string, you can solve with segment DP.

    here is my code.

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

    76901738

    The last character in $$$S$$$ will either be the first or last character in $$$A$$$. If we assume $$$S$$$ and $$$T$$$ are the same length, then that last character in $$$S$$$ has to match either the first or last character in $$$T$$$. We can repeat this process with a DP, maintaining a left and right position in $$$T$$$, and a current position in $$$S$$$. The number of characters we have placed down is the same as the number of times we have moved left and right in $$$T$$$, so we can do the DP in $$$n^2$$$. Now, in the DP, if we are comparing against a position that doesn't exist in $$$T$$$ (i.e. we're too far right), we can put down any character, since we only need $$$T$$$ to be a prefix of $$$A$$$.

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

      Thanks a lot :)

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

      I don't understand how do you get prefixes that appear before the word is complete. dp(0,N-1) will get you # of strings with prefix = T right? but how do you get the ones where the word was not complete, but the prefix was.

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

        You can count those by taking the sum over $$$dp(0, k)$$$, where $$$m-1 \leq k \leq n-1$$$.

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

          Thanks! Do you have the proof or at least some intuition behind why does it work? Just this specific part

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

            If you have some sequence of operations that give you a match, you can always place the remaining characters at the end of $$$A$$$.

            When you choose to place a character at the end, you transition to $$$dp(l, r-1)$$$, where $$$l$$$ and $$$r$$$ are your left and right positions in $$$T$$$. So, by calling $$$dp(0, k)$$$, you're forcing the last $$$n-1-k$$$ characters to be placed at the end. Since the last $$$n-m$$$ characters of $$$T$$$ will match with anything, keeping $$$k$$$ in the range $$$m-1 \leq k \leq n-1$$$ is sufficient to ensure that the forced operations are legal.

            Another way to interpret it is like you're cutting of some suffix of $$$S$$$ (and the associated blank spaces in $$$T$$$). We compute the current position in $$$S$$$ with $$$r-l$$$, so calling the DP with smaller arguments is equivalent to pretending that $$$S$$$ is shorter than it actually is. Thus, the result of the DP call will give you the number of solutions you have using only that prefix of $$$S$$$.

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

Solution for Div2 D

  • The function (a-b)^2 + (b-c)^2 + (c-a)^2 will be least when the gap between a and b and c is minimized. As an example if you had a == b and b == c, then the function would return 0 (and we could actually stop at that point as this can never be less than 0).

  • From the first set of numbers (say the red ones), iterate over each one (say r)

  • Find neighbors of r in the next set (say the green one). A neighbor is a number that’s equal to or just greater than r, and one before, and one after (call them g-1, g, g+1)

  • Find neighbors of r, g-1, g and g+1 in the final set (blue)

  • Compute the function with inputs as r and each number that we just extracted from the green and blue sets {( r, g, b); ( r, g-1, b); ( r, g-1, b-1); etc.}

  • Swap the arrays twice and repeat the process (for eg., the first swap: green takes red’s place, red takes blue’s place and blue takes green’s place)

Reference

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

Thanks for very great mahjong-based Div1D!!
The key of this task is distinguish 0 or other.
It's very interesting to make steps of observation!

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

https://mirror.codeforces.com/contest/1337/submission/76879433

Please, anyone tell me what's wrong with this Ternary Search solution for Div2 D, since it passed 92 case and got WA on case 93.

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

Screencast

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

Div2 — D Approach — Observation — Lets choose three points x, y, z of type red, green and blue respectively. Let the average be avg = (x+y+z)/3. The points are optimal for one another when the point closest to avg in the red set is x, in the green set is y, in the blue set is z. Out of x, y and z lets say the closest to avg is x then we should choose y and z which are closest to x. So the solution is to Iterate over all points in each set, find the closest to the current point in the remaining two sets, calculate (x-y)^2 + (y-z)^2 + (x-z)^2, and get minimum over all. 76888317

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

    you have used bs function I saw many solutions with the same kind of name for that function is that some sort of standard algorithm if so please tell me the name

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

      It stands for binary search. Well he has made complete function but there is no need c++ stl for vectors provides you with upper_bound lower_bound and binary_search options google it. Also it will be best to the learn the main algorithm.

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

Great contest waiting for editorial!

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

I am waiting for Editorial for this round.

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

76889124 Div2 D .I don't know why it can pass. May be o(n).

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

Why is this code giving wrong answer on test1 despite giving correct answer on local IDE 76910973 ?

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

    Perhaps your username sums it up

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it 
    int idx1=upper_bound(all(b),x)-b.begin();
int z1=b[idx1],z2=b[max(0ll,idx1-1)];

    How without checking idx1 to be out of bounds?

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

      $$$x=10$$$
      b[] = {1, 2, 3}
      idx1 will be 3, so calling b[3] is out of bounds.

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

Finally candidate master, barely made it though, but anyway, thanks for the contest :)

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

Div2C test 9 run time error, any ideas?

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

DIV 2C Linova and Kingdom, wrong answer on test 6, any ideas about the mistake? I have optimized for max hapiness by sorting nodes for (depth-no. of children) and then being greedy. 76915755

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

(Why do these contests start late at night?It's fit for Russian users,but not Chinese users!)

I'm sorry for my coment.

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

    Codeforces isn't chinese

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

      But this is a Chinese contest!

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

        Problemsetters being Chinese don't make this a Chinese contest. It's a Div1/2 CodeForces contest, nothing more or nothing less than that.

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

          I mean sooke is a Chinese,I think he(she) was sleeping at that time.

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

            So what? It doesn’t matter.

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

    Yes its bad but what can be the solution? whatever the contest time is, it will be unfriendly time for about $$$\frac{8}{24}$$$ of the world, there is no way to avoid it — if you know then just say it and whole world will be happy.

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

I thought I would not score, but this round is friendly to me. I'm very happy that My rating is higher than before (Maybe Chinese round is easy for me)

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

I can't believe the reason for fst in div1 c/div2 e --basically I was converting string to char array first and then to int and it went out of bound.Converting string directly to int worked

previous input code(out of bound)
new input code(AC)

the line at which cf judge pointed out of bound is -'strcpy(ac,s.c_str());'

Can anyone point out the reason this happens?

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

    C-strings have an extra \0 at the end, so you need to use an array of at least $$$n+1$$$ elements.

    However, I don't know why it passed the pretests. Maybe because of the magic of undefined behaviors :)

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

      increasing size of char array by 1 in previous code AC'ed.Thanks a lot for your help :)

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

So, there's another way to solve the C problem in Div.2.

Constructing a segment-tree and greedily choose the highest-contributing node, in the meantime modifying the contribution on its path to node $$$1$$$ and in its own sub-tree, reducing by one.

but could anyone explain to me why just modifying the path to node &1& could not pass? WA on test 6.

Although with these modifies I have ACed.

Unaccepted accepted

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

Still no editorial . . . :(

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

Could not find the reason for time limit exceeded in DIV 2.Problem D on pretest 5.. my code works o(nlogn) according to me.. can someone identify the issue in this code.. it will be very helpful.. My Code

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

    Never, Never, Never use arrays and vectors and other data structures as function arguments, it will take $$$O(sz)$$$ to send a data structure of size $$$sz$$$ to a function, and it will cause $$$O(sz)$$$ memory. Also referring to this blog, you can use min({a, b, c, . . .}) instead of using min(a, min(b, min(. . .))).

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

      >> Never, Never, Never use arrays and vectors and other data structures as function arguments

      Do you also recommend this when I'm passing a reference e.g. vector <int>& v as argument?

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

        No its fine, but i prefer using global vectors instead of using pointers as arguments.

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

          oh thanks, will keep this in mind the next time..

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

            you could pass the vector by reference, using "vector<ll> &vec" as function argument.

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

how to count the size of subtree using dfs or bfs?referring to DIV 2C

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

Tutorial ?

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

Desperately waiting for the Editorial

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

Codeforces is leaving no moment to provide coding practice to the users in this tough time.

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

76927904

How can this code which gives TLE for test case 7 be optimised to get accepted? Thanks in advance.

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

    Please avoid using arrays, vectors and other data structures as function arguments, it actually take $$$O(sz)$$$ to send a data structure of size $$$sz$$$ to a functions, also $$$O(sz)$$$ memory.

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

    use const reference if you want to pass big structures as function arguments. example:

    int func(deque<char> q)

    it will have to copy the whole deque so replace it with

    int func(const deque<char>& q)

    now it wont have to call copy constructor

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

can anyone help me where i can find graph problems like Codeforces Round #635 div.2D .I know basics of graph/trees but i am unable to solve such problems during contest.thanks in advance.

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

    You mean C right? This is just basic dfs on a tree.

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

      Yes C, sorry for confusion.

      This is just basic dfs on a tree.

      yes i know that,but during the contest my mind gets stuck on it and not able to clearly think about such problems.So ,i figured out that i have to solve many problems of such types in order to solve graph problems during contests.So i want to know where i can find such good graph problems for beginners

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

Hey Sulfox, Can u plz tell me why my solution is giving WA for problem Div2C?76854924

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

When will the editorial come? Sulfox

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

When editorial will be posted ??

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

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

I know it's a little late but I simply can't resist saying that this was one of my favourite contests. I know I didn't perform very well but I loved participating in it. The problem statements were well-crafted. 1337C - Linova and Kingdom was my favourite problem. Like many, I was so close to the correct answer but I couldn't solve it on time, unfortunately. Thanks a lot for the contest. Keep it up! :)

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

If Anyone Needed Too detail explanation of Div2 C Here

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

best round ever for me! very good and interesting tasks. thanks!

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

can someone tell me why am I getting T.L.E on pretest 7 for the Div2 -C problem here's the code https://mirror.codeforces.com/contest/1337/submission/76886978

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

    The std::sort function need a comparison function object (i.e. an object that satisfies the requirements of Compare) which returns ​true if the first argument is ==STRICTLY== less than (i.e. is ordered before) the second. You use <=. That will caused the sort function undefined behavior, maybe dead loop.

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

My solution to E2:

If the rank of spanning space is no more than $$$m/2$$$, it's trivial. Otherwise, the rank of the orthogonal complement is no more than $$$m/2$$$.

Let's recall Fast Walsh-Hadamard Transform:

$$$\hat{f} (T)=\sum_{S} f(S) (-1)^{|S\cap T|}, f(T) = \frac{1}{2^m} \sum_{S} \hat{f} (S) (-1)^{|S \cap T|}$$$

.

Let $$$g(T)$$$ be the answer, and $$$\hat{g}$$$ be the FWHT of the answer. We have

$$$\hat{g}(T) = \prod_{i=1}^n (1+(-1)^{|A_i\cap T|})$$$

, since FWHT of each term is $$$1+(-1)^{|A_i\cap T|}$$$.

So if $$$|A_i \cap T|$$$ is even for all $$$i$$$, $$$\hat{g}(T)=2^n$$$, otherwise $$$\hat{g}(T)=0$$$. That means $$$\hat{g}(T) =2^n$$$ iff $$$T$$$ is in the orthogonal complement of the spanning space of $$$A_i$$$.

$$$ans_k=\frac{1}{2^m} \sum_{|S|=k} g(S)=\frac{1}{2^m} \sum_{|S|=k} \sum_{T} \hat{g}(T) (-1)^{|S \cap T|}=\frac{1}{2^m} \sum_{T} \hat{g}(T) (\sum_{|S|=k}(-1)^{|S \cap T|})$$$

Due to the symmetry, when $k, |T|$ are fixed, $$$\sum_{|S|=k}(-1)^{|S \cap T|}$$$ is a constant. We can use dp or combinatorial approach to compute it. And we can simply enumerate all the vectors $$$T$$$ in the orthogonal complement, and compute $$$cnt_k$$$ where $$$|T|=k$$$.

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

My solution for D, let's choose 3 values such that $$${x}{{<=}y{<=}z}$$$, then if we fix $$${x}$$$ and $$${z}$$$ by differentiation we can prove that the best choice for y will be $$${(x+z)/2}$$$. During the contest I missed the case when such a y doesn't occur what should we do.

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

Is there any easier way to do D. I just kept comparing and comparing with binary search and my implementation is just messy. 76944408

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

    76959885 .. u can see this ..using function.

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

Hope there are more problems related to Majsoul! lol

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

[problem:C] In this problem first i'm trying to add all the happiness values of all the farthest nodes then second farthest and so on untill i have taken <k nodes in last iteration. then all the nodes which are at height h are taken partially to make exact count of k. for this i subtract from ans this value: (sz[i] — 1)*h and add this value: sz[i] * (h -1). can someone tell why it's not working?? code is: [76964908] Just do cout<<ans; (https://mirror.codeforces.com/contest/1337/submission/76964908)

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

    Man, clean this up, please, it's unreadable here — just post your submission link like this. Its a link with numbers like "76969147" on your submit page.

    PS. Please, stop downvoting him. He asked a round-related question.

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

      please check it now...

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

        Do you know that you can see a test case that your solution failed? Have you seen it? Do you understand why its failed?

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

This contest is a big success!

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

I solved two questions in this contest. Why did my rating still go down??

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

Your sticker pro-tip is very nice idea.

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

Thanks for a nice round :D

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

Why this code is giving TLE? Question D(Div 2)

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

problems were nice :D

→ Reply