YouKn0wWho's blog

CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
By YouKn0wWho, 4 weeks ago, In English

কি অবস্থা ব্রো? আবারও চলে এসেছি! (That's Bengali for "What's up bro? I am back again!")

I am super excited to invite you to participate in CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!) which will be held on Nov/23/2024 17:35 (Moscow time). This round is rated for both divisions.

The contest will feature $$$8$$$ problems, with three of them divided into two subtasks each. You will have $$$3$$$ hours to solve as many as you can. The problems are authored and prepared by me and wuhudsm.

I would like to thank -

Score distribution:
$$$500 - 1000 - (1000 + 1500) - 2000 - 2750 - (2000 + 2000) - 4250 - (2250 + 2500)$$$

Wishing you TONs of luck — hope you have a TON of fun cracking the problems!

UPD: Editorial

UPD: Congratulations to the winners!

  1. orzdevinwang
  2. tourist
  3. Rewinding
  4. Kevin114514
  5. maspy
  6. Radewoosh
  7. ksun48
  8. jiangly
  9. cn449
  10. maroonrk

And here is the information from our title sponsor:

Hello, Codeforces!

We, the TON Foundation team, are pleased to support CodeTON Round 9.

The Open Network (TON) is a fully decentralized layer-1 blockchain designed to onboard billions of users to Web3.

Since July 2022, we have been supporting Codeforces as a title sponsor. This round is another way for us to contribute to the development of the community.

The winners of CodeTON Round 9 will receive valuable prizes.

The first 255 participants will receive prizes in USDT cryptocurrency in the TON network:

  • 1st place: 2,560 USDT
  • 2–3 places: 1,280 USDT each
  • 4–7 places: 640 USDT each
  • 8–15 places: 320 USDT each
  • …
  • 128–255 places: 20 USDT each

All participants will receive Soulbound Tokens (SBT) that reflect their developer rating

We wish you good luck at CodeTON Round 9 and hope you enjoy the contest!

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

»
4 weeks ago, # |
  Vote: I like it +383 Vote: I do not like it

And here's something special: Solve problems and make a difference! Yes, you heard it right, just like my last contest, this time as well you can help the world just by solving problems. I will donate money to the underprivileged people in my neighborhood based on the solve count of each problem by the following measure:

Donation Per AC

You can check how it went the last time I did this: https://mirror.codeforces.com/blog/entry/96333#comment-907470

Also, the top $$$5$$$ Bangladeshi contestants will receive $$$1000, 800, 700, 600,$$$ and $$$500$$$ BDT respectively from me as a small gift!

Note that neither TON nor Codeforces has anything to do with the donation or the gift.

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

As a tester, I can confirm that this round does indeed have problems.

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Best wishes to the round, contestants, and problem setters.

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

As a tester, I tasted many flavours from the problems.

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

GLHF everyone!!!!!!!

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

change time/day icpc india clash

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

    Yes please :(

    Gotta wait one more week before the next contest

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

good!!

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

And The GOAT is officially Back!

Hope everyone outperforms themselves in this contest!

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Super excited for CodeTON Round 9! The problem lineup and the collaborative effort behind the contest sound amazing. Big thanks to the authors, testers, coordinators, and the TON Foundation for making this event possible. Looking forward to an epic 3 hours of problem-solving! Let's crack these problems together. Best of luck to everyone participating!

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

YouKn0wWho is back!

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

Where is the prize for top 256 — 511 and 512 — 1023? :(

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

Going to attend my first YouKn0wWho contest !!!

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

As a taster, I found the problems very delicious.

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

What is the rating distribution??

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Finally found a great opportunity to receive 0 BDT

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm waiting for this round,bro

→ Reply
»
4 weeks ago, # |
← Rev. 2   Vote: I like it -8 Vote: I do not like it

deleted

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Div 3er contest chai :)

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I have just realized from automated polygon emails that I already seen a problem from this contest (and even have access to it on polygon) since TheScrasse has just commited on it. No one has told me before this that I could not participate...

wuhudsm please do better.

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

    Actually you were coordinating wuhudsm's round but you gave it to me, so this time it's normal you have already seen the problems :)

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

      That's not the point. Also, why should I assume it's a problem I've seen before? The annoucement said that wuhudsm only contributed 1 problem. It's quite likely its a new problem???

      No one told me that I have already seen problems before. That is not ok. If polygon didn't send the above email (and you didnt suppress emails), I might have participated?

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

    I only received the message yesterday that YouKn0wWho's round requires an alternative problem, and the coordinator needs to select a problem from my round (which you previously coordinated). We are struggling with selecting problems and fixing bugs. We only confirmed the final problemset a few hours ago. And I expect to notify you after participating in today's codechef round. Overall, I apologize for not communicating with you in a timely manner.

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

      Sorry, I overreacted. I didn't consider that the problem could have been just added......

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

As a participant, I'll participate!

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

****too much excited**_**

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

Why are prizes in USDT instead of TON? Not that I will get them lmao.

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Going to attend my first YouKn0wWho contest !!!

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Programming is important skill, he is welcome to participate

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

অন্তত তিনটা সল্ভ করার ট্রাই করব ভাই। I will try hard to solve atleast three problems.

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

As a participant I'm Excited!

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

clashing with icpc prelims india

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

if possible please change the time/date of the contest as icpc india preliminary contest will be held on the same day 23rd nov 21-23:30. so that we all can take part too!!

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

    After reading this comment we considered moving the round, but unfortunately it cannot be done anymore.

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

      why not if i may ask? just shifting by 150minutes would work ( i have no clue about the underlying things and complexities of rescheduling but yes just curious)

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

        If the round is held at an unusual starting time, the participation usually decreases (maybe also in this specific case).

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

    ICPC is unrated anyways

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

I see tourist registed for this contest！

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

Is there supposed to be a score distribution or is ranking based on # of problems solved (ICPC format)?

→ Reply
»
4 weeks ago, # |
  Vote: I like it -26 Vote: I do not like it

They let anyone make contests these days...

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

div1+div2 is tooooo hard,I always try my best,never beat it:(

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

The timing of this contest overlaps with the India ICPC Prelims, and I really want to participate in both. Unfortunately, I’m torn between the two. :'(

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

.

→ Reply
»
4 weeks ago, # |
  Vote: I like it -33 Vote: I do not like it

cringe profile pic sir

→ Reply
»
4 weeks ago, # |
  Vote: I like it -26 Vote: I do not like it

clashes with Icpc India preliminary round

→ Reply
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it -42 Vote: I do not like it

    Looks like a lot of people here don't like India.

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

wuhudsm orz

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

Unlike the TON round 8, 256-1023 places lose their prizes, and 20 USDT is much less than 8 TON (8 TON > 8 * $5 = $40 = 40 USDT), which 128-255 places got in round 8.

Their settlement is also without TON now.

What happened to TON?

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

    I wouldn't say it's fair to take CodeTON R8 as a basis for prize comparison. That exact reward system was introduced in CodeTON R2 and didn't change until now. And the average (or actually median) Toncoin price for that time period was ~ $2 which gives 128-255 places in CodeTON R2-R7 less money (at the moment of receiving the prize) than they are promised here. Also, if we keep counting having $2 in mind as a pivot — we'll see that the total prize funds for almost all previous CodeTON rounds are really close to the current one ($20480). R8 is the only significant exception from this rule. What's also interesting about it is that Toncoin price at the moment of publishing R8 announcement was again ~ $2 but jumped 2.5x till the moment when contest actually held. Not sure what was the further story behind it and if TON Foundation actually paid everything in Toncoins like they did before and what was the price of it at that point if they did. But I believe this case (sudden 2.5x jump of prize fund in 1 month) is the reason they decided to switch to stablecoins and it seems pretty reasonable. Yeah, payouts in Toncoin were a good additional advertisement of their own crypto but it got too expensive last time and I would actually be grateful that after R8 incident they switched to another way of doing things instead of dropping it entirely (how many other companies do you know, who were so generous in sponsoring CF rounds and did it so many times?).

    That way or another it doesn't explain removing the prizes for 256-1023 places so I agree with a first part of your comment (and couple others below and above). In previous rounds they were able to make happy 4 times more people (kudos to TON Foundation for it!) with the same amount of money so it feels a bit disappointing to see this changing now. But we have what we have so good luck to you and other reds in the race for a prizes this time!

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

why 256-1023 places no prize this time :(

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

Let's make it to Specialist this time :)

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

G

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

Fun fact: 11 scoring opportunity is the unique largest for modern (= after CGR1) rated Div1+2.

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Bangladesh❤

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Excited to participate in a contest authored by Lord Voldemort.

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

Should we solve problem in order $$$A-B-C^1-C^2-D-F^1-F^2-H^1-H^2-E-G$$$? Why $$$H^2$$$ is even easy than $$$E$$$?

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

    No, I believe it's more precise to assume that P2 relative complexity is described by P1+P2 score. So the current order does make sense to me although people might want skip some P2's and jump straight to the next P1 in the list

    → Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

We are proud of you brother. Take love from Bangladesh.

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

redpanda orz

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Less prize :(

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

Will finally take part in another CodeForces Round. Very fun way to spend time. Hope to reach expert.

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

so excited as a bangladeshi hosting a contest.

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

sorry for asking but what's a Soulbound Token? :/

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there a penalty for wrong submissions?

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

All participants will receive Soulbound Tokens (SBT) that reflect their developer rating

What is the SBT Here Brother ,how its works.

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

hope to continue my form today as well

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

Hope we all get TONs of TONs!

→ Reply
»
4 weeks ago, # |
← Rev. 3   Vote: I like it +21 Vote: I do not like it

mathforces

edit: GCDforces

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

tourist might no longer be Tourist :(

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

Funny that E can be OEIS'd with a little bit of heavylifting.

I'm not sure if anyone tried OEISing F1 as well, but bruteforcing small cases for F1 is too troublesome. (wait, now I just realized F2 only raised a bit of constraints comparing to F1, this cheese shouldn't be possible ever...)

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

    omg I tried OEIS but failed. but I solved this...

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

    I tried looking on OEIS but unfortunately with the wildcard query 1,2,5,19,_,682 which doesn't match the transformed sequence T_T

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

      Yeah, I fell into the same roadblock as ya. Had to bruteforce as far as I did in the link, and even that would only give me the series of their deltas.

      → Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Really liked E

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

I really like how problem D boils down to a such a simple formulation.

The observation in E that the relation becomes trivial for arrays with inversions $$$\gt 1$$$ is also really cool. Still a bit salty I spent ~1 hour failing to calculate the number of arrays of length $$$x$$$ with 1 inversion correctly but that's totally on me since both the logic and the resulting formula aren't math / case-work heavy at all.

On the other hand, I'm not really a fan of C2. At least with my solution, it feels tougher than D (and definitely more irritating than either D or E) due to the associated case-work.

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

Animated Video Editorial for the Contest! Problems [A,D]

Link: https://youtu.be/elRvvUbk1J4

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

Bad C2.

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

why my submission get tle (problem d) 292986056 . any help would be appreciated.

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to D?

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

    using a sieve type of algorithm

    292980591

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

    if n is greater than or equal to $$$2^m$$$, then the answer is -1

    otherwise, you have to calculate to each index, how many prime numbers it have in its prime factorization, assume this number is in $$$cnt$$$ array

    then the result for this index is $$$S_{cnt[i]}$$$ (you have to reverse the set S)

    (the first index should have $$$S_0$$$)

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

I admire Shohag for his consistency in creating inelegant problems

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

E was availabe on OEIS

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

Thank you for AtCoder Regular Contest!

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

gcd round

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Loved the round, cool problems

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I donated a total of 0.009 USD (0.001 + 0.001 + 0.002 + 0.005), and I feel so happy about it!

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why didn't I get TLE with this code?? For C : https://mirror.codeforces.com/contest/2039/submission/292955782

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

    There's an upperlimit on total itarations in the for loop, that is actually min(2*x, m), so in the worst case scenario there are only 2*x = 2e6 operations. Moreover, the statement says that the sum of all x from all test cases is at most 1e7, so the complexity of your algorithm is O(1e7).

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

couldn't solve D in 160min, my brain ... 🙃

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

My brain was absolutely fried on B, I was considering the wrong definition of subsequence even AFTER the announcement came out... even submitted my solution onto a different problem once by accident lol

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

WA on B round

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

The bulk of the problems look... too much alike :) .

However, problem H is very nice, and a welcome step away from the prevalent topics.

Thanks for the contest!

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Isn't there any streams today?

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I genuinely do not know how to solve C1. For the case x <= y, simply get the factors of x in O(sqrt(x)) time and get all those values XOR x in some set S. Then get all values in S >= 1 and <= y.

How do I solve for the general case? Surely O(sqrt(m) + sqrt(x)) is too slow, right?

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

    y is no more than x * 2(or 4, something like that)

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

    Observe that after y reaches 2*x, y^x will forever be bigger than y/2 and x/2. So you can just iterate up to 2*x and count

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

      Of course every time I get near expert, some bitmask problem comes around and screws me over...

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

        That should tell you something.

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

          Yeah I know I gotta practice bitmask problems then... what annoys me is that they are always so ad hoc that there is not much transferability of knowledge amongst such problems.

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

            I totally disagree with you, the ideia in this problem is very recurrent. Y^X will always be bigger than Y/2 because you will never turn the MSB off and that is the main point. Most of bitmasks problems is usefull to look at the MSB or try to solve bit by bit. Good luck on hiting expert.

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

    $$$y$$$ can only be in $$$[ 2^w, 2^{w+1} )$$$, where $$$w$$$ satisfies $$$2^w \le x < 2^{w+1}$$$, so you just need to iterate and count in this interval.

    → Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

too low participant, it's slightly less than 9000 is CF is in decline ?

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

    Perhaps they don't want to participate in the math Olympiad.

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

Thanks for low time limit in C2

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

correct me if I am wrong, I tried problem D and I think in the notes the gcd was calculated incorrectly, it was actually lcf..

were we supposed to solve it as if the lcf was gcd?

maybe I just did not understand the problem since I am newbie TT

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

    I'm not totally sure which part you're referring to, but one part of it said $$$a_{gcd(2,3)}=a_1=6$$$, which is correct because $$$gcd(2,3)=1$$$.

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

      ohh yess I thought it meant.. nvm I was too dumb, thank you for pointing the logic, really appreciate that,

      I really need some sleep I think, not to mention I spent 1h on that while assuming things that did not exist :)

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

competitive programming? nah, we gonna do some math olympiad..

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone explain d in detail

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I just counted throughout the round, liked problem E tho:)

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

CodeForces ❌ GuessForces ✔️

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

CountForces today for counting problems in E,F,G

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

What was this with C2? I have no idea what I did for the solution, just stress-tested and ifed found cases until it passed.

Gcd round indeed.

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

    (x ^ y) must be divisible on min(x, y). Let's calculate y <= x normally so now (x ^ y) must be divisible on x. So we have some i (>= 2) * x, x < ((i * x) ^ x) <= m. If i increases, ((i * x) ^ x) should GENERALLY increase but not always. So let's first assume we get all Is from 2 to m / x(ans += m / x — 1) and then calculate 1e5 before i = m / x and 1e5 after it manually. 1e5 is some random constant so it may fall on systests

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

      No, it worked on systests. No idea why tho

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

      It is indeed clear you do first $$$cx$$$ normally and then you should only get the ones that are divisible by $$$x$$$, and there will be somewhat like $$$\frac{m}{x}$$$ of them. However it can be y > m that converts to y $$$\oplus x \le m$$$, and you also need to if this. But then it turns out your $$$[0;cx]$$$ can be intersecting with your $$$[m-x,m]$$$.

      So you start if-ing cases when they are overlapping and then you just add even more ifs found by stress tests.

      Not saying it is a bad problem overall, but it is definitely an overkill for C2. There probably is an elegant way to solve without that many corner cases, but I dont believe that's a problem that is always solvable by not that experienced participant even after they got the main ideas.

      Also i think 1e5 is a bad constant as $$$x \le 10^6$$$. $$$x$$$ should be enough, and less than $$$x$$$ is not enough -- imagine $$$m = 10000{x}_2$$$ (having $$$x = \ldots101_2$$$), than you can take $$$m - x + 2$$$ and it will give you xor bigger than $$$m$$$.

      Probably the easiest way was just to solve $$$m \le 4x$$$ the naive way and do first $$$2x$$$, last $$$x$$$ and then formulas otherwise.

      → Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem D, why aren't the three biggest elements in S enough? My construction is as follows: let a, b and c be the three biggest elements in S, let a_1=a, a_2=b, and from now on a_i=b if i is odd and a_i=c if i is even. I haven't found any clear contradictions.

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

    then how about $$$a_{15}$$$, for $$$a_{\gcd(3,15)}=\gcd(a_3,a_{15})=b$$$.

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

      Oh yeah, i completely missed that, my bad. So what is the solution?

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

        we can first sort $$$S$$$ in descending order.

        $$$a_1$$$ must be the maximum element $$$S_1$$$. From $$$a_2$$$ to $$$a_n$$$, they can't be $$$S_1$$$.

        consider $$$a_2$$$, it should be $$$S_2$$$, and all elements $$$a_j$$$ with $$$j=2k$$$ can't be $$$S_2$$$.

        So here's the pattern: we can let $$$a_i=S_{b_i}$$$ for every $$$1\le i\le n$$$. Then you can find $$$b_i=\operatorname{mex}_{j|i}{b_j}$$$. Here $$$\operatorname{mex}S$$$ stands for the minimum possitive integers which didn't appear in set $$$S$$$.

        so you can solve this in $$$O(n\log^2n)$$$.

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

          maybe I'm a little dumb for using this silly algorithm, but it did reflect my thoughts during the contest.

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

    Countertest:

    12 4
1 2 3 4

    (Actually the set $$$S$$$ could be any set of $$$4$$$ elements)

    You will fail because $$$\gcd(a_4, a_8) = 2 = a_{\gcd(4, 8)} = a_4$$$.

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

    n = 8

    [a b b c b c b c]

    gcd(a_4, a_8) = c = a_gcd(4, 8) = a_4 = c

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

C2 is bad at all...

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

$$$CF2039E(n)-2\times CF2039E(n-1)+CF2039E(n-2)=A079752(n)$$$

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to c2?

I had 60 * x and it tled

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

    Had 2 * x and enum (y mod w)? [w = 2 ^ k / w > x]

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

    after y reaches 2^(biggest signicant bit in x)-1, then there will never be a x^y, that y will divide because y will always be larger than (x^y)/2. so we can count up to that, and then we can see that the rest of the numbers must be divisible by x, so we can check how many numbers are divisible in the range of [2^(biggest signicant bit in x),m]. there is an edge case where the last number in the range may not be achievable(because the y that is needed exceeds m), and that the first number outside of the range might be achievable(because the y that is needed actually might not exceed m), so you can just check those 2 edge cases, and thats it.

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

    My solution is $$$O(X)$$$ but relies on a fair bit of casework:

    1. For a fixed $$$x$$$, notice that for any value $$$r$$$, there is some $$$x \oplus y = r$$$ with $$$r - x \leq y \leq r + x$$$.

      • So we can count see if a valid $$$y$$$ exists for all $$$m - x \leq r \leq m + x$$$ in $$$O(x)$$$ time.
      • Then for any value $$$1 \leq r \lt m - x$$$, we can always select some $$$y \leq m$$$ which satisfies $$$x \oplus y = r$$$ where $$$r$$$ is divisible by $$$x$$$ (except for $$$r = x$$$, which requires $$$y = 0$$$ which isn't allowed) and the count is just $$$\lfloor \frac{m - x - 1}{x} \rfloor$$$.
      • and and just count valid $$$y \lt m - x$$$ . This accounts for all numbers divisible by $$$x$$$.

    2. Note that for numbers divisible by $$$y$$$, we require that $$$x \oplus y \geq 2 \cdot y$$$. Using $$$x \oplus y \leq x + y$$$ we get $$$x + y \geq 2 \cdot y$$$ or $$$y \leq x$$$.

      • So we can just iterate on all $$$y \leq min(x, m)$$$ in $$$O(x)$$$ time and add them if they haven't already been counted by the first iteration (i.e., skip any $$$r = x \oplus y$$$ where $$$x$$$ divides $$$r$$$ except for the case where $$$r = 0$$$).

    Code — 292947242

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

Why not allowing digit dp to pass C2? time complexity is 60*x*2, which would work if the sum of x on test cases was bounded by 10^6.

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

My solution to problem C2.

If $$$x \oplus y$$$ is divisible by $$$y$$$, then $$$y$$$ is less than $$$x$$$. Check it trivially.

If $$$x \oplus y$$$ is divisible by $$$x$$$, then $$$x \oplus y = x \cdot k$$$, hence $$$y = x \oplus (x \cdot k)$$$. We have a sequence of numbers $$$x \oplus (x \cdot k)$$$, all of them are divisible, but the sequence itself is not increasing. Assume, at first, that for $$$k \le \lfloor \frac{m}{x} \rfloor$$$ the constraint $$$x \oplus (x \cdot k) \le m$$$ is satisfied. Then iterate on segment $$$k \in [\lfloor \frac{m}{x} \rfloor - x \cdot 2, \lfloor \frac{m}{x} \rfloor + x \cdot 2]$$$ and check it there manually.

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

    Hello, could you explain why you have the segment [⌊m/x⌋−x*2, ⌊m/x⌋+x*2]

    → Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I solved C1 but and spent about 1 and a half hours on C2 but didn't get a single idea. Can someone provide hints?

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

    $$$y-x \le y \oplus x \le y+x$$$

    After this, we can come to some conclusions divide in cases.

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

      Can you please elaborate a bit, since the range is still too large??

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

        we can divide in two cases: $$$y \lt x$$$, $$$y \ge x$$$

        As we know, $$$x \oplus y \le x + y$$$ So if $$$x \oplus y$$$ is a multiple of $$$y$$$, then $$$y \le x$$$. Solving in the range $$$1$$$ to $$$min(x-1, m)$$$ is a loop (we don't need to count $$$y=x$$$ now.)

        We also know, from $$$x \oplus y \le x + y$$$, if $$$x \oplus y$$$ is a multiple of $$$x$$$, then $$$x \le y$$$.

        We need to count multiples of $$$x$$$ that can be written as $$$x \oplus y$$$ and $$$y\le m$$$

        Now using $$$x - y \le x \oplus y \le x+y$$$, we know all multiples of $$$x$$$ less than or equal to $$$m-x$$$ (There are floor $$$\frac{m-x}{x} + 1$$$ multiples) can be written as $$$x \oplus y$$$ for $$$y\le m$$$. Now we need to check for multiples within the range from $$$m-x+1$$$ to $$$m+x$$$. Then subtract 1 for $$$y=0$$$ 292996452

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

Why my approach failed for D ?

Let largest 3 values in set be a>b>c, res[1] = a, res[i] = b if i is prime, else res[i] = c. and handling m<3 with casework.

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

    You need more than 3.

    1
8 3
1 2 3

    Your code prints 3 2 2 1 2 1 2 1, but for the 4th and the 8th element, $$$gcd(4,8)=4$$$ and $$$gcd(a_4,a_8)=gcd(1,1)=1=a_4$$$ so it doesn't satisfy the requirement.

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

      I see, so you need to put decreasing values in each increasing multiples.

      UPD : AC!, thanks.

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

Tourist be like oh shit I am going to be LGM.lol

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I hate these contests filled with maths. Almost every ques was XOR or GCD

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

Solution Problem E here

https://oeis.org/search?q=1+2+5+19+102+682+5321&go=Search

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

    Can you please explain how you got to this solution? Did you brute force for small values and try to find the sequence?

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

      Bingo, because when I saw the statement, I knew that it is impossible, but a lot of people solved it, so I think I should use something like google search :))))))

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

How do you solve F1? I reduced it to finding the sum, over decreasing sequences of positive integers at most m where all prefix GCDs are different, of 2 to the power of (the length minus one), which I found can be encoded in a DP with O(mlog(m)) states (DP[m][x] represents this sum where the current prefix GCD is m and the last element is x) but I can't figure out how to transition fast enough.

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What is wrong here? In C2 i isolated all possible $$$y$$$ values into three groups, smaller, equal, or bigger than $$$x$$$. smaller equal is trivial, while for bigger than $$$x$$$ i claim that only $$$x$$$ can be the divisor, so i count all the multiples of $$$x$$$ which have an MSB which not higher than $$$m$$$'s msb and strictly higher than $$$x$$$'s MSB. Then i subtract all multiples that would result in a $$$y$$$ value which is bigger than $$$m$$$, by saying that for each such multiple, as its xor is with $$$x$$$ bigger than $$$m$$$ there is a prefix of bits where the xor of $$$x$$$ and this multiple is equal to $$$m$$$ in all bits but last, and in the last it is $$$1$$$ while $$$m$$$ is zero. so then i go over all prefixes of $$$m$$$, and if the prefix ends with zero, then i know what the prefix of the multiples that would result in an issue with this bit, and so i subtract the number of multiples of $$$x$$$ which have this prefix.

WA on pretest 2 https://mirror.codeforces.com/contest/2039/submission/292987386

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

Why put so many problem in a contest? C2 is much harder than D, and I wasted a lot of time on it. Please make the problem set in the right order.

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

    we should have both paid attention. C1 + C2 has more score than D.

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

    Please explain d

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

      a[i] is the biggest number in S where a[i] ≠ a[divisors of i],
      We can loop over S to get the largest possible number, since i <= 1e6, then the max number of different divisors of i is 240, then we can break the loop after at most 240 iterations not 1e18.

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

number theory forces

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

Can someone explain E? I see a lot of people posting about OEIS but I have never heard of this before. Can anyone explain?

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

    OEIS — Online Encyclopedia of Integer Sequences basically you put in the first 5-6 terms of a sequence and it gives you the formula or recurrence and literature

    However I don't understand people that solve problems that way.

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

How does checker of B implemented?

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

No offense, but one of the least enjoyable rounds to participate in a while

Nice A, pretty cool B, but here it all ends

??? C1? ????? C2? Guessed (with proving it only after submitting when checking for possible fst) both

Really cool idea for D, but once again guessable-and-i-still-have-no-idea-why-it-works. Combined with exactly same impression from C, barely leaves any enjoyment from solving it.

OEIS'ed problem E. This says all about it.

Problem F is really cool, but seeing "output modulo 998244353" right after OEISing E left me just desperate (even though later still had fun solving it and almost managed to debug it before the round end)

Not saying any problem in particular was bad, uninteresting etc. Any of them would be highly appreciated if it was a single such problem in round, but not when they are four (five, six?) consecutive math problems in the problemset

Nothing is bad with math itself, but when 3 consecutive problems involve divisibility and 2 next problems ask for something mod 998244353 it should probably tell you you should mix the problemset with non-math problems too =)

Anyways, thanks for the round and thanks for GM :)

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

    how do we OEIS this kind of problem. can you please detailed steps ? many people like me would be interested in learning.

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

    prob H is brilliant atleast

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

    I liked H, but I only went for H after skipping everything from E onwards because they looked tedious.

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

      Yeah, i didn't get to H so can't have opinion on it, but it seems like many people expressed their appreciation of problem H,

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

i need small help.can someone please just add 'LL' after '1' in the reverse for loop in this code. https://mirror.codeforces.com/contest/2039/submission/292987555 . sorry to ask, but i m travelling and i cant submit with phone. and i really want to know if my code works or not.

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

dang, I completely missed

It is guaranteed that the sum of x over all test cases does not exceed 107.

in C1, and solved it without this constraint

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

    Can you explain the approach?

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

      if (x^y) is a divisor of y, then y must be <=2*x. why? well because if y>2*x then lg(x)<lg(y), so __lg(x^y) == __lg(y) and then (x^y) can't be a divisor of y as 2*(x^y) > y.

      now that we know y can't be that large. Let's do a prime sieve loop up front of size 2M:

      for(int i=1;i<=2M;i++) for(int j=i+i;j<=2M;j+=i) //we know i is a divisor of j

      so there's O(2M log(2M)) value-divisor pairs total. For each one, we can let x=j, and (x^y)=i, implying y=i^j. (and similary for let y=j)

      and here, sort queries by x, then by m, now each value-divisor pair affects a continuous range of queries

      292967375

      → Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Bruteforce, which helps you find a solution to problem E on oeis

Code
→ Reply
»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Forgot to mod 998244353 in problem E and got FST :(

→ Reply
»
4 weeks ago, # |
← Rev. 2   Vote: I like it -26 Vote: I do not like it

sorry, I didn't know about alt account before.

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

Sorry for the rough feedback but I think this contest could have been better.

Problems C1, C2 and D were about, like, pattern recognition.
I solved each of them as follows:

  1. tried to think a little
  2. realized I can't get my thoughts in order
  3. wrote a brute-force for small inputs
  4. found a pattern in, like, 10 mins each.

So the editorial for C2 was very cool, but since the input size is so small (just 2 numbers), you could just try to bypass that thought process, like I did. I think it's counter-productive to have problems where you can just "oooh... just notice that you can there are never answers above 2 * x". Why is that? Nobody knows, but it works, so let's go.

Contrast that with, for example, a problem like 2036F - XORificator 3000 where you had to, like, manually do the counting. There was no sneaky way around at least doing some of the work. Also literally any other problem with inputs of at least 1 dimension (at least one array), however, in today's D, I spent 40 mins on unsuccessful thoughts and just found patterns in 10 mins by generating answers for arrays with slight changes, seeing how the answer is affected.

That's not to mention E, it is very sad when you can just do the bruteforce and input the result into OEIS. You could take it as an enforced rule during problemsetting, whenever you have 0-dimensional input (like 1 or 2 numbers), generate answers for small inputs and input them into OEIS. If you find something interesting, chances are many contestants will, too.

Till the next contest, I guess :)

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

it feels really bad to see number theory after number theory

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

How can we claim our prizes? Is it enough if we insert the TON wallet code in our profile or should we do something extra? Thank you!

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

293013531 vs 293013930

>POV: you're trying to squeeze in time limit

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

Any one has proof for A as to why printing odd numbers works.

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

    as $$$2k-1\equiv k-1 \pmod{k}$$$, the remainder would be $$$k-1$$$ for each $$$k=1,2,...n$$$, and the value of $$$k-1$$$ are all distinct among these values of $$$k$$$.

    → Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

YouKn0wWho's head is a picture with tourist, but u let him down from T xD

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

So prize when

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Great problem d

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

Please take a look at my submission and try to check what is wrong in the code, what test case it might be failing ?! Any help would be highly appreciated, trust me, it would really be!

https://mirror.codeforces.com/contest/2039/submission/293983985

→ Reply
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Will the prizes be sent with USDT, which might mean we should change a wallet, or it will be transfered into TON?

→ Reply
»
3 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Have anybody received ton? I haven't yet.

→ Reply