cry's blog

By cry, 6 weeks ago, In English

Welcome to Natlan, Codeforces!

sum, vgoofficial and I are like a dog with two tails to welcome you to participate in Codeforces Round 988 (Div. 3) at Nov/17/2024 17:35 (Moscow time). We have cooked up $$$7$$$ problems to be solved in $$$2$$$ hours and $$$15$$$ minutes.

The round will be hosted by rules of educational rounds (extended ICPC). Thus, solutions will be judged on preliminary tests during the round, and after the round, it will be a 12-hour phase of open hacks. After open hacks all accepted solutions will be rejudged on successful hacks.

Note that the penalty for each wrong submission in this round is 10 minutes. Also, note the rule restricting AI use!!! If you are caught using AI in an unorthodox manner, bad things will happen to you. We will be watching you all...

IMPORTANT!!! There is at least one interactive problem in the problemset. Please familiarize yourself with the guide for interactive problems beforehand.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participant of the third division, you must:

  • take part in at least five rated rounds (and solve at least one problem in each of them)
  • do not have a rating of 1900 or higher at any moment in time.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you (unless you register unrated).

We would like to orz the following individuals for making the contest possible:

UPD: Editorial!!!

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

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

Let's just pretend that Natlan didn't come out two months ago.

»
3 weeks ago, # |
  Vote: I like it +32 Vote: I do not like it

As a writer, I welcome you to Natlan with open arms

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

As a tester.... Visit a local Scientology center, attend a free seminar, or take a personality test and find out how Scientology can support you on your journey. Awaken your true self and step into a world of possibility — Your path to a better life starts here!!!

»
3 weeks ago, # |
  Vote: I like it +40 Vote: I do not like it

As a tester, I have been wondering who Natlan was.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it -38 Vote: I do not like it

    Natlan is a country of Pyro in Genshin Impact.

    Original text in Chinese 英语水平有限,中文原文如下:

    纳塔是《原神》里「火」的国度。

»
3 weeks ago, # |
  Vote: I like it +43 Vote: I do not like it

As a tester, I just learnt that this round is Genshin themed (I don't play Genshin)

»
3 weeks ago, # |
  Vote: I like it +26 Vote: I do not like it

As a tester, I recommend the round — it is excellent.

»
3 weeks ago, # |
  Vote: I like it +21 Vote: I do not like it

As a tester, I think this will be the best Div3 ever. Enjoy it!

»
3 weeks ago, # |
  Vote: I like it +25 Vote: I do not like it

tester As ! , love std::shuffle I a

fun also problems The were ! very

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

do not have a point of 1900 or higher in the rating.

Is it a typo?

»
3 weeks ago, # |
  Vote: I like it +29 Vote: I do not like it

As a tester, I need to google Natlan.

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

    sorry for this, but can you tell me that which cartoon that your pfp comes from? I was finding this for thoooooouuuuuussssaaaannnndddds years since I stop watching tv

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

As a tester, the problem are great. Have fun and good luck

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

    Hi Aditya, how can one become a tester at Codeforces?

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

      when someone you know becomes an author :-)

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

      Hey quater_nion, I just messaged Cry to give me any oppurtunity for testing or problem-setting if possible.

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

        Did you possess any prior experience, or this was your first time?

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

          I had done testing for 3 contests earlier, you can also ask wuhudsm for the same. Also you can test for TheForces Rounds too.

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

            Okay thanks! Would really love to contribute to CF uwu

»
3 weeks ago, # |
  Vote: I like it +26 Vote: I do not like it

As a VIP tester, I can guarantee you that the tasks are tasks.

»
3 weeks ago, # |
  Vote: I like it +37 Vote: I do not like it

As a tester: Genshin, Activate!

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

I think this is the coolest contest announcement I've seen recently.

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

as a genshin hater, I'm looking forward to hopefully gaining quite a lot of rate change in this contest

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

    so do i. when this disgusting awful gayshit die?

»
3 weeks ago, # |
  Vote: I like it -57 Vote: I do not like it

As a unofficial tester, I want contribution

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

Wish me all the best for the ICPC preliminary round! ^_^

»
3 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

Oh, its time crashs with my Ragional Contest of ICPC, Shanghai Station! I'm now in mihoyo's HQ, wishing every participants good luck and high rating! And wish me to win a medal :) By the way, Genshin? Launch!

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

Yayy, very excited for the next div 3!!

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

i hope this div3 doesn't have as trash testcases as the last one.

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

    ye, totally agree :)

    i still remember that i hacked myself :))))))

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

who ever play genshin impact is my friend ❤

»
3 weeks ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

As a genshin player, I hope this will be a good round.

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

I hope this round won't be as hard as the spiral abyss

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

The arrogation of mankind ends now.

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

wait for my release

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

genshin mentioned

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

As a participant, I would be like a dog with two tails to visit Natlan!

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

I love you for the Gwnshin reference❤️

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

please don't make us cry as of in this contest...:)

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

LET'S GO MAVUIKAAAAAAAAAA

I can't take it anymore. I'm sick of xiangling. I try to play dieluc. My xiangling deals more damage. I try to play yoimiya. My xiangling deals more damage. I try to play Hu tao. My xiangling deals more damage. I want to play Klee. Her best team has xiangling. I want to play raiden, childe. They both want xiangling.

She grabs me by the throat. I fish for her. I cook for her. I give her the catch. She isn't satisfied. I pull engulfing lightning. "I don't need this much er" She tells me. "Give me more field time." She grabs bennett and forces him to throw himself off enemies. "You just need to funnel me more. I can deal more damage with homa."

I can't pull for homa, I don't have enough primogems. She grabs my credit card. It declines. "Guess this is the end." She grabs gouba. She says "Gouba, get them." There is no hint of sadness in his eyes. Nothing but pure, no icd pyro application. What a cruel world

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

ZaDiv3

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

Genshin Impact, launch! :D

原神,启动!

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

well exactly we have a natlan contest before gta VI

»
3 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

The picture in the post brings back memories of the song "Close to the Sun" by TheFatRat. It takes me right back to high school days, when the line between passing time and wasting it was just a little blurrier.

Feel free to give it a listen if you're in the mood: https://www.youtube.com/watch?v=oJuGlqO85YI

Thanks for the nostalgia boost!

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

as a jenshin player, i hope this contest is not as hard as imaginary theater

»
3 weeks ago, # |
  Vote: I like it +33 Vote: I do not like it

I will eat shit if I can't become Expert after this contest.

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

YuanShen

»
3 weeks ago, # |
Rev. 2   Vote: I like it -44 Vote: I do not like it

It should be "at most one" interactive problem for any div3 or div4 contests. There is absolutely no value in learning these kind of problems for lower rated participants. It brings "joy" only for higher rated contestants who got bored at some point and invented a "new kind of fun". Do you think it's fun for newbies to solve these kind of problems? They have enough problems just to come up with any solutions at all :D

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

    They don't want to spoil the number of interactive problems, but rather the fact that it will be used so people who don't know how to solve them can look at the interactive guide. Hence the "at least one" statement was used.

    Even in Div 2/1 it's not super common to see 2 interactive problems in a problemset.

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

For the sake of NATLAN!

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

Wait, They used Natlan's landscape. As genshin traveler, what do you need else! So excited for the contest eeeeeeeeeee..... lol!

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

Quick question, why are people with rating higher than 1900 not “trusted participants of the third division”?

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

    Those people are likely to be too good to be in Div. 3, and could have intentionally pulled themselves down to the rated range to win the contest, if they were to be included in the official standings table.

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

      Hmm, so if you're too good for a division you're not allowed to be on the leaderboard. Interesting decision...

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

        Well, that's why we have rating bounds for each division in the first place...

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

      high rated people can make new id's and can win anyways.

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

        Making alts is strictly forbidden by the rules. Also, number of rated contests >= 5 condition is there so that they won't feel like spamming alts just to win low divisions.

»
2 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Announcement: Welcome to Natlan! Actual contest: Welcome to Khaenri'ah! Hope it won't be the cataclysm for my rating.

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

Tell me your UID of Genshin.

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

Good luck in the contest!!!

But, what is a VIP tester?

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

Cannot turn it down as a player of Genshin Impact

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

It is Guaranteed that there will be no more than $$$N$$$ interactive problems.

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

codeforces have Anti Smurf why valorant dont have ?

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

MikeMirzayanov for being MikeMirzayanov is wild ._.

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

Genshin is bad, i recommend that you need to touch grass after 3 years

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

    i recommend everyone who play genshin to touch grass immediately

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

      Yeah, like every coder try to AC some hard problems for 3 years and dont touch grass

      PS: My english skill is so bad

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

It's been almost a year since I started doing CP seriously. Now my rating is 1361, hope to become specialist in this one.

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

I think participating in genshin impact round feels like being "GAY"

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

Expecting gooooooood problemss in this contest as a newbie

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

If I didn't perform well , I'll touch the grass.

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

I just quit this game last month why exactly does the universe hate me.

»
2 weeks ago, # |
  Vote: I like it -16 Vote: I do not like it

i hate newbies

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

It turns out that you too

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

score distribution?

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

    There are no score distrbution for div 3, every question is worth the same.

»
2 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

eagerly waited for Such cool Div3 (as a newbie). thank you !!!

»
2 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

As a participant, I bet atleast one problem is about Mualani!

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

OOOH IT'S Genshin UwU sadly i won't be home to participate in the contest but i'm so excited to enter as a virtual contestant :3 Goodluck Everyone <3

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

"MikeMirzayanov for being MikeMirzayanov"

»
2 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

I have an exam tomorrow, should I study or hit expert ?

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

    I suggest study, cause you can hit expert next time, but you can't do your exam again.

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

    codeforces >>>>>>>>>>>>>>>> school

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

    U hit expert as u said. How was your exam? How do you practice CP, u r getting rating increase in almost every contest

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    deserved. u cheated during the div3 so u cant reach expert :)))

    HOORAY!! ANOTHER CHEATER CAUGHT :))))))

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

As Genshin Impact player, I am pleasantly surprised. It's too good to be true.

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

IF I DON'T RETURN THAT DAMNED SPECIALIST, I SHALL RETURN THE NEWBIE

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

Ohhh my god. Never did I imagine to genshin impact in Codeforces XD XD XD!!! Excited for today's contest!!!

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

Will I fall below 1200 or move to 1300+?

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

hoping for pupil this round

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

Well wishes to all

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

cry, please, don't make me cry after the contest.

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

go to expert and candidate master

»
2 weeks ago, # |
  Vote: I like it +82 Vote: I do not like it

»
2 weeks ago, # |
  Vote: I like it -7 Vote: I do not like it

why problem D is in russian i only know french arabic and english should i learn russian to gain rating points and solve the problem ??? i am trying my best each contest to get any point and you guys came with russian language

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

    Click the United Kingdom flag at the top to switch it to English (and if you want French or Arabic, I believe GPT translation is allowed, though I need to double check on that)

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

      no but first it appear that "problem statement is not available in english" i can send you the photo if you need

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

        That's odd, are you sure you are on the right problem (Sharky Surfing, or Акулий серфинг in russian)? A picture would be useful, thanks.

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

I hate interactive problems!

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

I enjoyed coming up with the solution for problem C :)

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

As a Chinese, I wonder who Superultra is. Is it a user name?

»
2 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Great E

»
2 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

this exactly what a div3 should be, great problems!

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

I thought that problem C was harder than D

anyway, ill finally get to pupil :D

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

    Personally, C was harder to notice the observation, but was really simple to write compared to D, which was an easy observation but more difficult to write

    Spoiler
    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I find that so interesting about codeforces contests. They are much more focused on the observation difficulty rather then "data structures/techniques" difficulty. Like sometimes I can't even solve Div 2B's (if it is a observation problem), when it seems that everyone here can, and on the other hand the same ppl dont know basics about heaps, graphs, segtrees, etc.

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

        That's what I like about codeforces, the questions (for the most part) aren't "do you know this random theorem or this random data structure", but require more thinking. Sure, there will be some insanely standard questions (such as Ruler — easy version or A good string) that require little thinking outside of knowing an algorithm, but for the most part, the questions are unique and fun to solve.

        Only annoying part about that is difficulty feels a bit inconsistent, I'll be able to look at a 1400 and solve it immediately then struggle on a 1200 / 1300, but that's just how it is.

        • »
          »
          »
          »
          »
          2 weeks ago, # ^ |
          Rev. 3   Vote: I like it +3 Vote: I do not like it

          Yeah codeforces its really good to train logical thinking But well, we can't deny the random theorems and data structures bc thats what ICPC contests ask for unfortunately :/

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

D solution Please

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

    store the power ups as you traverse, when a power boost is required use the biggest of the them.

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

    For each time we pick up an item, we definitely greedily select the one that provides the greatest improvement to our abilities among the items we can take but haven't yet collected.

    Therefore, we can use a heap to manage the items. We enumerate each obstacle, add all the items available before that obstacle to the heap, and then take items from the heap until we can jump over the obstacle.

    The code:

    #define l first
    #define r second
    
    #define ft first
    #define sd second
    
    void solve()
    {
        int n, m, L;
        cin >> n >> m >> L;
        vector<pair<int, int>> a(n + 1);
        for (int i = 1; i <= n; i++)
        {
            cin >> a[i].l >> a[i].r;
        }
        vector<pair<int, int>> b(m + 1);
        int ans = -1;
        for (int i = 1; i <= m; i++)
        {
            cin >> b[i].ft >> b[i].sd;
        }
        ll val = 1;
        int cnt = 0;
        int j = 1;
        priority_queue<int> q;
        for (int i = 1; i <= n; i++)
        {
            while (j <= m && b[j].ft < a[i].l)
            {
                q.push(b[j].sd);
                j++;
            }
            while (q.size() && val < a[i].r - a[i].l + 2)
            {
                val += q.top();
                cnt++;
                q.pop();
            }
            if (val < a[i].r - a[i].l + 2)
            {
                cout << "-1\n";
                return;
            }
        }
        cout << cnt << "\n";
    }
    
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to do D?

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

    priority queue to save the power-ups u haven't use, when the hurdle ahead, if your power is not enough, pop the top of queue and add it into your power.

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

    For each time we pick up an item, we definitely greedily select the one that provides the greatest improvement to our abilities among the items we can take but haven't yet collected.

    Therefore, we can use a heap to manage the items. We enumerate each obstacle, add all the items available before that obstacle to the heap, and then take items from the heap until we can jump over the obstacle.

    The code:

    #define l first
    #define r second
    
    #define ft first
    #define sd second
    
    void solve()
    {
        int n, m, L;
        cin >> n >> m >> L;
        vector<pair<int, int>> a(n + 1);
        for (int i = 1; i <= n; i++)
        {
            cin >> a[i].l >> a[i].r;
        }
        vector<pair<int, int>> b(m + 1);
        int ans = -1;
        for (int i = 1; i <= m; i++)
        {
            cin >> b[i].ft >> b[i].sd;
        }
        ll val = 1;
        int cnt = 0;
        int j = 1;
        priority_queue<int> q;
        for (int i = 1; i <= n; i++)
        {
            while (j <= m && b[j].ft < a[i].l)
            {
                q.push(b[j].sd);
                j++;
            }
            while (q.size() && val < a[i].r - a[i].l + 2)
            {
                val += q.top();
                cnt++;
                q.pop();
            }
            if (val < a[i].r - a[i].l + 2)
            {
                cout << "-1\n";
                return;
            }
        }
        cout << cnt << "\n";
    }
    
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

why interactive in div 3 :(

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

tourist wtf?? How does one complete problem E in 1 min??

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

I think it was a nice set of problems. I struggled in trying to figure out where I was going wrong with E ... genuinely losing my mind. I don't think there's a problem with my idea/proof, but just maybe something small in the implementation... :(

UPD: Well, since the editorial is posted, I suppose I might as well explain my thinking for E:

  • IMPOSSIBLE if and only if there exists no "01" substring, which is equal to querying the entire string and getting an answer of 0.

  • Otherwise, there is some "01", and we start querying all the prefixes [1, 2], [1, 3] ... [1, n]. Suppose the first one to give a non-zero answer is [1, i]. Let that answer be R. Then, since all prefixes before [1, i] gave 0 as an answer, the string over [0, i-1] is i-1-R 1's followed by R 0's. Also s[i] must be 1. To determine the suffix s[i+1, n], we query over the prefixes still [1, i+1], [1, i+2] ... [1, n], and, at each query, if the answer increases from the previous one, we have a 1 there, otherwise it is 0 there. In total, we take exactly 1 query for each char in s[2, n], meaning we require n-1 queries.

Does anyone know if there is something wrong here?

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

    i think it's correct

    UPD: i think your implementation should have used long long. you took input as an integer, which can overflow and made the condition (r1 > prev) false.

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

      No, I redefined int to be long long. The issue was actually that "interQuery" function returned a god damn char instead of int by accident. :(((

      (Also the biggest number to be dealt with in this problem is on the order of (10^4)^2 = 10^8, so there is actually no need for long long anyways).

»
2 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

anyone who solved last problem, please teach me new things

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

In problem D, after the problem statement changed, still wrong. Or am I high?

In the second test case, she cannot jump over the first hurdle.

Actually it's the third hurdle that she cannot jump... I debugged my code for this.

UPD: Now I noticed she also cannot jump over the first hurdle, I'm actually high.

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

how to optimize G my solution is $$$O(n * k ^ 2)$$$
where $$$k$$$ is max no. of factors

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

    Use inclusion exclusion

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

      my is inclusion exclusion

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

      omg I just hear about it last month, but rarely face it and meet it today, can you explain more

      • »
        »
        »
        »
        2 weeks ago, # ^ |
        Rev. 3   Vote: I like it +1 Vote: I do not like it

        You need to calculate $$$\sum_{d|u}dp[d]$$$, and you can compute the prime factors of $$$u$$$ as $$$P=[p_1, p_2, \dots, p_n]$$$. Then we have $$$\sum_{d|u}dp[d]=\sum_{S\subset P}(-1)^{|S|+1}\sum_{p\in S}dp[p]$$$.

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

it's silly G was ChatGPT solvable, I'd review all submission of G among rated participant if I were coordinator.

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

As a participant, I got trouble understanding E

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

Somebody hack my solution for B. If k - 2 is a perfect square and its root is x, we should check if we have 2 x's in the multiset right? I did not do that.

Like example [2, 1, 1, 1, 1, 1] my solution outputs 2 2.

Submission

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

    That is not a valid input. It is guaranteed a solution (n,m) exists

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

    The example you gave is invalid because there is no answer possible.

    Why it works? x*x = k^2

    The sequence has only 1 x. This means there are two integers y and z such that y*z = k and y<z.

    Sinze x*x = k, therefore y<x and will be iterated over earlier than x and you'd already found the answer then.

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

Hello!

Can anyone help me with the idleness limit exceeded on this submission for question E

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

    did you flush your answer?

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

      Ahh thanks I wasn't aware that we had to flush our outputs as well

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

    You have to flush after printing the answer as well IMO

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

Hey! Can somebody clarify this? I've got 2 questions accepted with a penalty of 36, yet I saw that I'm ranked below those with much more penalty and only 1 question solved, when I went through the standings list. Why is it so??

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

    The standings list remains pretty messed up until the final standings are published after system testing. It'll be fixed in a while.

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

      Alright

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

      Final standings are here, but the issue is still there. Something is definitely messed up with the standings chart. Pretty pissed off at this moment, didn't expect this kind of mess-up.

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

Can anyone please explain G in simple terms. thank you :)

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

Is tourist for real? y'all sure he is not an AI?

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

    AI isn't that accurate yet :P

    Also, you sure are HUMAN? Because no real human would need to scream that in their username.

»
2 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

I enjoyed this contest :)

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

In problem D, shouldn't first test case be false instead of true? Need to jump from li-1 to ri+1 that is ri — li + 2. But the total power up that can be collected is 8 for the first hurdle and it is less than 9 that needed to be jumped from 6 15.

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

    You start with 1 power.

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

    Total power initially is 1 so after collecting the power boosts it will be 9, therefore it will pass the hurdle.

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

Inconsistent output for 2037 B. Intercepted Inputs https://codeforces.net/contest/2037/submission/292083626 Test case 1: 2 1 4 5 3 3 my output is shown as 2 2 but when I run it else anywhere (online and my machine) its giving 1 4. Can anyone help me understand what is going wrong here?

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

    undefined behaviour bc of the custom hash? dunno

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

    Note that the for-loop order of an ump is an implementation-based behavior. You shouldn't seperate calculating answer from building the ump.

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

292066305 siliconrhino chatgpt obviously,this guy solve e,f,g in 10 minutes. get him get him :P

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

The G problem has an original problem, which is Problem J from the 2022 ICPC Guangxi Provincial Contest. You just need to modify the modulus and the range, and you can submit it directly to pass.
Link: https://pintia.cn/market/item/1541299013331705856

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

    I can't access the link. Can you send an image?

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

      The organizer of this ICPC contest is Hangzhou Dianzi University. Maybe yuo can find more info there.

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

        Thanks, good to know. We would never have found it on our own D:

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

        Oops... Assured this is a coincidence. We ran it through the yuantiji AI and no tester has reported seeing that problem before. Since its a rather obscure link I think luckily this coincidence did not affect the rankings much.

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

          With CP having existed for so many years and millions of problems arising, this will inevitably happen.

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

Genshin Impact, Activate!

»
2 weeks ago, # |
Rev. 2   Vote: I like it +11 Vote: I do not like it

as a mualani main, D was cool but i couldn't surf through natlan and nice contest

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

Has rating changes been rolled out?

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

Man they didn't put Mauvika in :(

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

I am not getting why i am getting a wrong answer on this code.. Problem D__ https://codeforces.net/contest/2037/submission/292074400

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

    I have skill issue and could not read your code lmao, but the most sussy part I see is the "cnt++;" in the part "...b += val; cnt++; while...". Other cnt-- and cnt++ line all have good condition check.

    "exp_ected: '2', found: '3'" at 2044th answer, must be related to an edge case where an extra cnt++ were not supposed to be called was called.

    The "cnt--" call have a condition check that looked like my code so I think the problem is not on that part.

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

      For every hurdle i just checked whats the minimum number of jump boosters i need to take .. for that i took a set where i stored the power ups taken after the last hurdle to the initial hurdle i am on ... And a priority queue where i stored the power ups i didn't take from the beginning to the current hurdle i need to pass. My tar for every hurdle is the amount of jump power i need — sum(the jump power i have).. when my tar becomes less than 0 i check how many power ups i could initially not take that is in the set that's why cnt--.. after taking all the power ups before a certain hurdle if my tar is greater than 0 then i just take the power ups in the priority queue untill my tar becomes less than 0 and do cnt++.. if it cant then i do flag =1 and print -1 later on.

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

wc,yuan

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

Thank you very much for the contest. Really loved participating in the round.

»
2 weeks ago, # |
Rev. 2   Vote: I like it +15 Vote: I do not like it

Where is Editorial ?

can't find
»
2 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Why is the Editorial!!! not allowed to view.

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

Can someone explain why i get idleness limit exceeded, this is not new, almost for every interactive problems. I tried deleting fast io, endl, \n, also in this code i make assertion. How it could be possible: my code

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

    Because you are asking queries 2 * (n - 2) + 2 times and you can at most ask n queries. I wonder how you reached the expert rating 3 times even if you can't figure out this simple thing.

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

      But im not wondering why you are still a newbie with that much problems, 2 * (n — 2) + 2??? Are you kidding?

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

        My bad. You are asking queries n + 1 times. i.e., 1st queries in the beginning, then n - 2 queries in the for loop, and lastly, 2 queries when i == n - 2.

        And I am sorry for doubting you!

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

          I am also, but i make 1 query before start, then i make n — 3 queries from i = 1 to i = n — 3, then i is n — 2 and i make 2 queries, total is n. Also, i know my solution is probably wrong but im not on it.

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

            I figured out your problem! Yes, you are asking at most n queries. But you are not printing the answer for n = 2. Consider the below test case,

            Input:
            1
            2
            01
            Answer:
            1
            Your Output:
            !
            

            Your code is not going into the for loop, for (i = 1; i < N - 1; i++). Because N - 1 = 1 for N = 2. Hence not printing the answer instead of printing 1. That's why it says the Idleness limit is exceeded.

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

              Thanks, really.

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

Why my participation was unrated, I thought my rating would increase :) (I did join after the round started, maybe this is why?)

»
2 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

Why when I try to view the Editorial, it says 'You are not allowed to view the requested page'?

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

Can someone please explain the binary search approach for D ?

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

    There is a binary search approach for D?

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

    lets say you have {1,4,5} power ups and you need 5 more to jump and you can use binary search to pick the greater one like greedily
    I tried it using lower bound but I guess using priority queue lessens the work detailed —

    power ups pos val 1 1 (pick) 2 4 (pick) array of power ups — {1,4} hurdle L R 3 6 (needed = 6-3+1 = 4) and 1 additional to cross it so total 5

    now initial jump_power = 1 now since hurdle came at pos = 3 so binary search the power ups array for maximum value, we got 4 which make jump_power = 5 and erase 4 from it since 5 is the needed, so add 1 to answer and do the same for the rest (this is my intuition when I was solving yesterday, correct me please if I am wrong)

»
2 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Looks like the editorial has been taken down. Please fix cry

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

Hi, can someone pls help me?

my rank in standing page says 1594 as rank, but on my profile, the rank of the contest says, 1905. Can someone help me understand why two different ranks?

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

    This part in the announcement explains it:

    "Remember that only the trusted participants of the third division will be included in the official standings table."

    "Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you (unless you register unrated)."

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

For D i don't get where this logic is wrong? For every hurdle i just checked whats the minimum number of jump boosters i need to take .. for that i took a set where i stored the power ups taken after the last hurdle to the initial hurdle i am on ... And a priority queue where i stored the power ups i didn't take from the beginning to the current hurdle i need to pass. My tar for every hurdle is the amount of jump power i need — sum(the jump power i have).. when my tar becomes less than 0 i check how many power ups i could initially not take that is in the set that's why cnt--.. after taking all the power ups before a certain hurdle if my tar is greater than 0 then i just take the power ups in the priority queue untill my tar becomes less than 0 and do cnt++.. if it cant then i do flag =1 and print -1 later on. Heres my code https://codeforces.net/contest/2037/submission/292074400

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

    You should pick power-ups from high to low, not low to high

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

      I picked from high to low .. can you please give a test case where this code wont work

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

        Doesn't st.begin() return the minimum value?

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

          I am deleting this minimum value .. from my taken power ups when my target is less than 0.. so ultimately i am choosing from high to low

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

I placed 4000 and I got 43 point as a newbie wow is this real ?

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

why is editorial not available?

»
2 weeks ago, # |
  Vote: I like it +44 Vote: I do not like it

»
2 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem G. I have written this code after reading about sieve, inclusion-exclusion principle. But somehow it is giving wrong answer on test case 5. Can someone help me with this one?

const int maxn = 1e6+1;
const ll mod = 998244353;
bitset<maxn>sieve;
vector<vector<int>> factors(maxn);
void generateSieve() {
	// sieve[i] = 0 => i is prime
	int i, j;
	sieve[0] = sieve[1] = 1;
	for(i = 2; i * i < maxn; i++) {
		for(j = 2*i; !sieve[i] && j < maxn; j += i) {
			sieve[j] = 1;
			factors[j].push_back(i);
		}
	}
	factors[2].push_back(2);
	for(i = 3; i < maxn; i += 2) {
		if(!sieve[i]) {
			factors[i].push_back(i);
		}
	}
}


void solve() {
        generateSieve();
	int n;
	cin>>n;

	vector<int> arr(n);
	cin>>arr;

	vector<long long> s(maxn);
	vector<long long> dp(n);
	dp[0] = 1;

	for(int i=0;i<n;i++){
		int m = factors[arr[i]].size();

		for(int mask = 1; mask < (1<<m); mask++){
			int c = 0;ll mult = 1;
			for(int j=0;j<m;j++){
				if((mask>>j)&1){
					c++;
					mult*=factors[arr[i]][j];
				}
			}
			if(c&1) dp[i] = (dp[i] + s[mult])%mod;
			else dp[i] = (dp[i] - s[mult] + mod)%mod;
		}

		for(int mask = 1; mask < (1<<m); mask++){
			ll mult = 1;
			for(int j=0;j<m;j++){
				if((mask>>j)&1){
					mult*=factors[arr[i]][j];
				}
			}
			s[mult]=(s[mult] + dp[i])%mod;
		}
	}

	cout<<dp[n-1]<<endl;
}

I am failing on test case 5 with wrong answer. Is there some problem while including/excluding cases or the mod operation? It's a new topic I implemented first time.

Also, any improvements would be really helpful for sieve and this type of questions. Thanks in advance!

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

Can someone clarify D for me , suppose i collect power ups that sum to 10 but i made a jump of length 5 then will the 5 remaining power up stay with me for the next hurdles or will it come down to zero ?

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

    they will stay with you and won't reduce if there will be 10 they wont reduce to 5 they will remain 10

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

      They should have clarified , I am not saying that i would have solved it in contest if they had mentioned it . But the standard video game logic dictates that you loose power ups after you have used them

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

        Yeah same thing i thought then i dry ran some of the test cases and it got clear

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

https://codeforces.net/contest/2037/submission/292167168

can anyone help me with this please I do not know why this is failing I know I could have went directly in my approach instead of going this way and solved the other way too but still I want to debug this if anyone could help me with this please question — D

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

code giving correct answer in code editor but codeforces judge giving this error :wrong answer Integer parameter [name=r] equals to 5, violates the range [6, 5] (test case 1) can you some tell why this happening ~~~~~ void solve() { int n; cin >> n;

auto ask = [&](int l, int r)
{
    int x;
    cout << "? " << l << " " << r << endl;
    cin >> x;
    return x;
};
string ans = "";
int value = ask(1, n);

if (!value)
{
    cout << "! " << "IMPOSSIBLE" << endl;
    return;
}
else
{
    int l = 2;

    while (l <= n)
    {
        int x = ask(l, n);

        if (x == value)
            ans += '1';
        else
            ans += '0';

        value = x;
        if (!x)
            break;
        l++;
    }

    for (int j = l; j <= n; j++)
    {
        ans += '1';
    }

    cout << "! " << ans << endl;
    return;
}

}

int main() { int t; cin >> t; while (t--) { solve(); } return 0; } ~~~~~

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

Hi for me this contest went unrated even though i registered before the contest started. Any reason why this might have happened?

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

Message:

"Attention! Your solution 292032737 for the problem 2037C significantly coincides with solutions asikM/292032737, CheatPlusPlus14/292049353. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.net/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked."

I have got this message around 20 minutes ago. By mistake i have pushed my solution of this contest problems on my public Github repository (Github Link:- https://github.com/Asik8/My-Codeforces/tree/main) during the contest was running on 17th November 2024. Which was a wrong step for me. Someone managed to collect the code and change it in the python Language and submitted it. This is the prove i have that i have solve this problem on my own. I don't know what i should do. According to the Given message i have to post a comment on this round post I have already provided the explaination. Evidence:

  1. Github Repository Link: https://github.com/Asik8/My-Codeforces/tree/main
  2. Solution Of problem A: https://github.com/Asik8/My-Codeforces/blob/main/A_Twice.cpp
  3. Solution Of problem B: https://github.com/Asik8/My-Codeforces/blob/main/B_Intercepted_Inputs.cpp
  4. Solution Of problem C: https://github.com/Asik8/My-Codeforces/blob/main/C_Superultra_s_Favorite_Permutation.cpp

Now all my solutions got skipped. Can it be fixed?

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

I got flagged!! I use Programiz online compiler too and for the recent div 3 round 988 my solutions got skipped. I didn't know the rules regarding this, pls give my ratings back and pls don't block my account. I saw this msg recently and have done accordingly, what should i do next? pls help

»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

As a Programmer, I have been Asking who is Natlan.