FairyWinx's blog

Codeforces Round #926 (Div. 2)
By FairyWinx, 9 months ago, translation, In English

Neko Nya, Кодефорсес =＾● ⋏ ●＾=

I'm happy to invite you to participate in Codeforces Round 926 (Div. 2). It will take place on Feb/15/2024 17:35 (Moscow time) and in it, you will help a boy named Sasha win over a girl's heart. The round will be rated for all participants with a rating strictly less than 2100. You will have 2 hours to solve 6 problems.

Here is a big thank you to everyone involved in the round:

Looking forward to seeing everyone at the contest >~<

UPD: Scoring distribution: 500 — 1000 — 1500 — 2000 — 2500 — 3000

UPD2: Editorial

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

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

As a tester I highly recommend you writing this round!

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

cutie FairyWinx

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

Finally, a catgirl round!

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

As a tester,this round has a clear and concise statement. I highly recommend you to participate :)

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

Score Distribution of the round?? Score -> Updated

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

uwu

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

Kudos to the authors for continuing the trend of attaching their photos!

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

OWO

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

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

scoring distribution???

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

score distribution ?

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

Sasha is a determined young man, and he's not afraid to use his programming skills to win over the girl of his dreams. In this Div. 2, Sasha will have to solve 6 problems in 2 hours. But with the help of the cutest coordinator Artyom123 and the best platform KAN, geranazavr555, MikeMirzayanov, Sasha is sure to succeed. And if he needs any help, he can always count on the legion of testers: A_G, AgafonovArtem, Alexdat2000, Vladithur, wuhudsm, petyb, induk_v_tsiane, sevlll777, mz1, SomethingNew, AVdovin, NewLul, damirsit, and skylak3_3.

Good luck, Sasha! We're all rooting for you!

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

    Thank you, but you'd better help me and solve as many problems from the contest as you can.

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

>.<

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

What about the streak of announces with photo of authors???

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

Hope to become expert in this round.

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

GOOD LUCK

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

Why do I feel like I'm being called for by the announcement? (•‿•)

→ Reply
»
9 months ago, # |
← Rev. 3   Vote: I like it +20 Vote: I do not like it

╱|、
(˚ˎ 。7
|、˜〵
じしˍ,)ノ Good luck to all ≽^•⩊•^≼

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

I don't have a GF in real life, and I also can't use my limited coding skills to help you. So sad......

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

the cat is cute

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

koshka

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

I'll try my best to solve problems to help a boy named Sasha win a girl's heart. ≽^•⩊•^≼

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

kawaii catgirl !!

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

You are cute !!

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

No girls, only hardcore

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Love the theme of this round. Let's goo. Hopefully it is a good one. All the best everyone❤️

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Short round blog !

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope I can solve 3 problems!!!

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

Such a short and clear announcement I hope problems statements be like this too!

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Short statement Blog … nice

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Either way gonna sweat on 14 or 15

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope to become expert in this round!

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

Mid sem from 19 but CF round is the first priority

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

kawaii neko ^-w-^

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

As a tester, i wish good luck to all participants.

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

Sasha, I'll try to help you get her number)

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

But I knew Sasha is a girl's name from AOT .

→ Reply
»
9 months ago, # |
← Rev. 2   Vote: I like it +48 Vote: I do not like it

Nice of you to keep up the trend of problemsetters including their photos in the announcement

Oh, just noticed that I'm not the first one to think of that(

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

hoping to win heart three times very quick....

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hoping to do better after a disastrous run of contests.

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

hope for the best....

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

its either cyan or gray time no inbetween for me

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

Doesn’t the average tester rating seem quite high? :)

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hopefully I can do the first four problems！

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I want to solve ABCD

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

A lovely catgirl! I have to take part in this round. Will I become a catgirl after this round?

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

WOOOOOOOOOOOOOOOOOOOOOOOOOOOOOH

I finally have a legitimate reason to show my catgirl side in front of others. So after this contest I'm going to meow meow meow meow meow meow meow meow meow meow meow meow meow meow meow meow!:3

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

that is crazy

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

cute catgirl.

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

New profile picture

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

catgril !!!

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Looking forward to "Good Luck and High Rating"

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

    Ended up with “Bad Luck and Low Rating”

    → Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

All the best

→ Reply
»
9 months ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Neko round lets gooo!

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

As a particapant i alreary know this is gonna ne a great round

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Good Luck to all the participants.

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

lovely score distribution (´･ω･`)

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

As a participant I like the vibes

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

lets see if this sasha(me) can be specialist or not,, wish me a good luck..

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I need someone to help me,as sasha (*_^).

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

IDK that Codeforces changes its name to Kawaiiforces now =✪ ᆺ ✪=

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I might top this round

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I will start from $$$C$$$

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Wanna help Sasha badly

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Finally, score distribution released

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice score distribution

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

Even in kindergarten, Sasha liked a girl.

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

I'm a bit confused, I guess I forgot registering for contest, and there's timer stating: "Before extra registration", yet I'm unable to register? New here. Edit: my bad

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

i love catgirls

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

C statement is not clear to me?

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

    Same, no idea what its asking. The sample tests seem to contradict the problem statement

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

      I have the same issue with the problem, I even tried to guess it with samples (which shouldn't ideally be the case), but still I don't get it.

      They should add some explanation to more sample cases, or add extra information in the problem.

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

In C I am not able to understand the condition for Yes

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

very unclear statement of problem C.

Spent 30min reading the problem and just 5min solving it.

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

    can you explain problem statement ... testcases are contradicting from problem statement, why testcase 4,7,8,9 are no

    → Reply
»
9 months ago, # |
← Rev. 3   Vote: I like it +29 Vote: I do not like it

For Problem C the explanation is the most unclear explanation I saw

Edit : Thanks for answering our questions by " do not ask questions " XD

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

    You'll change your mind after reading D

    → Reply
»
9 months ago, # |
← Rev. 5   Vote: I like it -6 Vote: I do not like it

sasha is such a simp rizzing girls in kintergarden.. phh

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

i dont get the c question . is it math ?

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

    same, the cases are making no sense according to the test case

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

      yeah after the hint i finally get this . pretest 7 was something very hard to find

      → Reply
      • »
        »
        »
        »
        9 months ago, # ^ |
        ← Rev. 4   Vote: I like it 0 Vote: I do not like it

        In case of 3 3 6, Can't I always bet 1 and get as many coins as required. I am taking the case where there is no consecutive x losses

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

          1 1 1,

          If you win in 3rd time then you get 3, you achive 3-1 = 2 extra. But you already loss 2.So your coin will be no change.

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

        Hey can you please hint me on pretest 7? I failed it and could not figure out why :(

        I start with y = 1 and s = 1 (where y is the money I spend on this round, and s is the total money I have spent). I loop x times, each time update y to 1+s/(k-1) and s to s+y. Finally I check if s>a (i.e. if I have enough starting money for the worst case).

        Edit: Okay.. I just figured out long long is not enough, I need unsigned long long... This makes me feel bad :(

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

Few testcases are literally so weird w.r.to the problem statement.

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

I just think C is clear.

In which aspect cant you understand the statement?

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

    why wont he bet all his money after he end the losing streak , that way he doubles his money and he can get the amount he wants?

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

      I was initially thinking the same but there is a catch and that is what this problem is all about.

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

        cant see the catch , if u dont mind explaining it to me ,after the contest ofc.

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

          Well the casino can 'fuck him over' by giving him a win just before he is guaranteed to win, making him go into a cycle of losing money.

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

            How this works for the test-case 3 3 6?

            Sasha can bet just 1 coin in each round:

            • 1 coin — lost

            • 1 coin — win; receives 3 coins, total coins = 6 — 1 — 1 + 3 = 7

            And so on... Any amount can be created with just 1-1 coin bets!

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

              What if he loses for the first 3 times !! Then he is remaining with 6-3=3 coins.. Then if he again uses just 1 coin, he will be left with 3+3=6, so no improvement, right !!

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

                But, what after loosing 3 times, he bet with the amount 3.... this time he will have total score of 9

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

                Yes, but if he loses first 3 times, as x is 3, won't he bet all his coins for this round.

                • Bet 1 coin — lost
                • Bet 1 coin — lost
                • Bet 1 coin — lost
                • Bet all 3 remaining coins, as x is 3, so total coins now, 6 — 1 — 1 — 1 — 3 + (3*3) = 9
                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  9 months ago, # ^ |
                    Vote: I like it +1 Vote: I do not like it

                  Dude, the point is that the casino can LET HIM WIN on play 3, think about that case

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

                  But how is gonna know when he will win or lose !?

                  He can lose max k times in a row..suppose when he uses 1 coin, he wins but when he uses 3, he lose ! :(

                  His goal will be to make 7 coins from 6, right !

                  Then, that can recursively increase to 8, 9 ans so on..

                  Step 1: He can use 1 coin: If he wins, he is left with 6-1+3=8 (>=7) But he loses, left with 5

                  Step 2: He can still use 1 coin: If he wins, he is left with 5-1+3=7 (>=7) But he loses, left with 4 now.

                  Step 3: Now, if he uses 1 coin, even after winning, he will be back to 6..which is less than 7.. So, he must use 2 coins.. If he wins, OK But he again loses, so left with 4-2=2

                  Now, he is bound to win..but at max he can reach upto 2*3=6, so no increment..

                  I hope you guys get it :)

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

                  Thanks for the explanation. I understood it now!

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

              Take a look at my other comment where I explained the 3 3 6 case.

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

          The casino can decide whether to win or lose if there are no more than x number of games. If you keep betting on one dollar and win in the middle, the total amount will be smaller.

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

            so should i keep betting one and see if i run out of money or not?

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

              Each winning streak resets, and if the casino allows you to lose money in a losing streak, the total amount will not go up no matter how much you bet.

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

                so if after the first streak, my money is decreased , that means he lost or what

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

                  Of course it means that he loses because he can't possibly have more money than the principal.

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

      there is no guarantee that he will lose every single one till he gets the guaranteed win. His lose streak could go zero at the x-1st try.

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

D is not clear at all what's wrong with the writers

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

    I think the contest is made for the writers to understand only <3

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

      What's amazing is that dozen of LGMs just solve anything, I wonder do they need problem statements at all? )

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

        From their experience they solved many problems so they know what the writer want by reading some main points from the statement, one day we will be some of them <3

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

          Yeah, that makes sense indeed. It's like extra skill to be able to understanding the message from a pile of random words.

          At least this round showed me the area I need to practice it a lot :)

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

    It's pretty clear if you ask me, and English isn't even my first language. Can it be worded better? Definitely. But the statement along with the testcases are adequate I think

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

now I won't participate in any contests which have something like love stories in the problems, first diskoteka and his stories about Vika and now this one.

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

Bring back competitive programming please.

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

There is some real BULLSHIT going on with me cout << ceil (value of something); is apparently incorrect in some cases but if We take, ans = ceil (value of something) cout << ans; is correct This is disturbing

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

    cout << ceil(value) returns a floating-point value and ans = ceil (value of something) cout << ans; will typecast that float to integer (assuming ans is of int or long int type)

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

      Thnx Bro didn't know that, it just caused me an hour, so I knew ceil of(val/2) is equivalent to (val+1)/2 so I just randomly changed it to: cout << (val+1)/2; and I was even more furiated when this got accepted :(

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

Why are we gambling on codeforces?

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

felt Question C was not clear at all

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

I wish I could have visited Casino once :(

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

WTF the language of problems is so uncertain and hard to understand,like in b i didnt saw sample test case,and confused in what diagonal means, in c what any number of coins means was also uncertain and i read d 12-15 times and didn't understood the problem, plz work more on problem statements,it sucks

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

Unromantic problem wordings :(... Dreams tonight for ppl solving D, E, and F:

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

i gonna give u a downvote,unless the people who wrote these questions became a cat girl and date with me. :)

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

Rigged ah casino , house always wins!

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

C is an interesting problem that is very poorly worded

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

C is the hardest problem, change my mind

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

Problem D can be solved using the technique of adding children incrementally to a tree, for which I've recently created 2 tutorial and 2 practice contests.

Tutorial 1 and Tutorial 2

Practice Contest 1 and Practice Contest 2

My submission using the ideas from the tutorial.

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

I feel dumb to be unable to solve C. Goodbye Specialist and welcome Pupil :(

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

D and F are very standard, while C was really hard (for me).

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

    I saw F after the contest. Seems easier than D and E unless I'm misunderstanding the problem..

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

    True wasted time on C.

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

    I wonder why D was very standard? It was easy to see dp can be use like dp(i,j) where j={0, 1,2). But according to your dp definition dp(i, 1) it was like simple path starts from i then go to the below leaf node having only one dangerous node. while my definition was simple paths that passes from current node i and have only one dangerous node. Due to this change you are making combination of childs in dp(i, 1) and this also helps in later calculating i parent node dp(par, 2). But according to my definition I have to make those combination in dp(i, 2). B/c if I will consider more than 1 children having 1 node in dp(i, 1) Then it will become 2 dangerous nodes as my definition says passes from current node. But due to this it is missing some cases in calculation of i node parents dp(par,2).

    So my point was many people could come up with my dp defintion as it give a sense that we are considering all the simple paths. Because you are only considering paths starts from node i . Here's a comment Link of someone having same assumption. I think I can AC it with one more array for storing those combinations. But it will become more complex. So Please could you share some problems using this same thinking difference I can relate it with and consider this as standard problem .

    → Reply
»
9 months ago, # |
← Rev. 3   Vote: I like it +96 Vote: I do not like it

The easiest div2 contest I've ever seen (but understanding problem statements is harder than solving them).

A: max(a[i])-min(a[i])

B: If you color cells (1, 1), (1, 2), ..., (1, n), (n, 2), (n, 3), ..., (n, n-1) by this order, you color 2 new diagonals for each cell. And coloring (n, 1) and (n, n) will fill last 2 diagonals. So the answer is ceil(k/2) if k<4*n-2, 2*n if k==4*n-2.

C: Suppose you place a bet of t[i] coins if you've lost i times in a row (0<=i<=x), in order to make the number of coins increase, we must have k*t[i]>t[0]+t[1]+...+t[i] for each 0<=i<=x, and t[0]+t[1]+...+t[x]<=a. So we can calculate t[i] greedily: t[i]=floor((t[0]+...+t[i-1])/(k-1))+1.

D: We consider 2 types of good set: First, assume we take node 1 as root, and for any two different nodes (u, v) in the set, u is not the ancestor of v. In this case, we can calculate the number of valid sets by dp: dp[u]=1+prod(dp[v]), where v iterates over all childs of u, and the number of sets of the first type is dp[1]. Second, assume there exist nodes (u, v) such that u is the ancestor of v. In this case, the set must be contained in the subtree of u, and if we remove u from the set, there will be exactly one child of u, such that the set is contained in the subtree of that child. For each edge (u, w), there are dp[w]-1 sets of second type(we need -1 because {u} is already counted as first type).

E: Let mask[j] = the set of paths that the j-th edge is contained in. We can calculate them by brute force in O(n*k). In fact, there can be at most 2*k different values of mask[j]. Then we let dp[mask]= the minimum number of edges we need to color paths in mask, then we have dp[0]=0, dp[mask]=min(1+dp[mask&(~ t)]), where t iterates over all values of mask[j]. Then we can solve the problem in O(k*(n+2^k)).

F: First turn the binary tree into an array by pre-order traversal, and prepend 1 at the front and append C at the end of the array. Then for each maximal block of consecutive -1 in this array, let L be the number before this block, R be the number after this block, and t be the length of this block, we need to fill this subarray by t numbers within [L, R] and sort them in non-decreasing order. By a well-known conclusion, there are C(R-L+t, t) ways to do this. Because sum(t)<=n, we can calculate it directly and solve the problem in O(n).

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

    how to prove In fact, there can be at most 2*k different values of mask[j].?

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

      Let's prove this by induction. Situation for k==1 is obvious. First, the intersection of several simple paths in a tree is empty or a simple path. Therefore, for any M>0, S(M):={j: mask[j]==M} is empty or a simple path. Then when we add a the k-th path, if S(M) is contained in the new path, then S(M) will become empty (and S(M|(1<<k)) will become previous S(M)). If S(M) have no intersection with the new path, it will remain unchanged. Otherwise, S(M) will have intersection with the new path but not contained in it, and this can only occur at two ends of the path. Therefore, the number of different values of mask[j] can increase by at most 2 when we add each new path.

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

        thanks (●'◡'●)

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

        Thanks for the explanations. But I do not agree with some points in this proof (or I may have misunderstood you):

        1) Based on S(M) being the set of edges i whose mask[i] is M, "S(M) is a simple path" is not necessarily true. Although S(M) must be a part of a simple path (the intersection of paths in M), but it does not necessarily has to totally cover it.

        2) "The intersection can only occur at two ends of the path". We can have cases where 2 paths intersect at their middle.

        A case demonstrating the previous 2 points:

        If we add the paths [5, 6] and [7, 8], S({[5, 6]}) = {(1, 2), (2, 5), (3, 6)}, S({[7, 8]}) = {(1, 4), (4, 8), (3, 7)}, and S[{[5, 6], [7, 8]}] = {(1, 3)}. Also, the intersection between the 2 paths did not happen at any of their ends.

        3) "the number of different values of mask[j] can increase by at most 2 when we add each new path", this is not necessarily true, consider the following case:

        If we add paths in the following order: [4, 5], [6, 7], [10, 11], [12, 13], and [11, 12], the addition of [11, 12] introduces 5 new different mask values ([11, 12] with every previously added path as well as [11, 12] alone). And we still have mask values for each of the previously added paths alone, e.g., mask[(2, 4)] = {[4, 5]}.

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

          I think we could rephrase the statement to something like "There's always an order of insertion such that the number of mask values increases by at most 2 for each new added path"

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

        Therefore, for any M>0, S(M):={j: mask[j]==M} is empty or a simple path.

        Is this correct though? Assume that we have a tree

        1-2 2-3 2-4 1-5 3-6

        We have a path 3-4 and another 6-5

        In this case, S({5-6}) = {3-6,1-2,1-5}, which is clearly not a simple path.

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

    E big brain, I just did $$$ans$$$ or-convolutions (so $$$k^22^k$$$ total)

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

      Still found it easier than D (probably exactly because I skipped the thinking part)

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

      Could you please further explain your approach with or-convolutions?

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

        Let's solve the following problem: let $$$S$$$ and $$$T$$$ be two families of subsets of $$$\{1, \ldots, k\}$$$. Let's find $$$f(S, T) := \{s\cup t\,\colon\,s\in S,\,t\in T\}$$$.

        If we find out how to do this, the original problem is easy: start with $$$S = \text{the set of all submasks for the edges}$$$, $$$T = \{0\}$$$ (or $$$\{\varnothing\}$$$ in the set-theory language). While $$$T$$$ doesn't contain the full mask, increase the answer by $$$1$$$ and replace $$$T \leftarrow f(S, T)$$$.

        To find $$$f(S, T)$$$, we just create two arrays of size $$$2^k$$$, fill $$$1$$$ at all positions corresponding to the masks that are present in $$$S$$$ or $$$T$$$ respectively, then calculate the or-convolution of them. Now at position $$$m$$$ we have the number of pairs $$$(s, t)\in S\times T$$$ so that $$$s\cup t = m$$$. If this is not zero, replace this number with one. Since this number cannot exceed $$$3^{20} = 243^4 < 256^4 = 2^{32}$$$, we can calculate this in unsigned ints and be fine (I even calculated it in signed ints, though their overflow is technically undefined behaviour).

        → Reply
  • »
    »
    9 months ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    for Problem C, I was thinking of the below 2 conditions (t_i is amount bet in ith round):

    1. k * t_i > t_1 + ... + t_i-1 (if at any point we need to restart it covers for previous losses) for all i in 1 <= i <= x

    2. k * (a — (t_1 + ... + t_x)) > a

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

    in F, I guess it is in-order traversal.

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

    I estimated different values of mask[j] $$$k^2$$$ during the contest. (it's much easier to prove)

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

C problem sucks!

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

Can anyone explain the testcase "3 3 6" in problem C?

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

    The rationale for that test case is very poor. I was also confused about the same. They are stating that the casino will always play optimally, and so the player will always just break even, if they apply the best possible strategy.

    Basically, the casino is rigged against you and it's not a game of luck.

    Very poorly prepared problem.

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

      From the statement, which hasn't been modified:

      "In other words, is it true that for any integer $$$n$$$, Sasha can make bets so that for any outcome that does not contradict the rules described above, at some moment of time he will have at least $$$n$$$ coins?"

      Does this not make it clear that this isn't a game of luck?

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

        I understand it now. It was tricky wording to understand without having context.

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

    same

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

    Suppose we want to guarantee a profit if we ever get a win. This will ensure that we won't play more than x+1 games. Because if we lose all x games, the x+1st game is guaranteed to bring a profit.

    Now considering the 3 3 6 case, lets place our bets like this: 1, 1, 2, 2

    You can check and see that, if we at any point except for the last one we get a win, we will be in a profit. But what in the last case? If we win on the last bet we are going to be back at 6 chips. That way the casino can keep us in a loop forever, therefore never giving us a profit.

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

      why do we have to make a profit, can't we just break even(no profit no loss).

      In other words, is it true that for any integer n , Sasha can make bets so that for any outcome that does not contradict the rules described above, at some moment of time he will have at least n coins.

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

        why do we have to make a profit, can't we just break even(no profit no loss).

        If you always break even and never make any profit, how can you reach $$$7$$$ coins in the above example?

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

    If you want to bet all at once on x+1, then the casino can let you win the penultimate game; If there is a bet of more than 1 in bets, the casino will keep you losing, and your total amount will still be less than 6 even if you win the x+1 game.

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

      This makes sense , Maybe they should have worded it like a two players playing optimally type problem.

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

    Bets can be placed in the order 1 1 1 2 (repeating this sequence if achieved a win before).

    Doesn't this guarantees a win? Probably I understood the question wrong :(

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

Treeforces

→ Reply
»
9 months ago, # |
← Rev. 13   Vote: I like it 0 Vote: I do not like it

╱|、
(˚ˎ 。7
|、˜〵
じしˍ,)ノ It was a awesome round. I solve 3 problem. I hopefully reached specialist ≽^•⩊•^≼

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

The integer range check for problem C was DIRTY but NECESSARY.

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The problem C was very ambiguous and confusing. The test cases were poorly explained, and clarification provided extra information not included in the original problem. This should have been a two-player problem where both players play optimally.

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

    Part of the task was understanding that the worst case scenario in a random setup is an adversary.

    → Reply
    • »
      »
      »
      9 months ago, # ^ |
      ← Rev. 2   Vote: I like it -24 Vote: I do not like it

      It was never stated that the task had an adversary. A casino is supposed to be random. If I can break even in the worst case and profit in the best case, then I will eventually profit. It is not stated that the process is not random but deterministic, it is a fault in the problem.

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

        When you analyze an algorithm like quicksort, does the universe tell you there's an adversary making it as unsortable as possible? No, but that's how worst-case analysis ON a RANDOM process is conducted.

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

Please, do better problem statements.

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

    If I hadn't given that explanation, I might not have been able to understand the C in this game

    → Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I am going to be a gambler!

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

Took me 1 hour to understand C (in fact I used that time to solve D, but couldn't).

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

    Because understand statement is part of solution

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

      So, you didn't think this might be an issue?

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

        If it's difficult to understand what it means to get an arbitrarily large number and what an adaptive strategy is, then you probably just aren't ready for this task.

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

      Correction: understanding

      I think I know why the statements were unclear.

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

Could anyone please explain C? I thought I would bet 1 coin for x times, so after losing x times i have a-x coins. Then i can simply bet the entire remaining amount, right? But the test cases dont match. Someone please help me out!

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

    Me too!

    → Reply
    • »
      »
      »
      9 months ago, # ^ |
      ← Rev. 3   Vote: I like it -31 Vote: I do not like it

      It's worse than Good Bye 2023.

      If nothing else, my name is going to be gray (and within 10 rating of green).

      UPD: Just looked at it with the plugin, down to 1199 rating...

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

    casino is smart he will only let you loose x-2 times and will make you win on x-1th time so the counter starts again, i realised this in contest but still could not solve it :(

    think of it as two player game with condition that player 2( casino ) can't win more than x times

    EDIT: added second paragraph

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

    we have to think that every time, from the 1st to the x+1th time,
    if we win the bet we will make a profit, but if we lose, we will lose the least.
    And we have to check that we can do this without running out of initial money.
    sorry for my bad english.

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

    You're assuming that the casino would make you loose if you bet 1 coin, they also want you to loose as much coin as possible. So what if they let you win if you bet 1 coin so that the streak for x breaks and then they can take the bigger amount of coin.

    → Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

hint for D pls?

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

    Root the tree at vertex $$$1$$$. Try to find out all the configurations of subtree at node $$$u$$$ such that all upward path to node $$$u$$$ have a maximum count of black vertices as $$$0$$$, $$$1$$$ or $$$2$$$.

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

For D, I tried to find the number of distinct paths of length in the range [3,n]. For this I copied the code for the problem Fixed-Length Paths II of CSES Problemset Link. Then I subtracted this value from 2^n (Total no of possible sets). But my answer didn't match with sample test cases. What was I doing wrong ?

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

    Number of distinct paths of length >= 3 does not equal to number of subsets such that at least path exists with length >= 3.

    → Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

l don't like this time in rating:b+(600~800)=c,a=b and c=d

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem C was like a horror experience

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

С>D=E=F

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

    In my opinion E>C>D>F. Didn't found that there are just 2*k different masks :(

    → Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

i dont wanna stay in grey forever :(

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain the 3rd question of the 4th question, how does Sasha lose? Sasha always plays 1 If the number of consecutive losses is less than 3, he always gets at least 1 point If the casino gives 3 losses in a row, Sasha will have at least 3 coins and get at least 9 points As a result, he can always increas his mony

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

    They don't necessarily lose three in a row.

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

    "He always gets at least 1 point If the casino gives 3 losses in a row"

    What If the casino doesn't?

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

      Well, if they don't do this, then we have a maximum of 2 losses in a row, and with the next win, the number of his coins will be -2 + 3

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

        No, after losing a game, the losing streak is reset to 0.

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

          Can you explain more?

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

            Initially, you have streak = 0, money = 6

            If you bet 1 and lose streak = 1, money = 5

            If you bet 1 and lose streak = 2, money = 4

            If you bet 1 and win (the casino can control this) streak = 0, money = 6

            It's back to the beginning. :D

            → Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone can explain problem statement of D atleast then i could think of solution.

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

    +1

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

    +1.

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

    I will simplify the statement in a more straightforward way.

    There is a tree given with $$$n$$$ nodes. Let's say you choose a subset of nodes, then you will mark those nodes in the tree in red, now this subset of nodes will be called "bad" if there is any possible simple path in the tree such that there are more than $$$2$$$ red nodes lying on it.

    You have to count the number of subsets that aren't "bad", the subset can be possibly empty.

    PS: I also had to read several times to come up with some understanding of it. The terms "city" and "intersections" are confusing together.

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

Pretty good round, the hardest problem was getting to the round in time

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

Statements be like:

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the great problem C FairyWinx.
I surely enjoyed the clear problem statement and will cry to bed tonight with a 5-digit rank and -100 delta. Thanks once again.

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

OHHHH catgirl power! I may become purple this round!

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Give me some hint for D pls

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

    u can see my code, use dp.

    dp[u][i] means in u's subtree (includes u), pathes that start with u has a maximum of i dangerous node (i ∈ {0,1,2})

    for the staus's transformation, u can look through my code or just think with yourself.

    Code

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

      For me, dp is a lifelong enemy:(

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

      Why do paths that start with root node correspond to number of sets? Are we covering all the paths, what about the ones that do not start at root?

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

    Tree ᓚᘏᗢ

    → Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Am I the only one who couldn't find the logic behind problem C?

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

I like how the contest concluded that the best gift for your girlfriend in Valentine is a binary search tree.

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I can understand what C means, but I can't understand D... I guess the questioner wrote the question in his native language and then used software to translate it into English, just like this comment.

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The problem statement of C could have been better if it has that announcement in a note

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

Sample tests for prob D are just rubbish

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Literally it took me half an hour to understand what problem d wants to say btw thanku for the contest

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

Didn't know Codeforces was a gambling site :(

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm very glad that I solved CD and nearly F. Thanks for the problemset!

TreeForces

D: I think my solution 246547495 is strange. I did 2 passes of DFS and DP on the tree, and the calculations are not that straightforward.

F: How do you manage to calculate C(C, n) mod M where C=1e9 and M=998244353? Neither preprocessing or Lucas worked. Or is my solution not the intended way? 246561698

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

    Sum n for C(C, n) less N and you can calculate this with for

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

    Try this formula: $$$\binom nm=\frac{n(n-1)(n-2)\cdots(n-m+1)}{m!}$$$

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

      Thank you! I have just completed round 925G and everything I thought of is to copy paste that part.

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

IELTSforces

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

There is a participant in my room submitting obfuscated solutions to avoid getting hacked. I think that conduct is against the official rules of the contest. Who should I report this issue to?

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

In my opinion, dear Fairy Winx should learn human language before learning programming language, so as not to put such unclear and incomprehensible questions in the context.

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

System test was fast, anyways

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Do you know "Ha Jimi" ?

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

After this round, I will definitely not get involved in gambling.

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

Get a job Sasha!!And stop Gambling!!

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

Very unbalanced

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

I think it will be beneficial for ones who has known about the "doubling bet" strategy to solve C, although it is just the case when k = 2.

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

D easier than C I think.

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I get the error "wrong output format Expected integer, but "2.6917e+07" found" with Problem B in test number 4.

How to fix or avoid that error?

246566145

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

    Transform your answer into integer but not float.

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

    This part you cout after doing division with 2.0, so the result will be a float (That's why it has the e+07 part)

            if (2 * n >= k)
        {
            if (k % 2 == 1)
            {
                cout << (k - 1) / 2.0 + 1;
            }
            else
            {
                cout << k / 2.0;
            }
        }
    → Reply
»
9 months ago, # |
  Vote: I like it -6 Vote: I do not like it

bad statement for problem c

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

Sasha's girlfriend confirmed imaginary.

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

    Conclusion: Sasha's girlfriend exists only in his imagination (not surprising)

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

I think problem C statement is good, at least you can figure it out by yourself that casino isn't always gives you win only after $$$x$$$ loses. Maybe it would be better if it had been written "you don't know will you win or lose, but you guarantee will win after $$$x$$$ loses in a row"

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

One Moment of Silence for all those who struggled the entire contest in problem-C...

(Just because of unclear statements).

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

for C just think there is one man who control you lose or win, and you should find a way to get coins more. so, for every bet you should think if this turns you win your coins how to increase. so, if you have lost k-1 coin, you should put 2 coins next time, if you don't do it, the man will let you win and you will get k coins but you have spent k so your coin didn't increase. so, if you have lost b coins, next time you should put b//(k-1) +1 coins. for my code https://codeforces.net/contest/1929/submission/246544539

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Great contest ! Any hints for D ?

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

    1) What is a path in a tree?

    2) What pairs of vertices $$$(v,u)$$$ should we observe?

    → Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This code must get TLE,but why am I get Unsuccessful hacking attempt?

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

In my opinion F<<D... So why is a BST written in the statement? Just to make it scary and match our past impressions of the difficulty of problem F?

btw why is C (in F) up to 1e9, not 998244352?

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

    For the C in problem F: Both options "overflow" the binomial, as you need to use the stars-and-bars method, so it does not matter.

    → Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone say what really problem C ask for? I can comprehend nothing

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

    in simple terms it's asking can you have infinite amount of coins

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

If D appeared in an Atcoder contest, here's what the statement would've been.

Given a tree, you need to color each node in black or white. How many colorings exist such that the path between any two vertices contains atmost 2 black vertices.

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

    Yes, Atcoder is very good at writing statements . Nothing rubbish is written unlike todays C.

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

    can you give me the link to the contest?

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

      I didn't mean that it has appeared in an Atcoder contest. But if it did appear, this is probably how the statement would've looked like.

      BTW, I did reword the problem according to this statement in this mashup contest

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

        Oh sorry, i misunderstood your comment.

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

Bad statements

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

any hint for B...please

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

    Think about how much the number of diagonals can increase if we color in a single square. Also, think about how to include all diagonals with the least amount of colored squares.

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

    If k!=4n-2 then the ans is ceil of k/2. If k==4n-2 then ans is (ceil of k/2)+1 because some cells will have only one unique diagonal. Take n = 5 and 1<=k<=18 and draw a grid with diagonals and try to find ans for each k then you will understand what I am saying.

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

I really hope that Sasha was able to win the girl's heart.

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

I recently came with a rule that in a contest when there are multiple submissions then last pretest passed submission will be used for system testing and previous submissions are skipped. In this contest, I submitted 1st question under 2 minutes and got pretests passed (Submission id- 246491221) and i accidentally submitted similar code again after almost 1 hr 50 minutes (Submission id-246561262) and as per rule my 1st submission skipped system testing and 2nd submission got accepted which made my score drop and my rank drop from nearly 3300 to 5330 which will affect my rating.

I wanted to request that there should be some feature to lock any submission you want and not just last pretest passed submission as it is just taking penalties/lower scores without any reason. And also, if no submission is locked then next submission should only be tested if previous submission failed system testing which is done in some of the contests.

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

    There literally is a feature to lock your submission. Furthermore, after this you can read the codes of other people from your room to this problem, and if you think the solution shouldn't work on some test you know, you can even provide the test and get some points if their solution fails!

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

      Ah, I reread your comment and understood that you want to lock a submission that is not the last one

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

        Yes, exactly i haven't locked my 1st correct submission and submitted it again. Then i was trying if i can lock my previous submission but was not possible and instantly my score and rank was dropped.

        → Reply
»
9 months ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

for Problem C, Are these 2 conditions correct (t_i is amount bet in ith round):

  1. (k — 1) * t_i > t_1 + ... + t_i-1 (if at any point we need to restart it covers for previous losses) for all i in 1 <= i <= x

  2. k * (a — (t_1 + ... + t_x)) > a

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve the C? I think binary search

→ Reply
»
9 months ago, # |
← Rev. 2   Vote: I like it +29 Vote: I do not like it

Test data for D are weak. Many people just printed ans + 1 or even ans + n + 1 without performing modulo, but they still got accepted.

Here's a hack that creates an answer that is exactly 0 — or 998244352 + 1: https://codeforces.net/contest/1929/hacks/983200

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

E>>F

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem C , how for test case : 2,3,15 , answer is yes ?

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

    betting sequence 1 2 4 8 in any scenario you you atleast once have total coins > initial coins so after that you can repeat the sequence and get as many coins

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

      Not clear, what 1 ,2 , 4 ,8 sequence here are you referring to??

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

        this is a no. of coins you bet each round

        → Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

someone please explains the problem C.

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

    you can't lose x times continuously and win/lose is random so your win expectation is >money you've lost. do this x times if your money isn't 0 you must win money.

    → Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I think that problem C was not clear before the announcement was made and it became clear afterwards

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

Can C be solved using Binary Search??

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain me D

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

I feel like the problem set is rather imbalanced.

A B C all math

D E F all trees

also E, F is of similar difficulty (from number of solves). Should make F harder I think.

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey guys, I saw this blog post about problem C. This is really unfair for many of us who legitimately participate in contests on our own. https://codeforces.net/blog/entry/125935

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

I did problem C with what seems a solution identical to the other ones, but I kept getting Incorrect Answer 7, can someone please explain what is wrong? Thank you

https://codeforces.net/contest/1929/submission/246537505

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

    If I am not mistaken, my code failed on the test 2 1 6 for which my code wrote YES, but the answer seems to be NO, can someone explain this?

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

      i am new at CP ,was this contest rated because i didn't got any rating.

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

    The value of prev_sum can overflow out of long long datatype. You need to break early if prev_sum > a at any point.

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

couldn't escape expurrt after spending first 30 min trying to understand D >;-;<

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

Although I was not a participant in this round, the Problem and sample analysis of Problem C was terrible and bewilderingly.

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

No-sigma raund

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why the f is that my problem d was in russian : |

→ Reply
»
9 months ago, # |
← Rev. 2   Vote: I like it -13 Vote: I do not like it

C is nice , bit hard to understand

→ Reply
»
9 months ago, # |
← Rev. 6   Vote: I like it -10 Vote: I do not like it

deleted content

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

Problem D is a good introduction to DP on Trees. For training purpose, I added the problem to a mashup and simplified the problem statement, so that it's easier to remember it by name.

You can access it here.

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

"Please do not ask questions about test cases in the example that are not explained. We cannot answer them, as it is a hint to the solution of the problem."

this was the most naive response I have ever seen. I believe I'm not the only one that thinks that the statement was a real mess.

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem C statement was not clear ...

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

Me to ques C ---> Link ;-;

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem C video solution with live coding: https://youtu.be/XRjHt1rnzqs

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

I spent too much time on problem C and Did not attend problem D which was easy . Problem statement was not clear and ended up with negative rating change.Regret giving this contest(T_T).

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

great contest, and love the catgirl!

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I've got no idea why my code for D doesnt pass the official test.

It says that it expects output '12' (instead of '11) on test number 2.

But when I run this test locally I get result '12' :O

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

We need more anime rounds. Please naruto

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I love the concise statements.

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Sasha Lol, it reminds the character "Sasha Blouse" from AOT.

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

D is an easy version of https://atcoder.jp/contests/abc340/tasks/abc340_g. Just set Ai=1.

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is E's hack opened?

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

I failed Sasha. He will be single forever.

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

this c i feel bad QAQ

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please tell me why my answer is wrong?

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
int main(){
	ll t;
	cin >> t;
	while(t){
	    ll k, x, a;
	    cin >> k >> x >> a;
	    bool flag = true;
	    ll lost = 0;
	    ll bet = 1;
	    for(ll i = 0; i < x; i++){
	        if((bet * (k - 1)) > lost){
	            lost += bet;
	            a -= bet;
	        }
	        else{
	            bet = (lost / (k - 1)) + 1;
	            lost += bet;
	            a -= bet;
	        }
	    }
	    if((a * (k - 1)) <= lost){
	        flag = false;
	    }
	    if(flag){
	        cout << "YES" << endl;
	    }
	    else{
	        cout << "NO" << endl;
	    }
	    t--;
	}
}
→ Reply
»
9 months ago, # |
← Rev. 5   Vote: I like it -16 Vote: I do not like it

In the statement of problem C: "Note that the bet amount must always be a positive (>0 ) integer" and "Sasha also knows that there is a promotion at the casino: he cannot lose more than x times in a row." As we can see.. two very clear RULES. the statement also says: "is it true that for any integer n , Sasha can make bets so that for any outcome that does not contradict the RULES described above, at some moment of time he will have at least n coins." Meaning, the casino must never let his money reach 0 -THE FIRST RULE IN GAMBLING IS THAT YOU MUST HAVE SMTH TO GAMBLE WITH OTHERWISE YOU HAVE LOST-, and if he reaches the limit of losses in a row, the casino must make him win -THE MADE UP RULE OF THE GAME, BUT YET STILL A RULE-.... And as we saw in the testcases along with the tutorial, when his sum of money reaches 0 while his losses in a row aren't past the limit yet.. the game ends... In a logical world.. Sasha will always win... cos... "any outcome that DOES NOT CONTRADICT the RULES described above" but the tutorial, the judging server, as well as the test cases proved differently.. I hope for less ambiguous statements in the future. edit: I read the problem after the contest and the adjustments were not yet added to the statement..

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

shinonome ena???

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

The system has suspected of me copying the code for problem C. I think it is because I have never solved C in div 2 before or whatever the reason may be. I was pretty close to solve C in the previous div 2 as well. Anyways here's proof I did not cheat

I had seen similar questions before, and knew it was a gambler's ruin problem https://youtu.be/Ne2lmAZI4-I?si=C6cn7-NH0nUfwroV Pretty popular video on the problem. Once that was known, I only had to check if I had the required amount of money to bring back my amount lost after every gamble. And the most I could lose was x no. Of times. So that's only what I've done. I don't know how it was similar to other people's code but it's only normal for them to write in Java with the same logic and very little scope of picking other variable names. And Gpt will write the same code for the command I have written above. It is that simple. I rest my case. I hope I am heard.

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

    Same exact situation for me, except I never saw a video about it. Incredibly frustrating.

    → Reply
»
9 months ago, # |
← Rev. 14   Vote: I like it -23 Vote: I do not like it

Great problemset

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

Ok, same problems. thank you, i'm still scared

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I got my problem removed for rules violations despite the fact I did and do not share or receive solutions. This is where these solutions probably came from https://www.geeksforgeeks.org/count-sum-of-digits-in-numbers-from-1-to-n/.

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

wuw

→ Reply