cry's blog

Codeforces Round 952 (Div. 4)
By cry, 9 months ago, In English

Hellowo Codeforcers :3

sum and I are very delighted, ecstatic, enchanted, euphoric, excited, exultant, jubilant, overjoyed, and proud to invite you to participate in Codeforces Round 952 (Div. 4), which will start on Jun/11/2024 17:35 (Moscow time). There will be $$$8$$$ problems, with one split into two subtasks, to be solved in $$$2.5$$$ hours.

As usual, I have to copy and paste the following...

The format of the event will be identical to Div. 3 rounds:

  • 5-8 tasks;
  • ICPC rules with a penalty of 10 minutes for an incorrect submission;
  • 12-hour phase of open hacks after the end of the round (hacks do not give additional points)
  • after the end of the open hacking phase, all solutions will be tested on the updated set of tests, and the ratings recalculated
  • by default, only "trusted" participants are shown in the results table (but the rating will be recalculated for all with initial ratings less than 1400 or you are an unrated participant/newcomer).

We urge participants whose rating is 1400+ not to register new accounts for the purpose of narcissism but to take part unofficially. Please do not spoil the contest for the official participants.

Only trusted participants of the fourth division will be included in the official standings table. This is a forced measure for combating unsporting behavior. To qualify as a trusted participant of the fourth 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 point of 1400 or higher in the rating.

Regardless of whether you are a trusted participant of the fourth division or not, if your rating is less than 1400 (or you are a newcomer/unrated), then the round will be rated for you.

We want to express overwhelming gratitude to the following individuals for making the contest possible:

Vladosiya and mesanu for coordinating the contest and reviewing the problems.

Dominater069, omeganot, Phi-001, flamestorm, nskybytskyi, willy108, ScarletS, mark, yuan-shen, vgoofficial, htetgm, buffering, yash_9a3b, haochenkang, ETL, natalina, MatthewC3297, and lcsc0 for testing the round.

MikeMirzayanov for the usual.

We suggest reading all of the problems as we have put mucho effort into all of them. Best of luck, mis amigos!

UPD: Editorial

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

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

Auto comment: topic has been updated by cry (previous revision, new revision, compare).

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

orz

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

As someone who loves newbies, I hope this contest helps your rating!

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

My planned post-contest discussion stream

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

Published 2 months ago! :O

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

We urge participants whose rating is 1400+ not to register new accounts for the purpose of narcissism but to take part unofficially.

Aye aye captain!

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

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

    Now i need to wait for the next Div. 4

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

The round feels more solid with sum and cry as problem setters! :)

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

uwu :3

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

Woah!! Another Div 4 Round again... Let's Go!And gain some ratings!

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

The best part of testing was the brotherly camaraderie I shared with vgoofficial.

Thanks to my friends cry and sum for setting the contest. It will be fun for any Div 2 competitors, so even if you are out of contest you should give it a try!

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

Will try to solve this round in rainboy style :)

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

Dear USACO Bronze Participants,

I write to offer my sincerest apologies for the unexpected challenge presented by Problems 1 and 3 in the recent USACO Bronze contest. It appears my attempt to craft engaging problems inadvertently led us down a rabbit hole more labyrinthine than anticipated.

Upon reflection, I understand how frustrating it must have been to encounter such formidable obstacles, akin to stumbling upon a hidden boss level in a seemingly straightforward game. Rest assured, it was never my intention to transform the contest into a virtual odyssey fraught with unforeseen perils.

As the architect of these challenges, I take full responsibility for their unintended complexity and any resulting vexation. Please know that I am committed to rectifying this misstep and ensuring future problems maintain a balance of accessibility and intrigue. Your feedback is invaluable in guiding this endeavor, so please continue sharing your thoughts and experiences.

In the meantime, I hope you'll accept my heartfelt apologies and know that your perseverance in the face of adversity is truly commendable. Together, let's navigate this coding journey with determination and resilience, knowing that each challenge only strengthens our skills and camaraderie.

With sincere regret and gratitude, cry

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

gotchu i will do my best even though im too highly rated

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

Last round, Div4 has just celebrated its 4th birthday, and it looks like we'll be saying goodbye to the SlavicG flamestorm mesanu era, meeting more and more interesting questions. Thanks all of you! :D

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

cry orz

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

sto orz (just two cats about to fight)

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

why is cry crying (crying emojis)

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

Ladies and gentlemen, finally I can say what I've always wanted to say at Div. 4 rounds announcements: My first unrated contest :^)

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

Div-4 is Mental satisfaction for Newbies

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

Hope this contest will be perfect div 4 contest and Codeforce website won't be down or lagg AND thanks sum****

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

My first unrated contest , yay!

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

What if those whose rating is >= 1400 are restricted from registration? As we have seen this restriction in Div-1 contests. Then the submission queue and system testing will be smooth, I think. And you know, after the contest anyone can make submissions!

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

Every greeting synonyms of this blog could be the problem title of the whole Dashboard to make it more interesting!!!

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

Hopefully, I will make a comeback to reach CYAN after this round, insha-Allah.

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

very delighted, ecstatic, enchanted, euphoric, excited, exultant, jubilant, overjoyed, and proud

lol

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

I am gonna reach Pupil at this contest!!

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

    Best of luck! I hope you do great

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

      thanks you! I hope we both will reach Pupil

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

        what if we reach pupil than what there is nothing we get after reaching out there .

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

create 2 new problems and make a div 3 also.

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

New faces at Div.4? Hehe, time to do a clean AK for appreciation's sake. Congrats on your first Div.4 round!

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

As an unrated contestant i hope to solve the problems

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

Looks like the problems will be named

A.delighted

B.ecstatic

C.enchanted

D.euphoric

E.excited

F.exultant

G.jubilant

H.overjoyed,

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

can i be rated ? i want to be rated because my rated is so ....

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

The best writer...

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

I registered when I was an Specialist. It still shows asterik(*) next to my name. Will this be rated for me?

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

the frequence of div4 is really low,i sincerely hope all the trusted participants good luck, hope this will help u get rating

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

Most casual announcement ever.

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

What is the penalty of resubmission in this round?

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

I hope someday division 4 won't be rated for me ...

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

Hey, just a request.. during such rounds the servers can not take the loads ig and that happens to the mirror websites as well sometimes. Please take a look into that

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

Excited for Codeforces Round 952 (Div. 4)! Best of luck to all participants—let's solve some great problems and learn together!

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

Hoping to perform better after 2 poor performances .

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

hope my rating>0

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

Is the Div4 the easiest competition game in CodeForce?

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

    no its hardest game ever on CF . God of CF also afraid to solve these div 4 problems

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

hopefully i can participate in a div4 soon!

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

let's go!!good luck everyone

→ Reply
»
6 months ago, # |
  Vote: I like it -7 Vote: I do not like it
11003 users be like:
→ Reply
»
6 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I am gonna get a better rank than you !!! (Challenge me!!!)

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

In recent times, cheating is significantly increased and we the Newbies are suffering a lot :) It becomes harder to Newbies to increase ratings because of these cheaters.

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

Div 4 is like a Major Event to Us (Newbies). We eagerly wait for this round :D

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

I am delighted, ecstatic, enchanted, euphoric, excited, exultant, jubilant, overjoyed, and proud to participate in this round.

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

Well, this won't be rated for me, Good Luck to everyone

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

Hopefully my last rated Div. 4. Goodluck to everyone!

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

    By seeing your submissions ,i think you are cooked.

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

      Yeah I fucked up big time. Solved G literally 5 seconds after contest ended and apparently F got hacked. Unlucky.

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

        Damn if you solved G that means you will reach specialist in the very next DIV2

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

Hope to get positive delta

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

Hellowo :3

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

:)

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

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

Good luck to everyone! I'm old and slow but if I don't solve at least ABC I'm going to tilt kek.

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

Hope to reach pupil, also good luck to everyone!

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

All the best guys :))

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

I hope I will get some point. UwU

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

Vai Kalke semistar final ☹️(Bangla)

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

what do these lines means? "ICPC rules + 12-hour open hacking phase.** Untrusted participants are not included in the official rank list."1.

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

    ICPC rules = after every wrong submission that's on testcase 2 or more, +10 minutes in penalty.

    12-hour open hacking phase = people have 12 hours to generate testcases to try and make anyone's code get WA, TLE, RE, etc.

    Untrusted participants = people who haven't yet participated in 5 rated rounds.

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

    nothing

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

My submission for problem D has been in queue for quite a while(>10 mins I believe). What should I do? Should I consider resubmitting?

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

    The problems are easy so we get lots of submissions, queue will decrease soon, just wait.

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

Div 5

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

    It's called "solvable for rated participants"

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

ABCD, I'll take it.

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

geometryforces... and negativedeltaforces for me :(

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

    where did you see geometry?

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

      D and E. To be fair D was just a simple observation- choose the row with the most number of '#'. But I just wanted to comment geometryforces for the fun of it :)

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

        Woah, nice stuff for D. I solved D the lazy way and take the mean value of all x-coordinates and y-coordinates of # cells. XD

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

          Oh wow, my old and slow brain convoluted this one way more than needed ... I found the first row with a single #, call it r1, then the other row with a single one (if it exists), call it r2, then center row is (r1 + r2) / 2, and center column is just the column with the single #. Row with just the most number of # would indeed be MUCH simpler and quicker heh, nice!

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

          Wow, taking mean is an interesting observation. liked it! It might come in handy for some other problems, but maybe a bit of overkill for this problem. Anyways, I observed the first row where I get a '#', and I know that this is going to be the column of the center. For the later rows, I only checked if this column has a '#' in it. The center's row is the average of last such row and the first row.

          bool lookfst = true;
ffr(i, 0, n){
    cin >> s;
    if(lookfst){
        ffr(j, 0, m){
            if(s[j] == '#'){
                k = j;
                lookfst = false;
                h1 = i;
                break;
            }
        }
    }
    else{
        if(s[k] == '#') h2 = i;
    }
}
if(h2 == -1) h2 = h1;
cout << ( (h2 + h1) / 2) + 1 << ' ' << k + 1 << '\n'
          → Reply
        • »
          »
          »
          »
          »
          6 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Can you explain to me why this method works? Thank you!

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

            It's easy to see that a Manhattan circle is centrally symmetric at its center — that is, if a circle is centered at $$$(h, k)$$$ and there exists a point $$$(x_1, y_1)$$$ in the circle, then there will always be another point $$$(x_2, y_2)$$$ also within the circle such as $$$\frac{x_1 + x_2}{2} = h$$$ and $$$\frac{y_1 + y_2}{2} = k$$$.

            We can keep discarding those pairs of points while calculating the average (coz' if a point has positive difference at x-coordinate from the center, its symmetric point will throw back at it with the same-margin negative difference, discarding themselves — and the same goes with y-coordinate as well). Eventually, there will only be the circle left, making it by default the average value of the x/y-coordinates over all points of that circle.

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

What is the approach in G (definitely not digit DP with such a big k, right)?

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

    $$$k > 9$$$ means instant $$$0$$$. For $$$k \le 9$$$, denote $$$n = (\lfloor \frac{9}{k} \rfloor + 1)$$$, $$$ans = n^r - n^l$$$.

    UPD: I made a terrible drunken mistake at first revision of this comment. Fixed now.

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

    Try to brute force the valid $$$n$$$ and see what does it look. It is pretty trivial after you see the pattern.

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

    By running simple examples, you can understand that this equality is satisfied only if there are no carries during multiplication.

    For example, for k = 3, only the digits 0, 1, 2, 3 (amount = 4) are suitable to appear in any number, for k = 2, only the numbers 0, 1, 2, 3, 4 are suitable, amount = 5 for k = 7, only the numbers 0, 1 are suitable, amount = 2

    Well, calculate amount ** r – amount ** l (of course with using mod and fast pow)

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

    you can actually get solution's close form. Assume N = number of valid digits (if multiplied by k <= 9)

    Then, res = ((N-1) * (N^l + N^(l+1) + ... + N^(r-1))) % MOD

    You can use geometric mean to compute

    (N^l + N^(l+1) + ... + N^(r-1) = (1 + N + .. + N^(r-1)) — (1 + N + .. + N^(l-1)).

    Then use mod inverse to handle substraction

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

How to solve C?

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

    If a number in the list is the sum of all other numbers, then it is the maximal number in the whole list.

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

      Ohh!

      Got it. Thank you for sharing the insights. Appreciated.

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

    Suppose you have an array a1, a2, ..., an. You need to choose n-1 elements in such a way so that their sum is equal to the not chosen element. But because all elements are non-negative, the only way for that to happen is if the not chosen element is maximum.

    Therefore you can keep track for each prefix two things: the current prefix sum, and the maximum element in that prefix. The prefix is good if sum — maximum = maximum.

    My submission: 265313130

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

any counter example for problem E , submission

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

Can anyone please help me with my solution for H1, it gives runtime error on test 5. 265363442 Thanks for your time.

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

    From my "investigation", Exit code is -1073741571 means stack overflow

    And the culprit is the dfs function with too many parameters. Maybe you should try reducing the number of parameters by using some global variables, and see if it works

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

how do you do G? and is H1 related to graphs or can we do it without it

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

    H1&H2 is floodfill, a common graph algo

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

      H1 can be solved using DSU

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

        I dont know DSU

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

          really ?

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

            yeah. You can reach purple without knowing DSU.If you are really good at DFS/BFS/floodfill and common DPs on graphs.

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

              How did you get so good by just solving around 300 problems ,or do you practice at some other platform?

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

                I did USACO prior (got to silver)

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

                  plus many years of math competitions.

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

                  So you practiced their training problems?

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

                  why our F is hacked, please help what was wrong with the code?

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

      i see, then i would not be able to solve it

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

      Explain your solution lil bit please?

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

        H1: 1. Floodfill(look it up).

        Create a row and cols array

        During each floodfill,track which rows and cols can be reached(rows and cols within 1 of connected component. and size of connected component. Rows[row] += size, Cols[col] +=size. For each row and col reacheable.

        For each '.' add one to its row and col.

        Answer is max(max(rows),max(cols))

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

    You can notice for $$$K>=10$$$ there exist no $$$N$$$.

    For $$$K < 10$$$ you can form cases as follows:

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

What is delta? How does rating work with respect to previous contest ratings?

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

Problem E was the best.

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

even problem G got leaked

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

Is G a troll Problem???

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

    Yeah, first I thought of using digit Dp then used math and solved problem.

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

spend 20 min in E because I was doing cin>>x>>y>>x>>k instade of cin>>x>>y>>z>>k :)

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

Todays codeforces was very slow in loading too much frustrated

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

How to solve E in less than O(n^3) ?

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

    There are only 2 degrees of freedom(3 variables — 1 constraint). Iterate over those and get the 3rd from the constraint.

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

    Because x <= 2000 and y <= 2000 you can brute force on just those two, and see if k is a multiple of their product. If that's true, z is going to be equal to k / (x*y).

    The time complexity will go from O(x*y*x) to O(x*y).

    265331162

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

      But time complexity will be O(x * y * t) it is too much

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

        It is guaranteed the sum of all x, sum of all y, and sum of all z do not exceed 2000 over all test cases.

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

          Wow, thanks!

          It was so simple task

          I try to find better time complexity, but did not notice than N^2 is enough

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

        You can fix two coordinates and find the third one using $$$K / (i * j)$$$.

        Then for {i, j, k} you can have at max 3! orderings of {i, j, k}.

        For each of these orderings find the max answer.

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

    Thank you everyone for the insights!! After a bit of trial and error got the n^2 approach working :)

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

Fun fact: E was originally proposed to be A of 887

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

how to solve G

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

    The answer is $$$x^r - x^l$$$ where $$$x = \lfloor \frac{9}{k} \rfloor + 1$$$.

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

    By running simple examples, you can understand that this equality is satisfied only if there are no carries during multiplication.

    For example, for k = 3, only the digits 0, 1, 2, 3 (amount = 4) are suitable to appear in any number, for k = 2, only the numbers 0, 1, 2, 3, 4 are suitable, amount = 5 for k = 7, only the numbers 0, 1 are suitable, amount = 2

    Well, calculate amount ** r – amount ** l (of course with using mod and fast pow)

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

hello @cry !

i faced a very big technical issue in todays contest of server issue and i was not able to submit many solutions , most of time it was buffering for human verification.

please help regarding this matter.

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

number theory forces

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

How 'F' has 7k+ submissions? In [newbie, pupil] range it's 4k+? Am i missing a very simple idea?

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

    You only need to know priority queues 265323773 (or binary search)

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

      what ? It's not binary search on answer?

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

      But still 7K+ for F by newbies is odd ,i mean they can but why would someone be 1000 rated if they knows this level of binary search. However it might be a case 1400+ people abusing Div4 by their alts.

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

    I use binary search of answer

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

    Simple binary search works

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

      Wow! Binary Search works? I need to upsolve this problem! Thanx Master!

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

      Hey! can you tell my why this binary search solution got hacked
      Thank you

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

        I think because you used int. You should have used long long. Also in the problem example you can see that they told ans can be large , use 64bit integer

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

    same to me G was easier although I did not do it during the contest but I upsolved it still not sure how to do F

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

    F is not a simple problem for Newbies and pupils .

    most of the submission were done thanks to cheaters

    i reached rank 900 during the first 1h:30 but when the cheats came out i was knocked to 3000

    thankfully a lot of the submissions got hacked.

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

In Problem F, what was the safe upper bound to assume on the number of turns for the binary search? (Taking into account any overflow that may occur). I saw solutions with upper bound equal to 1e12, 1e13 and 1e17.

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

    They can be hacked, correct way is to set upper bound LLONG_MAX, which isn't possible for any hacks

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

    The boss health is maximum 2e5 and the worst case is 1 attack with 1 damage and 2e5 cooldown, so the upper bound should be 2e5 * 2e5 = 4e10 I think.

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

    In the worst case: n = 1, with a = 1, c = 2e5, h = 2e5, so I think something close to 2e5*2e5

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

      yeah thinking this i kept it as 1e12. still it got hacked any reason why?

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

        Same man :(

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

        Me too.

        i made this in contest:

        bool good(ll m){
    ll sum = 0;
    rep(i, 0, n){
        sum += a[i]*((m-1)/c[i]+1);
    }
    return sum >= h;
}

        but it got hacked. However, this was accepted now:

        bool good(ll m){
    ll sum = 0;
    rep(i, 0, n){
        sum += a[i]*((m-1)/c[i]+1);
        if(sum >= h) return true;
    }
    return false;
}

        I think that just the sum explodes in some test case for me.

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

          i guess there are no new tests while hacking phase because i reload the hacked solution and it's accepted in my hacked solution exists the row sum>=h then break

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

          When n=2e4,

          and a[i]=2e5 and c[i]=1 for all i. Then total sum is close to 2e4*mid*2e5 if we don't break. Hence when mid comes to 2e10(assuming hi=4e10+1) then LONG LONG Overlow happens and due to which Binsearch will shift low pointer to mid.

          I think this is the reason why many of the solutions got hacked because they forgot to break early just like me :(.

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

            Solution

            Still hacked with break :(

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

              Because ur hi value is too high to begin with. Even if n=1, and in first mid evaluation, mid=5e17 and when we keep a[0] = 2e5 and c[0]=1. Then sum += (5e17 * 2e5) which again gives LONG LONG OVERFLOW.

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

                Ah, so hi should be at most $$$\big\lfloor \frac{2^{64} - 1}{2\times 10^{5}} \big\rfloor$$$ huh? (assuming a unsigned ll)

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

          during checking the m values, if the m value is big enough and c is small, and A is again large, then it easily overflows even int64. I got hacked for the same reason and only had to add a similar early return statement for it to not hack.

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

    4*10^10 + 1

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

    I tested it with testcase which gives the largest answer, and the largest possible answer is 39999800001 = (2*10^5)^2 — 2*10^5 + 1 with the test case: 1 200000 1 1 200000. In most solutions 1 is added after binary search, so you can search from 1 to 39999800000, but be really careful to handle the case when right edge of search is an answer, so better just search up to 4*10^10, this wouldn't slow down a solution

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

      Also don't forget to check case when answer is 1 before the binary search

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

Nice problems, congrats for such a great contest.

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

very nice tasks

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

in F task

from 21 6 1 1 1 1 1 1 5 5 8 10 7 6

how we got 21?

Won't it be 27

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

Can someone pls give some hint in G. I got stuck there is it some kind of dp or math problem. And also hint for H2

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

    H2 hint: fix the row and column ($$$r$$$ and $$$c$$$). Instead of calculating the total sum of sizes of connected components that would be connected if we paint $$$r$$$ and $$$c$$$,calculate the total sum of sizes of connected components that would NOT be connected if we paint $$$r$$$ and $$$c$$$.

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

    G: If $$$k\cdot n$$$ results in any carry, $$$D(k\cdot n)$$$ won't be equal to $$$k\cdot D(n)$$$.

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

More like Div 5.

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

the contest that i most enjoyed in a long time.

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

Can someone please explain the TLE in my submission of H1 265349188

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

    I think your profile pic kinda explains some of it.

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

      And the same code in C++ is accepted :( 265398650

      Generally I would've suspected Java, but in this case I saw some C++ submissions getting TLE on nearby test cases, and some accepted Java solutions. So I thought there is some problem in my code.

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

    I use C++ and my first solution without some optimizations got TLE, so I guess it does explain something lol

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

    I'm not an expert in Java, but I can suppose a couple of possible causes:

    • (more like an recommendation): DSU for highlighting components instead of dfs or bfs. Hypothetically DSU is quite able to pass time limit with such limitations, but to be sure I would recommend to use dfs or bfs in such simple case, since it's almost impossible for them to not pass the time limit
    • (My personal main suspect): Multiple usage of operations with hashset, especially "merge" of adjacent hashsets. Yeah, asymptotically all operations with hashsets in your solution work in $$$\mathcal O(n*m)$$$, but it's good to keep in mind that interaction with hash tables usually has a bad constant of working time, and I'm almost sure that it prevented your solutiong from passing

    If you are wondering, there is a determined $$$\mathcal O(nm \log(nm))$$$ solution with acceptable constant, and it also can be improved to determined $$$\mathcal O(nm)$$$

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

      Regarding the first point, the solution using DSU is coming faster than DFS and BFS.

      • DFS is slow probably because of deep recursion. TLE in test case 5, which is probably full # 265405138
      • The BFS solution is slightly slower, probably because of object creation (using $$$int[]$$$ as pair in Queue) 265403795
      • The DSU solution 265404399

      The second point is the main reason for TLE. Instead of precomputing the hashsets, I found them at the end only. The precomputation solution passed in C++ though :(

      Regarding using HashSet instead of TreeSet, in Java if there are a lot of collisions, then the buckets internally works as a TreeSet (refer this).

      So TreeSet and TreeMap are mainly useful when we want the values in sorted order.

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

In Problem E , for the Test case x = 4 , y = 3 , z = 1 and k = 6 , the optimal lengths i am getting is 2 , 3 , 1 , then answer will be is 3 ( (0,0,0) , (1,0,0) , (2,0,0) ) . but in problem statement it is given that answer is 4 . Anyone Please Explain !!!

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

    Theres is a better set of lengths: 3, 2, 1, which gives 4 possible positions ((0, 0, 0), (1, 0 0), (0, 1, 0), (1, 1, 0)), and due to ban of rotation in any direction, this set is not the same as 2, 3 , 1

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

Editorial

A: Switch the first letters of both words and print them. https://codeforces.net/contest/1985/submission/26521678

B: If n=3 print 3 else print 2. https://codeforces.net/contest/1985/submission/265225459

C: Keep track of sum and max of element as you scan through its prefixes. Count amount of times max = 1/2*sum. https://codeforces.net/contest/1985/submission/265232206

D: Track first and last #, when traversing grid, answer is the average of those. https://codeforces.net/contest/1985/submission/265242217

E: 1. Loop(a) through all values from 1 to x. If k divides a, loop(b) through all values y. If k/a divides b. Then c is k/a/b.

  1. answer is max of (1 + x — a) * (1 + y — b) * ( 1 + z — c)

https://codeforces.net/contest/1985/submission/265319163

F: 1. Store a min-heap priority containing time of each attack and attack.

  1. Until boss has 0 health, take top item of queue, and use attack.

  2. For each attack decrease boss's health by attack strength, and insert a new attack of strength of current attack and time of current attack + delay time.

  3. Answer is time of last used attack.

https://codeforces.net/contest/1985/submission/265293032

G: 1. Answer is ceil(10/k)^r — ceil(10/k)^l.

  1. Powers can be computed in O(log n) by squaring repeatedly storing in array, and using bit structure of n to multiply down until you get answer.

n^10 = n^8 * n^2.

https://codeforces.net/contest/1985/submission/265362645

H1: 1. Floodfill(look it up).

  1. Create a row and cols array

  2. During each floodfill,track which rows and cols can be reached(rows and cols within 1 of connected component. and size of connected component. Rows[row] += size, Cols[col] +=size. For each row and col reacheable.

  3. For each '.' add one to its row and col.

  4. Answer is max(max(rows),max(cols))

https://codeforces.net/contest/1985/submission/265337176

H2(take with grain of salt my solution passed with 1935 ms):

H1 but one must also have a point 2D array to track double counting. This happens in two ways.

  1. For each connected for each row and col reachable, track the possible double counting by adding size to points[row][col].

  2. For each '.' add one to points[row][col]

  3. Answer is max(rows[row] + cols[col] — points[row][col]).

https://codeforces.net/contest/1985/submission/265384992

Sorry if some of the later solutions are messy.

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

    For D you dont even need to keep track of the average of all rows, only the row with the highest number of #s.

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

      Yes, you could get D by finding the meidan of the row with most endpoints.

      I used average of top and bottom point ( firts and last on standard 2D array traversal).

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

    madhavG — How did you develop the idea for G?

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

      Sample cases + testing out some examples. It is obvious that if k>=10, there will be no solutions. Otherwise if k>=5: All solutions have 0 or 1 for all digits. Otherwise if k>3: All solution have 0,1,2 for all digits. So on and so forth.

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

        Do you have a proof that for any $$$k > 10$$$ there are no solutions?

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

          Not really, just intuition.

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

          For digit sum to be multiplied by 10. A 1(smallest nonzero digit), must split into atleast 2 digits. And multiplication by 10, increases digit count by 1, not doubles it. Ergo, k>10 no sols.

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

          Suppose we have a number in the form of 10a+b. The sum of its digits is (a+b)..and let us multiply a number k to it. Suppose k*b is of 2 digits and is equal to 10c+d. Hence we have:

          k*(sum of digits) = k*(a+b) but sum of digits(k*n) = sum(10a*k + 10c + d)

          for the moment consider a*k+c do not have a carry. Hence the sum of digits will be equal to a*k+c+d.

          Clearly k*(a+b) = a*k+10*c+d != a*k+c+d as an extra factor of 10 is added here. Similarly this can be extended for multiple digits and even if a*k+c does have a carry.

          Thus we can conclude that had It been a carry, then the property would not have been satisfied. It's not a solid proof but it's the best reasoning I could come up with, after the contest. Hopefully it helps.

          PS: This kind of a problem had already come on codeforces at some point in the past, where the result won't have been possible if we had carry. I just can't remember when. :(

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

    Can you please explain your point 3/ in H1 madhavG?

    "For each '.' add one to its row and col."

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

      This to cover for the fact that by changing each row to # you have to not only add all connected components touched by the row, but additionally must add all . that are now #, which would not be covered by connected components as they only include squares that are #

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

    in H2, if there was test like that, it would be TLE?

    n = 1000, m = 1000;
for (int i = 0; i < n; i+=2) {
    for (int j = i; j < m; j++) {
       G[i][j] = '#';
       G[j][i] = '#';
    }
}

    cause of 

    for (ll a:vr){
   for(ll b:vc){
      points[a][b]+=D;
      }
}

    my solution 265691252 with approach like your this test takes 7.3 sec on my PC

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

      huh, it says acceoted, you prolly just have a slow PC

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

    My H2 idea is similar , but ending up in TLE in test case 7 , can u help ?

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

    idea : there is an edge connecting two components if some c or r is replaced . sum of degs can not be more than 3*n*m , now at each component , i am pairing up (r,c) sum over ri*ci <= O(n*m) where ri = no of r connections while ci = no of edges by the column c at the connected component i .Please point out mistakes if any .Thanks in anticipation.

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

why is carrot not working ????

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

My H1 runs surprisingly slow, can someone tell me why? I'm sure it's something in my implementation but I don't know what. Feel free to hack if possible: 265367113

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

    std::set is generally slow. Especially since $$$n.m \leq 10^6$$$.

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

      But in my solution, I used 2 vectors to hash the size values of each component and got a TLE. But when I converted it into set and map, it passed, albeit still with a high time.

      Map Submission

      Vector Submission

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

    Most probably because of set and map in general, my solution uses set and map too and I got TLE, but I tried some optimizations so it got accepted in 452 ms

    You probably don't have to worry about it though, I think your time is still safe

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

=> Speedrun ABCDEF in 1.5 hour
=> Stare at G for 1 hour

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

I really hate cheaters. if you're a cheater and reading this duck you. I also wish a shitty days for the president of a certain country for spoiling my contest.

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

I enjoyed the problems a lot, G and H1 were especially neat. Thanks!

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

Hint for H2, please. For H1, I individually checked each for each row; what's the size that's getting added if we set all cols in the row to '#, i did the same for cols and chose the max as ans,

→ Reply
  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    1. Look at what can be double counted by simply taking the max of rows and cols.
    → Reply
»
6 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Codeforce server becomes very slow specially on div4 contests

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

After long time ,,,

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

Cloudfare forces, jokes aside it was a really good contest for me. I am not that good but I xould solve upto E! And I guess F would have required a solution with priority queue, but I was too slow to implement it.

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

    cloudfare blocked me from getting H2 in comp, but I got it within a minute post-comp.

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

I request this contest to be unrated atleast for me , the servers were not working 98% of the time.

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

In G, can someone explain why $$$k > 9$$$ doesn't matter?

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

    $$$K = 10$$$, D(N*10) $$$=$$$ D(N) $$$\neq$$$ 10*D(N)

    $$$K > 10$$$, D(N*(K + 10 * X)) $$$=$$$ D(N*(K<=9)) $$$<$$$ K * D(N).

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

      Didn't get the second part, how is D(N*(K + 10 * X)) = D(N*(K<=9)) and D(N*(K<=9)) < K * D(N)?

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

    as the case will be only valid when k*(any digit of n) will be a single digit number , as if it will be more than 1 digit the case get invalid (digit sum case). look into my code the case ll y=9/k+1; it will always be 1 . 265330453

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

    if u r asking for a proof idk , but if u run a bruteforce code u will find that when n > 9 , answer is always 0

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

Why is my code for problem H1 giving TLE on test 10?

I used dfs algorithm keeping ids of each component in the visited grid and stored the size of each of the component ids in a map.

I then traversed the grid row-wise and column-wise to get my answer.

Here is the link to the submission : https://codeforces.net/contest/1985/submission/265376706

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

    number of component can be $$$\frac{n\times m}{2}$$$ (think of a chessboard). So the $$$id$$$ in your code is $$$O(n * m)$$$, thus your for loop that involves constructing $$$visid$$$ is $$$O(n^2\times m)$$$.

      for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      if (grid[i][j] == '#' && vis[i][j] == 0) {
        dfs(id, i, j, grid, n, m, cursize, vis, idsize);
        id++;
        cursize[0] = 0;
      }
    }
  }
  ...
  for (int i = 0; i < n; i++) {
    int temp = 0;
    vector<int> visid(id, 0);
    → Reply
    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ohh that makes so much sense. I'll try to optimize it.

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

    Your code probably fails in a test like this:

    .#.#.#
#.#.#.
.#.#.#

    Your solutions runs in $$$O(max(n,m) * id)$$$ (because of declaring the vector $$$ids$$$ each time). The size of $$$ids$$$ may be large. In order to prevent this, you can use a global $$$ids$$$, and a queue to keep track of the components you choose. In the end of the iteration, you can empty the queue and reset only those $$$id$$$'s that were changed.

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

      Yes it makes sense. I'll try to optimize now.

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

      I got it!! The queue worked and I understood why it was necessary.

      Thanks a lot for this hint. This is my first time solving a H1 problem. Just wish it clicked to me during the contest itself

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

Can someone explain how to hack? https://codeforces.net/contest/1985/submission/265283368

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

Just hoping that the cheaters are caught:( . I saw many codes which looks like they have been copied from some other sources.

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

    I was looking at the java submissions for this contest, almost 50% of them are chat-gpt converted codes for harder problems

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

      Yeah i also saw many codes from python and it looked like they had been taken from ChatGpt or elsewhere

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

can any one tell me what is the wrong 265398472

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

    **There must be an overflow in sum ** for(int i = 0 ; i < y; i++){ sum += v1[i]*((mid/v2[i])+(mid%v2[i]>0)); }return sum >= x;

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

      ok thanks iam just use break and this was the wrong

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

I have solved F using priority queue Submission, i think its quite complex implementation of mine. Could someone check and tell me whether we have a better and neat approach for the same question. Also I would like to get the hints to solve this using binary search. Thanks

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

hi, i have a question I solve problem A and B with penalty =17… and my standing is like 20000 in the official…when other users with my performance are in like 14000…I don’t know why is this happening

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

When will people stop?

In most recent hacks, I didn't even check anything other than these three lines:

unordered_map<int, char> grid[MAX_N];
unordered_map<int, int> component_id[MAX_N];
unordered_map<int, int> component_size;

and just one test data was enough to hack like 30 submissions which had these lines. Now where is the source of this?

To explain the hack: Apparently, there has been a long-living bug with GCC's unordered_map::clear() that it keeps its bucket size, so clearing takes $$$\mathcal{O}(x+k)$$$ time where $$$x$$$ is the number of elements and $$$k$$$ is the bucket size. While $$$x$$$ is reset to 0 everytime we call clear(), $$$k$$$ remains the same so we can just insert a whole bunch of elements in the map in the first test case, and with the remaining 9999 cases we can spam $$$n=m=1$$$ so that it calls clear() 9999 times, each taking $$$\mathcal{O}(nm)$$$ time where $$$n$$$ and $$$m$$$ comes from the first test case.

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

    That's interesting. We should avoid using unordered_map. Is initiating the map locally for each test is better?

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

      In most cases it's better not to use unordered_map at all. In this case though, either making it a local variable, or just doing mp = unordered_map<int, int>(); instead of mp.clear() also works.

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

        Initiate local also variables consume time also. At some point, we can get TLE if we declare local variables and it got AC when moving to global variables. But yeah, will keep in mind to avoid using unordered_map.

        OOT, observing your hacked solution, I cant help but notice that people do like to write stories in their code :)

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

See this, 265373769.

Lots of useful statements like

for(int i = 0 ; i<56 ; i++){
        if(i == 50){
            break;
        }
    }

to escape plagarism.

Are such tricks good enough to escape plagarism? MikeMirzayanov Vladosiya

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

    Will any actions would be taken in order to address this? Atleast people who used these unnecessary for loops should be punished.

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

why my submission of C got hacked?

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

why this solution got hacked? https://codeforces.net/contest/1985/submission/265344132

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

    Because you used unordered_set (tc is O(n) for very large n values) ordered set shd work fine

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

    Unordered variants of set and map are pretty easy to hack with one simple idea, which djm03178 described in one of the comments above. From my experience, if your idea does not work with set/map complexity, then it is probably wrong.

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

why so many F got hacked? my F: https://codeforces.net/contest/1985/submission/265337189

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

anyone can you give test hack problem F

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

Idk why I'm posting it now, but here's a testcase for hacking problem F:

1 200000 100 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

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

In F, if you accumulate the total damage at the first iteration of binary search (check(mid)), it can go to $$$n*a*mid$$$, with mid going at least to $$$\frac{h*c}{2}$$$ which is around 2e10. So the total accumulated sum can go up to 8e20 at best, which explains the reason why many got hacked in F (it overflows, but overflows to the point where the accumulated sum produces negative results when casted to int64_t. This causes check(mid) to be false (while it is actually true), thus it creates a wrong answer (the range of binary search is now wrong)). To fix this it is usually needed to fast break out of the loop or use __int128.

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

As newbie, I solved 4 problems (current rating 733), will it level up my ratings?

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

I enjoyed a sound sleep after scoring 6 problems. After waking up, my 'F' got hacked!!! Thanks for not hacking the submission before my sleeping time.

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

Can anybody tell me what is the use of hacks, And what happens if I successfully hacked others solutions??

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

    Hacks here are tests added by users during a contest (Div.1+Div.2, not Educational) or in a hacking phase (Educational/Div.3/Div.4) that satisfy the problem constraints, yet make an Accepted solution (the one you're hacking) either giving different answers from the jury (rendering WA) or stumbling onto TLE/MLE/RTE/etc..

    For those rounds with hacking phase, you simply contributed to the final testset. For Div.1/Div.2 rounds, you actually gain points when hacking successfully (but before doing so you have to lock your problem first, thus not being able to resubmit in-contest and now prone to other hacking you should that solution is incorrect as well), though chances are low as present rounds seem to have pretty strong testsets to start with.

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

Here is test case for overflow hacking: https://upfile.live/download/7609ae3e/

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

Hacking is so scary

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

Can you check question F for me?

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

Can anyone look at why my E got hacked?

https://codeforces.net/contest/1985/submission/265354724

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

Problem F : Can someone please help me in finding the mistake in the following code . It got accepted during the contest but now it is showing hacked.I am not able to find the mistake .

Submission

Thanks

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

    Run your code for the below test case: 1 1 1 200000 1 It overflows and returns 92233720368548 instead of 1.

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

Can anyone tell me why am I getting Runtime error for my submission 265366493 for H1?

Approach : Mark all the connected components and store their size in a map. When marking a particular row or column, take all component and add their size.

Same approach is passing that test without Runtime Error 265347306 but giving MLE.

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

my rating is 987 <1400, i have given this contest but it is unrated for me. why is it?

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

One of my fav Contests. Finally contests with less math and more algorithms.

Loved it

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

when are the ratings updated?

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

My solution for question F got hacked thereafter I submitted the same solution and it got accepted, then the solution got hacked. Please help!!

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

    Same with me. And why are the ratings not updated with new test cases then?

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

      yes send me all solution of your last algroave contest they dont allow me to send msg more than 2 in same hour so i can't msg u there

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

    I believe that the hack tests aren't yet added into the set. Best that we should wait until system testing finishes (which... I'd assume to be ~4-6 hours from now).

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

      Can there be a possibility of hack been removed??

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

        Realistically, no chance. Unless hacks are of invalid inputs that validator code from the round setters failed to catch, I don't see why (in most of the time) one should remove a hack test that would discern correct answers from wrong ones.

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

        Don't use unordered set and map

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

      But it is not showing system testing. If many have similar solutions , if mine is hacked then those solutions should also be considered as wrong submissions right?

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

        Yeah. System testing will come much later, and it will include all the hacks presented. In a way, don't worry, those "similar solutions", if really similar, would fail eventually.

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

          Why system testing has not even started yet? Is there something unusual or it is normal?

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

When will the ratings be updated??????

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

Problem F guarantees that the sum of h and n over all test cases does not exceed 2*(1e5) ... However, it seems like this constraint has not been enforced in quite a few hacks generated.

For example, https://codeforces.net/contest/1985/hacks/1041402/test

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

    Nah, the test you showed clearly falls within constraints.

    There's only one test with $$$h = n = 2 \cdot 10^5$$$, which is just right at the upper bound limit for both $$$\sum h$$$ and $$$\sum n$$$. Notice that there are no limits on $$$\sum a$$$ or $$$\sum c$$$.

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

      Apologies, I though the constraint was ∑(h+n) <= 2*(1e5)

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

just virtualled it, a w div4 round as expected from the problemsetters orz

(i wouldve had a +100 delta if i had actually taken it :( sadge ) (help i used unordered_set by habit for h1, please no hack) (random gibberish, i am sleep deprived and have no concept of social cues anymore)

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

Why is this under unrated for me i did solve 3 question and i am under 14

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

can someone tell why is dsu giving tle in H1

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

Here's my bfs submission for H1 if u r looking for

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

very good problem!

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

What does -1 indicates in the problem dashboard?

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

    if this is for problem F, you were most likely hacked, but you can check what happened by double clicking the -1

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

has the result come for this contest?

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

C was little difficult for me , but it it was fun upsolving it.

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

When would this system testing ends? When we can see our final results ( final rating change) does anyone have any idea ?

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

that was awesome

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

cf

I submitted my code for contest 952 (Div-4) Problem B 6 minutes before the contest ended, and it was accepted yesterday. However, today it is showing that it is still in the queue. Why is this happening?

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

    System testing

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

    They are conducting a second test

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

    while system testing, they run the code for new testcases. So basically you code is there in queue for getting tested on new testcases.

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

so as of now , system testing is done what about updates in ratings ?? does anyone has any idea ?

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

Could anyone please tell why my rating has not been updated?

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

Div was very special

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

Why is it that my score has reached 1200, but I am still a newbie

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it
  • I solved 6 problems with 219 penalty.
  • I can find myself at the 854th place in the 'Common Standing' page.
  • But when I go to the 'Friends Standing' page it says I'm on the 1312nd place.
  • Also the 'Rating Changes' and 'Friends Rating Changes' pages list me on the 1312nd place.

Can someone help me to understand this discrepancy?

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

    that's because in standings there are only trusted participants

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

Finally became pupil. Thank you for this round. Onto specialist now :D

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

Hello I want to ask about something I solve 2 questions in div 4 correctly from first try and my rate decreased why ?!

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

    In simple words, at your rating, a better performance is expected from you.

    It's more about the ranking than solving 2 problems.

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

      Okay but I should have at least increased by less than 10 points, for example

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

tomato

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

Why am i getting TLE in my submission for H1 ? 265560987

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

I've just VP and solved 6 problems.

SO SORRY THAT I CAN'T PARTICIPATE OR ELSE I WILL GET MUCH RATING

→ Reply
»
6 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it 
#include<bits/stdc++.h>
using namespace std;
#define int long long
int mod=1e9+7;
vector<vector<int>> mult(vector<vector<int>>& a,vector<vector<int>>& b){
    int r=a.size();
    int c=b[0].size();
    int comm=b.size();
    vector<vector<int>> ans(r,vector<int>(c,0));
    for(int i=0;i<r;i++){
        for(int j=0;j<c;j++){
            for(int k=0;k<comm;k++){
                ans[i][j] = (ans[i][j] + (a[i][k] * b[k][j])%mod)%mod;
            }
        }
    }
    return ans;
}
int func(int n,vector<vector<int>>& mat,int node){
    vector<vector<int>> ans(n,vector<int>(n,0));
    for(int i=0;i<n;i++) ans[i][i]=1;
    while(n>0){
        if(n%2==1){
            n--;
            ans = mult(ans,mat); 
        }
        else{
            n/=2;
            mat = mult(mat,mat);
        }
    }
    return ans[0][node];
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m,k,a,b;
    cin >> n >> m >> k;
    vector<vector<int>>mat(n,vector<int>(n,0));
    for(int i=0;i<m;i++){
        cin >> a >> b;
        mat[a-1][b-1]++;
    }
    cout << func(k,mat,n-1) << endl;
    return 0;
}

Can someone please see what is the inefficiency here? When I manually run it on custom invocation in codeforces it says "Memory limit exceeded" however I have passed all the matrices by reference. Also, the code given here for graph paths — 1 is getting accepting by using a recursive implementation of binary exponentiation. I have used iterative implementation, still it is not accepted. Kindly have a look. This is for problem Graph Paths -1 of CSES under mathematics section

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

I participated in the contest but one of my solution "significantly coincides with solutions deified/265366837". I have not engaged in any type of such activities i know that for sure as my solutions are different from any other for which i got a rank of 187 whereas "deified" who had copied(without my consent)/similar code has got a rank of 523. If someone did a little bit similar syntax and now i am excluded from the context then i am not participating in any further context. Please look into the matter.

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

    yes i know him. He is one of the top coders of JU. Please look into the matter.

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

I participated in this contest and have been accused for Plagiarism, with the user newbie333 265377444 while here is my submission 265318802. I have had no prior contact to the user, though our answers are visibly similar, Like idk how real are the chances of this happening, but i believe the approach written in solution is very standard.

Also there is a significant difference between the time of submission between us around an hour or so, Please consider this as mere coincidence and make this round rated for me again.

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

    bro never expected this from you...

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

    Actually, i'm only the normal participant like everyone and make sure that almoost all my answers are mine. When i received this report from the system, I'm extremely stunning that problem. To be honest, i do not know TarunAga prior in the real and even virtual life. how this happens?

    I strongly agree with TarunAga opinion and his post, and i warrant that my submission was so late than his one about 1 hour, but this can not prove me as Plagiarism. I reckon that this issues should verify again and please consider is as a coincidence. Eventually, I hope the system to rate point for us again.

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

    SoCloseButStillSoFar

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

Dear Contest Organizers, cry and MikeMirzayanov

I hope this message finds you well. I participated in the Codeforces Div. 4 round on Tuesday, June 11, 2024, at 20:05 UTC+5.5. I recently received a message stating that my code matches with many other submissions. I would like to sincerely clarify that I did not share my code with anyone, nor did I copy it from any source.

The problem I solved involved a straightforward implementation of a priority queue, which is a common approach and could easily result in similar code among different participants. Below is my code for your reference: 265367242

The solution relies on basic operations with priority queues and vectors, which can result in similar implementations by others independently. I am confident that this overlap is purely coincidental given the simplicity and commonality of the approach.

I kindly request you to review my case. I assure you of my honesty and integrity in this competition. Please make this round rated for me.

Thank you very much for your understanding and support. cry, MikeMirzayanov

Best regards, AnchalJain06

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

Dear cry

I participated in the Codeforces Div. 4 round on Tuesday, June 11, 2024. Today I received a message my solution of problem F is similar many other solution. I don't know how is it possible? Here is my last year contest submission 182009452 181980838 and this problem F solution is 265365007 . My last contest code and previous year contest code pattern is the same . And In this problem F , I used binary search for finding minimum number of turn and avoid TLE. I don't know why some of solution is the same. I suggested you check all of problem solution. I think you are understand easily.

Thank you.

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

Hi cry,

I wish to challenge the plagiarism case raised in front of me a week after the contest. I have been accused of coincidentally copying my solution for problem F from about 50 people. I do not know how, in the right mind, it was done or if anyone even looked at the codes. I am hoping that was automated so no one noticed. However, I compared my code to that of about ten people on this list. My code has been claimed to plagiarise the input style and the usage of the priority queue. Specifically, 2 loops for the input and a while loop for the priority queue. Now, I do not understand how anyone would claim that it comes under plagiarism because my code style, template, macros, and everything else are on point, like all my submissions I have ever made on this website. Not just in the contest but literally throughout my submission on this website. 265376036 is my submission for the problem. And I'll provide you with some more codes that have been claimed to be plagiarising with me. You can look at the solutions and everything.265299387 265380885 265377283 265359673. The parts being shown to be the same are how code is used on all of my codes. Please look into it.

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

orz

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

Hey there, I participated in this contest and it is showing my solution is copied from some 30+ ppl after a week. I think this was a pretty straight forward priority queue implementation qn. Now I don't know how that can happen as I use VSCode while writing the code. I was so happy that I was able to solve a lot of qns as the questions this time had less math involved and more algos. Please look into it. You can check that my other submissions also follow a similar pattern.

Regards

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

I tried running my code on ideone in default setting and someone copied my code and I was not aware about that.

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

Tomato

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

Good contest!

→ Reply