Sooke's blog

By Sooke, 5 months 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 15.04.2020 17:35 (Московское время). 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 Sooke.

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. cwcszzh
  7. soltanbh
  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

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

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

GL & HF!

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

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

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

I am feel this round will be nice

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

You may have already heard of Mahjong Soul here.

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

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

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

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

Orz EA, Sooke & ustze!

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

Hey,Sooke.

What is the score of each question?

Forgive me for my rusty English,QAQ

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

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

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

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

Hope you like our problems. GL & HF!

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

Is there a typical difficulty on the interactive problem or could it be any? Just curious.

»
5 months ago, # |
Rev. 4   Vote: I like it -43 Vote: I do not like it

I look forward to your contest!

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

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

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

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

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

Chinese Round!

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

Hope Strong Pretests .

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

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

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

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

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

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

what is GL & HF???

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

Hope it will be a great contest!

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

No Mahjong Soul over two weeks. :(

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

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

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

Orz Sooke tql

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

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

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

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

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

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

Wow, another Chinese round!

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

EA txdy!

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

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

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

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

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

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

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

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

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

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

    Only 2000 points is solvable.

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

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

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

Will there be an interactive problem in div 2 also? PS- Exited for the contest

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

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

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

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

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

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

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

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

»
5 months ago, # |
  Vote: I like it +40 Vote: I do not like it
»
5 months 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

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

In this current scenario of lockdown due to corona Codeforces is something which keeps us engaged!!! Thanks from India

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

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

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

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

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

      (Sorry for using kanji)

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

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

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

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

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

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

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

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

I hope it will happen for third time(^_^)!!   )

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

I like these sweet animes with the problems.

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

Hope it will be a great contest!

stO

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

[deleted]

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

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

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

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

what was the last contest by EternalAlexander??

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

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

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

»
5 months 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 % Sooke !

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

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

    That's Azazel, not a bat!

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

    That's not a bat!

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

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

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

    This is not a bat

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

    That's not a bat!

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

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

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

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

          Oh sorry, I know it was a joke and you're not being rude. I was a bit angry called some friends to downvote you, I shouldn't do that, that's my fault.

          But it's my favourite character in my avatar and you know it is somehow offensive to call something a bat especially during this time, even you didn't mean it.

          Sorry again for my improper behaviour.

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

            Who is Azazel? /yiw

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

          • »
            »
            »
            »
            »
            »
            5 months ago, # ^ |
            Rev. 2   Vote: I like it -27 Vote: I do not like it

            wow so y'all mobilize mfs for downvoting exercises smh. y'all trippin

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

I hope this will be a good contest

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

Hope everyone will get a YAKUMAN in this round!

»
5 months ago, # |
Rev. 3   Vote: I like it -10 Vote: I do not like it

[deleted]

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

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

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

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

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

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

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

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

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

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

include

using namespace std;

long long l, r;

long long gcd (long long a, long long b) { return b ? gcd (b , a % b) : a; }

int main() { cin>>l>>r; for (long long a=l;a<r-1;a++) for (long long b=a+1;b<r;b++) for (long long c=b+1;c<=r;c++) if (gcd(a, b) == 1 && gcd (b, c) == 1 && gcd (a, c) != 1) { cout << a << " " << b << " " << c; return 0; } cout<<"-1"; return 0; }

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

Interactive problems are so boring.. change my mind

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

    They are one of the most interesting on CF

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

    Tell me your mind's password then probable i can change it. I mean nothing can change your mind as long as its locked.

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

I hope everyone will enjoy this!:)Thanks!

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

Yet Another Chinese Round?

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

Yostar round pog Can't wait for Arknights round

»
5 months 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. Sooke hoping for good and interesting problems. And Thanks for providing Yet Another Chinese Round.

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

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

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

Who would like to play Majsoul before this round?

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

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

Why is this contest longer than the usual ones?

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

    Well 6 questions and 2.5 hours probably hinting that the difficulty is more than usual.

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

    I guess the last problem must be data structure.

»
5 months ago, # |
Rev. 3   Vote: I like it +58 Vote: I do not like it

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

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

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

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

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

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

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

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

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

    If you have no submissions, then no.

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

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

Hello HNV.

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

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

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

Waiting for a Mahjong problem :)

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

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

I am a fan of Sooke!

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

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

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

A nice fact about Sooke, 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 :])

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

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

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

i registered to this contest Div 1 now i am not able to submit the code can anyone help please

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

Another day in Div1.

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

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

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

    Being a weeb is the worst reason to downvote a contest

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

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

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

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

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

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

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

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

      i see. Thanks, your comment is very helpful. I'll keep this in mind for future competitions.

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

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

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

How to solve Div 2 C and D?

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

    • »
      »
      »
      5 months 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://codeforces.com/contest/1337/submission/76925284

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

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

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

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

      same here!

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

      That's ternary search not binary search.

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

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

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

      Now WA on test 10 in problem D :3

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

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

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

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

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

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

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

        It is level of node minus subtree size.

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

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

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

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

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

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

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

      Nice solution. Short and easy.

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

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

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
  • »
    »
    5 months 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.

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

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

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

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

    Div2 C This could be helpful i guess See Here

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

So I think 1337C - Linova и королевство 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.

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

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

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

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

    I implemented this solution i get wrong answer on test 9

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

      Try changing to long long

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

        Ah yes thanks that was it, so close yet so far ...

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

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

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

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

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

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

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

    I think n=k

    Oh my bad sorry

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

      It is given that k<n

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

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

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

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

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

          I dont understand your approach :<

          Can you hint me ?

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

            Sure, I don't mind. But the thing is it's 23:00 where I live and I haven't had dinner yet. I'll try and be back soon. Until then, if someone does understand my approach, feel free to comment and explain if you'd like.

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

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

              another way getting depth

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

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

      Yeah got my mistake. Thank you :)

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

        What I did is like yours. I find the subtree size of each node then sorted them by depth and if two depths are equal sorted them by subtreee size. . I don't what's wrong in this approach. I totally understand this approach "x=depth−subtree and sort vertices by x and greedily choose the first k vertices with maximum x and increase ans by x."

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

      Hey, I was sorting only on the basis of the subtreesize since the depth of a particular level is the same. Can you please tell me where i am going wrong. https://codeforces.com/contest/1337/submission/76880891

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

        You did the same mistake as mine.

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

          Can you explain, I am going level by level, so for a particular level sorting only on the basis of subtree size won't suffice?

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

            Think about what would happen if the number of leaves is lesser than K.

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

            Consider you are at level 4 and has subtree size of 3 and another node is at level 3 and subtree size of 1.

            It would be optimal to take the node at level-3 rather than at level-4.

            This was the same mistake in my code.

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

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

    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 DS


    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

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

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

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

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

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

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

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

  • »
    »
    5 months 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 ;_;)

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

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

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

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

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

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