cry's blog

By cry, 3 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

»
2 weeks 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).

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

orz

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

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

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

Published 2 months ago! :O

»
2 weeks 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!

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

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

    Now i need to wait for the next Div. 4

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

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

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

uwu :3

»
2 weeks 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!

»
2 weeks 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!

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

Will try to solve this round in rainboy style :)

»
2 weeks 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

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

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

»
2 weeks 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

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

cry orz

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

sto orz (just two cats about to fight)

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

why is cry crying (crying emojis)

»
2 weeks 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 :^)

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

Div-4 is Mental satisfaction for Newbies

»
2 weeks 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****

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

My first unrated contest , yay!

»
2 weeks 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!

»
2 weeks 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!!!

»
2 weeks 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.

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

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

lol

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

I am gonna reach Pupil at this contest!!

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

    Best of luck! I hope you do great

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

      thanks you! I hope we both will reach Pupil

      • »
        »
        »
        »
        13 days 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 .

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

create 2 new problems and make a div 3 also.

»
2 weeks 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!

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

As an unrated contestant i hope to solve the problems

»
2 weeks 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,

»
2 weeks 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 ....

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

The best writer...

»
2 weeks 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?

»
2 weeks 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

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

Most casual announcement ever.

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

What is the penalty of resubmission in this round?

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

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

»
13 days 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

»
13 days 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!

»
13 days ago, # |
Rev. 2   Vote: I like it +4 Vote: I do not like it

Hoping to perform better after 2 poor performances .

»
13 days ago, # |
  Vote: I like it +16 Vote: I do not like it

hope my rating>0

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

Is the Div4 the easiest competition game in CodeForce?

  • »
    »
    13 days 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

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

hopefully i can participate in a div4 soon!

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

let's go!!good luck everyone

»
13 days ago, # |
  Vote: I like it -7 Vote: I do not like it
11003 users be like:
»
13 days 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!!!)

»
13 days 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.

»
13 days 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

»
13 days 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.

»
13 days ago, # |
  Vote: I like it +1 Vote: I do not like it

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

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

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

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

    By seeing your submissions ,i think you are cooked.

    • »
      »
      »
      12 days 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.

      • »
        »
        »
        »
        12 days 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

»
13 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Hope to get positive delta

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

Hellowo :3

»
13 days ago, # |
  Vote: I like it +1 Vote: I do not like it

:)

Spoiler
»
13 days ago, # |
  Vote: I like it -7 Vote: I do not like it

»
13 days 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.

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

Hope to reach pupil, also good luck to everyone!

»
13 days ago, # |
  Vote: I like it +1 Vote: I do not like it

All the best guys :))

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

I hope I will get some point. UwU

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

Vai Kalke semistar final ☹️(Bangla)

»
12 days 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.

  • »
    »
    12 days 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.

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

    nothing

»
12 days 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?

  • »
    »
    12 days 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.

»
12 days ago, # |
  Vote: I like it -36 Vote: I do not like it

Div 5

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

ABCD, I'll take it.

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

geometryforces... and negativedeltaforces for me :(

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

    where did you see geometry?

    • »
      »
      »
      12 days 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 :)

      • »
        »
        »
        »
        12 days 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

        • »
          »
          »
          »
          »
          12 days 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!

        • »
          »
          »
          »
          »
          12 days 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'
          
        • »
          »
          »
          »
          »
          10 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          • »
            »
            »
            »
            »
            »
            10 days 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.

»
12 days 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)?

  • »
    »
    12 days 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.

  • »
    »
    12 days 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.

  • »
    »
    12 days 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)

  • »
    »
    12 days 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

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

How to solve C?

  • »
    »
    12 days 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.

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

      Ohh!

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

  • »
    »
    12 days 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

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

any counter example for problem E , submission

»
12 days 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.

  • »
    »
    12 days 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

»
12 days 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

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

    H1&H2 is floodfill, a common graph algo

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

      H1 can be solved using DSU

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

        I dont know DSU

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

          really ?

          • »
            »
            »
            »
            »
            »
            12 days 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.

            • »
              »
              »
              »
              »
              »
              »
              12 days 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?

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

                I did USACO prior (got to silver)

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

                  plus many years of math competitions.

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

                  So you practiced their training problems?

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  12 days 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?

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

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

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

      Explain your solution lil bit please?

      • »
        »
        »
        »
        12 days 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))

  • »
    »
    12 days 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
»
12 days 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?

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

Problem E was the best.

»
12 days ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

even problem G got leaked

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

Is G a troll Problem???

  • »
    »
    12 days 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.

»
12 days 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 :)

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

Todays codeforces was very slow in loading too much frustrated

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

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

  • »
    »
    12 days 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.

  • »
    »
    12 days 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

    • »
      »
      »
      12 days 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

      • »
        »
        »
        »
        12 days 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.

        • »
          »
          »
          »
          »
          12 days 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

      • »
        »
        »
        »
        12 days 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.

  • »
    »
    12 days 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 :)

»
12 days ago, # |
  Vote: I like it +1 Vote: I do not like it

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

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

how to solve G

  • »
    »
    12 days 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$$$.

  • »
    »
    12 days 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)

»
12 days 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.

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

number theory forces

»
12 days 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?

  • »
    »
    12 days 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)

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

      what ? It's not binary search on answer?

    • »
      »
      »
      12 days 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.

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

    I use binary search of answer

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

    Simple binary search works

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

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

    • »
      »
      »
      12 days 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

      • »
        »
        »
        »
        12 days 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

  • »
    »
    12 days 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

  • »
    »
    12 days 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.

»
12 days 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.

  • »
    »
    12 days 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

  • »
    »
    12 days 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.

  • »
    »
    12 days 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

    • »
      »
      »
      12 days 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?

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

        Same man :(

      • »
        »
        »
        »
        12 days 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.

        • »
          »
          »
          »
          »
          12 days 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

        • »
          »
          »
          »
          »
          12 days 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 :(.

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

            Solution

            Still hacked with break :(

            • »
              »
              »
              »
              »
              »
              »
              12 days 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.

              • »
                »
                »
                »
                »
                »
                »
                »
                12 days 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)

        • »
          »
          »
          »
          »
          12 days 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.

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

    4*10^10 + 1

  • »
    »
    12 days 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

    • »
      »
      »
      12 days 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

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

Nice problems, congrats for such a great contest.

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

very nice tasks

»
12 days 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

»
12 days 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

  • »
    »
    12 days 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$$$.

  • »
    »
    12 days 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)$$$.

»
12 days ago, # |
  Vote: I like it -12 Vote: I do not like it

More like Div 5.

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

the contest that i most enjoyed in a long time.

»
12 days ago, # |
  Vote: I like it +8 Vote: I do not like it

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

  • »
    »
    12 days ago, # ^ |
      Vote: I like it +49 Vote: I do not like it

    I think your profile pic kinda explains some of it.

    • »
      »
      »
      12 days 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.

  • »
    »
    12 days 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

  • »
    »
    12 days 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)$$$

    • »
      »
      »
      12 days 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.

»
12 days 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 !!!

  • »
    »
    12 days 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

»
12 days 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.

  • »
    »
    12 days 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.

    • »
      »
      »
      12 days 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).

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

    madhavG — How did you develop the idea for G?

    • »
      »
      »
      12 days 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.

      • »
        »
        »
        »
        12 days 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?

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

          Not really, just intuition.

        • »
          »
          »
          »
          »
          12 days 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.

        • »
          »
          »
          »
          »
          12 days 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. :(

  • »
    »
    11 days 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."

    • »
      »
      »
      11 days 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 #

  • »
    »
    10 days 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

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

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

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

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

      probably due to using pof sets

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

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

why is carrot not working ????

»
12 days 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

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

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

    • »
      »
      »
      12 days 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

  • »
    »
    12 days 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

»
12 days 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

»
12 days 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.

»
12 days 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!

»
12 days 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,

  • »
    »
    12 days 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.
»
12 days ago, # |
  Vote: I like it +5 Vote: I do not like it

Codeforce server becomes very slow specially on div4 contests

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

After long time ,,,

»
12 days 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.

  • »
    »
    12 days 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.

»
12 days 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.

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

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

  • »
    »
    12 days 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).

    • »
      »
      »
      12 days 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)?

  • »
    »
    12 days 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

  • »
    »
    12 days 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

»
12 days 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

  • »
    »
    12 days 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);
    
    • »
      »
      »
      12 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    12 days 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.

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

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

    • »
      »
      »
      12 days 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

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it
»
12 days 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.

  • »
    »
    12 days 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

    • »
      »
      »
      12 days 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

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

can any one tell me what is the wrong 265398472

  • »
    »
    12 days 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;

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

      ok thanks iam just use break and this was the wrong

»
12 days 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

»
12 days 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

»
12 days 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.

  • »
    »
    12 days 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?

    • »
      »
      »
      12 days 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.

      • »
        »
        »
        »
        12 days 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 :)

»
12 days 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

  • »
    »
    12 days 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.

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

why my submission of C got hacked?

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it
  • »
    »
    12 days 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

  • »
    »
    12 days 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.

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

anyone can you give test hack problem F

»
12 days 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

»
12 days 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.

»
12 days 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?

»
12 days 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.

»
12 days 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??

  • »
    »
    12 days 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.

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

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

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

Hacking is so scary

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

Can you check question F for me?

»
12 days 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

»
12 days 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

  • »
    »
    12 days 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.

»
12 days 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.

»
12 days 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?