cry's blog

By cry, 2 months ago, In English

This was our first time setting a Div.4 contest. We sincerely hope you enjoyed the problems!

1985A - Creating Words

Problem Credits: cry
Analysis: cry

Solution
Code (C++)
1985B - Maximum Multiple Sum

Problem Credits: cry
Analysis: cry

Solution
Code (C++)
1985C - Good Prefixes

Problem Credits: sum
Analysis: cry

Solution
Code (C++)
1985D - Manhattan Circle

Problem Credits: cry
Analysis: cry

Solution
Code (C++)
1985E - Secret Box

Problem Credits: cry
Analysis: cry

Solution
Code (C++)
1985F - Final Boss

Problem Credits: cry, sum
Analysis: cry, sum

About Hacks
Solution
Code (C++)
Bonus
1985G - D-Function

Problem Credits: cry
Analysis: cry

Solution
Code (Python)
1985H1 - Maximize the Largest Component (Easy Version)

Problem Credits: sum
Analysis: sum

Solution
Code (C++)
1985H2 - Maximize the Largest Component (Hard Version)

Problem Credits: sum
Analysis: sum

Solution
Code (C++)
  • Vote: I like it
  • +103
  • Vote: I do not like it

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

tomato

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

    tomato

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

      tomato

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

        tomato

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

          tomato

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

            tomato

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

              tomatooooo

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

                me too

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

                tomato

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

                  tomato

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

                  tomato

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

                tomato

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

              tomato

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

              even you are not able to crush that tomato.

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

      tomato

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

    what's mean? why so many "tomato"

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

    tomato

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

    tomato

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

    tomato

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

    tomato

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

    tomato

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

    tomato

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

F : Boss Fight Detailed Video Tutorial Priority Queues and Maps

https://youtu.be/COkEV373zRo?feature=shared

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

got hacked on F :(

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

Hopefully rating changes will come out soon!

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

my C's not gonna pass system testing :( and Thanks! for E,F,G , for E looping over sorted divisors of k is also an interesting solution ig

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

my binary search solution wasnt hacked because i checked for overflow :D way to go

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

    +1 did the same

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

    how i didn't understand . how can i learn it

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

    how to check overflow, please tell the constraints on left and right, and did you do l<=r or l < r, can you please explain

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

      Thats not the overflow error. In binary search many including me put r as 1e12 ish.

      The max value of attack will be — 1e5 * 1e5 * 1e12.(N, attack[i], mid) long long cant handle that. To solve it, at every iteration of n we have to check if the value is greater than health or not

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

        Your comment literally says its because of overflow :D

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

          He was asking about the constraints on binary search. L<r or l<=r won't lead to overflow. Maybe he meant it as 2 separate things.

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

            oh sorry i misunderstood but yea whenever we multiply two very large integers its always recommended to check for whether its gonna overflow or not :D well you are definitely a specialist and way better than me so you know better ;D

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

              Yea I actually forgot checking. Anyways rating doesn't matter when making mistakes and during discussions. Also I think you will reach pupil, Congo!

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

        I have checked if monster health is between [2^r,2^(r+1) ) taking r from 0 ,1 ...so on to avoid overflow .

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

      Youtube Link this video might help you.

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

Thanks for the editorial. I learned a lot.

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

tomato

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

This was a good contest! Thank you cry and sum!

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

Was it a unrated contest??

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

When is the time of acceptance for a problem calculated? Is it at the time the problem is submitted and accepted, or at the time we see the acceptance?

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

    Time will be calculated based on submission but the solution should be accepted

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

    Sometimes, the verdict of our solution will be delayed because it will be in the queue. If your solution is accepted then the time of acceptance will be when you submitted it.

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

tomato! got hacked on F ;(

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

What is the difference between my binary search sol and those that got hacked? I wanna know more on why I got pass the hacking phase.
https://codeforces.com/contest/1985/submission/265355482

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

    It's when someone uses a very high value for the upper limit of binary search (like 1e18). Then (turns/c[i])*a[i] could go very high, even above 64 bit long long. So to AC you could either use int128, or set a lower upper limit such as yours. Or use a lang like python :)

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

      Oh, that's interesting! Thanks!

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        h -= a[i]
        

        This rules out the test cases where all the attack values were $$${2 \cdot 10^5}$$$. So, the maximum sum of $$${a_i}$$$ should be less than $$${2 \cdot 10^5}$$$. The choice of r = $$${10^{11}}$$$ is judicious as $$${r \cdot \sum\limits_{k = 0}^na_k}$$$ fits in the range of LONG LONG INT.

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

          That makes more sense now :0

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

      You're wrong, it's not because of the upper bound you take. I've also taken 1e11 as upper bound but got hacked. 265328896

      If all attacks have damage 2e5 and cooldown is 1, sum can reach 2e5 x 2e5 x mid. if mid is >= 1e8, it overflows. Yours is correct because of the h -= a[i]. It prevents running binary search in such cases.

      The correct way to deal with this is to use 128 bit integer or break out of the loop as soon as sum becomes >= h.

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

        I will consider this as the official answer :v Thank you so much!

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

    the value of r (or high) you have taken it to be 1e11 while i took 1e14 which caused overflow

    265361398

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

tomato

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

Going to spend time crying because the brute force approach did not come to mind for E

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

Anyone who used DSU for H1,H2 explain your solution?

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

    For H1 — You can use dsu to connect the components first and get the size of each component.Now for each row,check if . have any neighbor # which it can connect to,if it can then add that component size,finally add all . of this row to size aswell(as they will be converted to #).Do same for columns aswell and then finally return max value.

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

    You can use dsu to join components of '#'. Notice that for any $$$(n * m)$$$ grid, we can represent $$$(i, j)$$$ as $$$(i*m + j)$$$. So initialize a disjoint set of $$$(n*m)$$$ components at first.

    Then whenever you encounter a '#', you can run a flood fill via dfs / bfs and take $$$(i, j)$$$ = $$$(i*m + j)$$$ as the parent for all '#' you encounter.

    Now you have size of all the connected components of '#'.

    Now you can either '#' an entire row or column. I'm considering row here, same thing can be done for each column.

    Notice when you '#' an entire row, You already have some '#' as parents, once you '#' the row, all these parents combine together.

    One more thing, the parents from row above and row below will also be joined in this new component.

    Hence the final answer would be $$$Count('.')$$$ + size of each parent you encounter.

    To prevent taking a parent twice you can use the set.

    Code:

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

    I use DSU+DP to calculate four arrays: when the operation is at row=x, col=y, what's the total size we can get for the top-left/top-right/bot-left/bot-right w.r.t to (x, y).

    I use set to track rather than unordered_set so the complexity is O(mnlog(n)): https://codeforces.com/contest/1985/submission/266763301

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

tomato

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

tomato

i need help in problem G :=> "D function" i am not able to understand the editorial so a simpler straight forward way would be really helpful

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

    consider the digit to be xyz and when we multiply it by k individual digits will be multiplied by k so the new digit will be like (kx)(ky)(kz) to get what is asked in question we should notice that during multiplication if carry is genrated then our condition is never met . so (kx) should only lie between 0 and 9 , similarly other two.

    thus for k>=10 ans is simply no. now let us take for k = 1 to 9 k = 1 --->> [0,9] k = 2 --->[0,4] because (2*5 = 10) thus we get num by 9/k + 1;

    now consider this r_ _ _ l_ _ _ now from i = 0 to r ith digit can take num values but we need to eliminate those answers which are less than 10^l; so for i = 0 to l-1 ith can take all nums and for i = l to r-1 rest wil be 00; thus ans would be simply difference of both.

    Ps: check my soln once for better understanding: 265443453

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

For problem F, if we take R as 1e12 it is being hacked

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

    Consider 2e5 values equal 2e5 in array a, array c : 2e5 values equal 1 .. so, when multiplying (mid / c[i] * a[i]) 1e12 * 2e5 * 2e5 gives 1e22 which doesn't fit into 64bit :)

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

      The editorial contains bonus problem solution which uses 1e12

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

        I have used 1e13 lol, just break the loop as soon as sum becomes GTOE health. I mean if you're not breaking the loop, it will cause overflow .

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

          My bad didn't see that return true part. Understood thanks

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

tomato :) btw a question. will the time complexity of priority queue solution be also $$$ O(hlogn) $$$ ?

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

tomato

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

Fast Editorial!

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

Tomato

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

this was my first contest on codeforces , managed to solve A and B , got TLE on C . should i register for upcoming div 2 contests or just wait for other div 3 or div 4 contest ? What should i do , suggestions ??

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

    You should register for contest and try to solve a and b

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

      but it feels like waste of time struggling with problems after A and B , should i prepare more first ? before contesting for div 2 contests

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

    I think you should wait for DIV 3, because problem A div 2 +-= problem C div 4

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

    you should register for div 2 and try to solve atleast a. from my first 5 contests, onlt 1 was div3, rest were div2s.

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

      Ok , thankyou for your suggestion

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

        You could do either, I personally waited till I hit expert atleast once before doing non-educational Div2.

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

this was my first contest, will this change my status from unrated to newbie?

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

tomato

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

tomato

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

what does tomato mean?

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

    The editorial solution for problem F has a comment in the code that says to comment "tomato" if you read that comment.

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

Is there anyone generous enough to debug my code?

I tried to up-solve F. If I'm not wrong my solution takes O( n log n). Then why it's getting TLE on the second test case?

Submission: 265448705

Edit: Solve it by replacing the vector(named coolingTime) with a map;

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

Tomato

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

I'm still eager to see a proof of why there are no such $$$n$$$ that satisfy $$$D(n \cdot k) = k \cdot D(n)$$$ in the case of possible carries in multiplication.

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

    Same. I just guessed it

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

    Yeah, guessed it is well, 'cause haven't managed to construct a formal proof of that fact in a reasonable amount of time during the contests. Wonder if such even exists. If yes, I am interested to see it too.

  • »
    »
    5 weeks ago, # ^ |
    Rev. 4   Vote: I like it +7 Vote: I do not like it

    We can see that for a number with more than one digit, its $$$D$$$ will be smaller than itself(this is how number expression works!). For a number with exactly one digit, its $$$D$$$ is equal to itself.

    Imagine we are multiplying a single digit $$$x$$$ by $$$k$$$, resulting in a carryover. We get a result $$$kx$$$ which has more than one digit. And we expect $$$D(kx)$$$ to be $$$kD(x)$$$, which is equal to $$$kx$$$ ($$$x=D(x)$$$). Thus, our $$$D$$$ has been smaller than the target. It’s impossible to compensate for this with another digit multiplication since $$$D(ky)$$$ won’t be greater than $$$ky$$$ for any $$$y$$$.

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

    For each carry, D will be reduced by 9: the carry will add 1 to D instead of adding ten.

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

    Yeah shitty editorial.

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

solved A B C D , first contest after so long , hoping to be 1000+ after the rating update.

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

I submitted the hacked solution for question F again and it got accepted then how is it possible that my solution got hacked, please help!! cry

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

Problem G was ProjecteulerForces XD

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

tomato

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

![ ](Screenshot-2024-06-12-123853)

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

In H1 why to subract R[maxR + 1] -= sz; and C[maxC + 1] -= sz; in solution.

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

Can anyone help explain why this equation is wrong only with large numbers in problem F using the binary search method?

The number of times we use the current attack is ceil(mid / (c[i] + 1)).

(c[i] + 1) is the segment length in which we can perform only one attack.

Dividing gives us the number of segments we have, and any float will be ceiled. I don't understand why this is incorrect. Can anyone clarify?

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

When will start System testing?

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

Is there a formal proof for B?

  • »
    »
    5 weeks ago, # ^ |
    Rev. 8   Vote: I like it +14 Vote: I do not like it

    Let's consider any number greater than $$$n > 3$$$, then for $$$x=2$$$ we have $$$k = \lfloor n/2 \rfloor$$$ , hence $$$2 \cdot (1+2+ \dots k) = k \cdot (k+1)$$$, which is $$$n \cdot (n+2)/4$$$ for even $$$n$$$ and $$$(n^2-1)/4$$$ for odd $$$n$$$.

    Consider any $$$x \ge 2$$$, then, $$$g(x) = \frac{(n+1) \cdot (n+1-x)}{2x} \le \frac{x \cdot k \cdot (k+1)}{2} \le \frac{n \cdot (n/x+1)}{2} = \frac{n \cdot (n+x)}{2x} = f(x)$$$. On evaluating, we get $$$f'(x) = \frac{-n^2}{2x^2}$$$ and $$$g'(x) = \frac{-(n+1)^2}{2x^2}$$$, hence a decreasing function. Thus, $$$f(x)$$$ or $$$g(x)$$$ should be maximum at $$$x=2$$$.

    If the $$$f(x)$$$ and $$$g(x)$$$ logic is not convincing, you can think that $$$\lfloor n/x \rfloor$$$ will be always of the form $$$(n-\lambda)/x$$$ ,where $$$0 \le \lambda < x$$$ and it depends on $$$n$$$. [In fact, $$$\lambda = n \% x$$$] Thus the sum $$$h(x, \lambda) = \frac{(n - \lambda) \cdot (n- \lambda +x)}{2x}$$$, where $$$\lambda$$$ itself depends on $$$x$$$ and $$$n$$$. But, the for the extreme values of $$$\lambda$$$, the function $$$h(x)$$$ essentially takes the form $$$f(x)$$$ or $$$g(x)$$$, and it can be shown that it will work for any intermediate $$$\lambda$$$ as well.

    PS: I am not sure why the above explanation doesn't work for $$$n=3$$$, could anyone point it out? Thanks!

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

      Really intuitive and clear explanation, thanks a lot.

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

      3(2) = 2

      3(3) = 3 3>2

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

        Yep I know that, but why is the proof failing? Cause the function is decreasing?

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

    x(1+2+3+......+k) = k(x+kx)/2 — eq1 As x<=n and kx<=n => x+kx<=2n => (x+kx)/2<=n => eq1<=kn and if we consider n>=2 exept 3 we get the maximum value of eq1 when we have max k value thus k will be max for x = 2 as x>=2 given in problem and x = n/k thus for larges k we have to take smallest possible value of x thus 2 here and it will give the max answer for every n value. But for 3 we will have to take 3 as 2 < 3

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

got hacked F, ha.

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

cry for H2 on point 3. of the last paragraph, shouldn't it be subtract s on the subrectangle?

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

write proof for G, please

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

    If I add two numbers and their digit carry over, then the digit sum of the new number will onviously decrease than the sum of the digit sum of the first two numbers. Same thing for k additions, if it is same after k additions, there should still be no carry. If there is no carry then each digit can be calculated for separately. More precicely each digit can range from 0 to 9/k. If a number is less than 10^l, then there are l digits to be filled so 9/k+1)^l. since we are asked in between, we can simply subtract the two values for r and l.

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

Is it just me or the code for Problem E is wrong?

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

For G, i solved this problem by Matrix Multiplication

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

H2: We find some $$$O(n^3)$$$($$$O(nm\times \min(n,m))$$$) solutions like 265329368. Their solutions need to enumerate each cells in the smallest rectangle containing the connected blocks.

The data like

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

or

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

can let them have $$$O(n^3)$$$, but in fact they just need to run about $$$\frac{n^3}{12}$$$ times. We tried another construction, but it also failed. I think these solutions are wrong, hope the new construction can hack them.

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

Problem G was really good. Though I did not figure it out until I read the solution.

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

tomato

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

Tomato

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

I wonder why some participants solved the 'D' problem in a horrible way. Simply, push all the coordinates where the char is '#'. Then print the middle one.

Submission: 265290261

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

So how many testcases are there now in problem F?

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

tomato

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

how much time it takes for the ratings to be updated ???

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

tomato

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

Meow

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

to be honest, i generated all n satisfy for all k from 2 to 11 and got the rules. got AC just by guessing the rules and i don't know how to prove the solution at all i was so regret that my solution for problem F got hacked because i forgot to check the overflow case

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

for this problem 1985E — Secret Box the code you provided gave 0 instead of 1030301 for the last test case. how come does it get accepted ? please answer. even my code was giving 0.that's why i didn't submit it yesterday.

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

Hi everyone,

I participated in this contest yesterday and I managed to solve 3 questions out of 9. Today when I look at the submissions, it says that I was only able to solve 2 out of 9. Can anyone tell me why is this happening?

Thanks.

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

tomato

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

tomatooooo

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

Wow, G solution was so easy... I almost came up with the idea that for each digit there are 9/k+1 digits, but I used 10/k+1, so couldn't figure out the answer(

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

Hey Guys, did anyone solve E. Secret Box in less than O(xy)?

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

    Yes, it is solvable in O(k).

    Here is the complete solution. Find all divisors of k and store them in a vector(let's call it div). The maximum size of this vector is sqrt(k) (let's call it size sz). Then you can brute force for x and y in this vector and calculate x = k/x/y. Now if these x,y,z satisfy given constraint then you got a valid dimension.

    Overall complexity(O(sz*sz) where sz = sqrt(k)) => so O(k) Here is my O(n) submission: https://codeforces.com/contest/1985/submission/265647792

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

      k <= 1e9?

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

        Yes, it will still work because number of divisors for k <= 1e9 at max is 1344. So O(1344^2)

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

          But O(root k) to find divisors actually takes more time then O(xy)

          I used the same approach, and my runtime was more then that of O(xy)

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

Tomato

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

Is there a solution about dsu roll back for H2, can you help me?

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

H1 can be solved using RollbackUnionFind

Submission: https://codeforces.com/contest/1985/submission/265404470

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

The queuing time was too long. My solution for F got queued for 15mins, and gave wrong answer. I could have rectified it sooner :(

Hope codeforces fixes this :)

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

tomatoo

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

I have a friend who solved f using binary search and value of right 1e18 but it passes system tests.How?

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

    share code

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

        the guys is clever, i think it passes because he first performed the division then multiplication (in line 7 and 8), but i also got overflow because i multiplied both terms together and then divided, during multiplication of both then i might have got overflow.. any experts please reply after

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

          in Line 5:

          double totalDamage = 0;
          

          He used double to store the totalDamage,so there's no worry about overflow.

          in Line 7:

          double numAttacks = (turns + cooldown[i] - 1) / cooldown[i];
          

          the expression at right is at most 1e18 , also not overflow.

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

tomato

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

Its sad that being from India most of the cheaters and leaked solution are from my country although it does not affect my personal growth but it ruins the sportsmanship .. sad !!!

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

    nothing sad, colleges focus on rubbish curriculum poor faculties, such high competetion for low paying jobs too.. then kuch to chahiye resume me bharne ke lie. not supporting cheating but most people start in their colleges , cp needs time and dedication blood sweat. but then students should have to do dev also, core also. seeing this they have nothing but to cheat and get rating tag (specialist/expert)..

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

just out of curiosity i am asking... in the E question is there any mathematical way to find the optimal sides of the smaller box directly(in constant time or even if in O(N) time) rather than using nested loop?

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

    You can downgrade it from 3D to 2D, so if you can solve 2D version in constant time then you can solve 3D in linear time. In my opinion, the problem requires you to fix the shape first which I think may not be possible to have a solution faster than $$$O(min(min(x, y), \sqrt[]k))$$$.

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

tomato

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

265530894 This is my approach for problem F — Final Boss. I am fairly new to codeforces. I am not able to solve this error. Can anyone help why i am getting this diagnostics error?

Thanks

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

    Diagnostics detected issues [cpp.clang++-c++20-diagnose]: p71.cpp:37:20: runtime error: signed integer overflow: 9195700509336791281 + 60645102003290034 cannot be represented in type 'long long' SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior p71.cpp:37:20 in

    I am a C++ noob, but i think you need to use a bigger datatype for sum varriable.

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

    Basically your sum variable is overflowing. try to figure out a way such that it doesn't overflow.

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

tomato

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

For problem E,
Can any one explain for $$$h \lt 10^9$$$, why the given time complexity holds true? Why in $$$log$$$ there is $$$h * max c_i$$$?
Thanks.

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

    $$$h*maxc_i$$$ is one upper_bound of turns to kill the boss.

    It's easy to prove. If you only use the attack that have max cooldown time of all attacks , assume that this attack only takes 1 damage , after $$$(h-1)*maxc_i+1$$$ turns the boss will die. This is the worst case, so you know that in $$$(h-1)*maxc_i+1$$$ turns the boss must die. For $$$(h-1)*maxc_i+1 < h*maxc_i$$$ ,in convinient we use $$$h*maxc_i$$$ for the upper_bound.

    $$$log$$$ comes from binary_search approach.We use binary_search to find answer. You can find its time complexity proof on the Internet.

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

G:(D-Function) Can someone explain, why do we add mod in this print((pow(9 // k + 1, r, MOD) - pow(9 // k + 1, l, MOD) + MOD) % MOD) to the result of the difference?

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

    we know that pow(9 // k + 1, r, MOD) $$$\in [0,MOD-1]$$$ and pow(9 // k + 1, l, MOD) $$$\in [0,MOD-1]$$$

    so it's possible that in some cases we have (pow(9 // k + 1, r, MOD) < pow(9 // k + 1, l, MOD)

    To avoid print a negative value , we add a MOD to the result.

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

For problem G, how to prove the legal number n should be only that each digits of n multiple k have no influnance to the next digits.

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

    using $$$D(x+y) = D(x) + D(y) - 9*carry$$$

    To prove this formula , you can start with one digit , and it's correct. And you can expand this to all digits.

    so we have $$$D(k*n) = k*D(n) - 9*carries$$$ .

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

      What a prove!!! Pretty good, thanks.

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

for problem H1 could someone tell me why my code get tle? Is there anything wrong with my dsu? code

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

    there is a mistak in line 56, but it is still TLE after I correct it :(

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

tomato

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

Can someone explain why my submission 265271439 for problem C gives a TLE? It seems to be an O(n) approach. While I agree it's in Python, it would be helpful if someone pointed out what went wrong

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

From problem H2 what is wrong with the idea of taking maximum(first convert a row which gives maximum component size then convert a column which gives maximum component size, or reverse of previous).

I already implemented it and it fails at 5th sample case but I am not able to figure out why. I doubt its implementation mistake.

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

Does anyone get stack overflow in test 5 in Problem H2 in Java while implementing recursive dfs? In C++, it seems to be working (the author's solution uses recursive dfs). Any reason for this? Submission: 265565304

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

For problem F,
Can anyone help me to understand how $$$\lfloor{\frac{t - 1}{c}}\rfloor$$$ is derived?

Also, please let me know if it is a standard or generic way to calculate in such situations.
Thank you in advance.

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

    This is a typical data structure problem. Here is my solution: https://codeforces.com/contest/1985/submission/265355672

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    say c = Cool Down , t = Turns
    
    now attacks will be on the turns : 1 , 1+c , 1+2c , 1+3c . . . 
    so , kth attack will be on the turn : 1 + (k-1) * c
    
    say , till 't' turn , 'k' attacks has been done
    so => turn on kth attack <= 't' turn
       => 1 + (k-1) * c <= t
       => k <= (t-1)/c + 1
       => k = (t-1)/c + 1 (since division gives floor result, so we can just equate)
    
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

TOMATO!!

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

For H1 I am using a map of pairs called compNum which basically marks each '**#**' with its component number. I have taken key pairs because I need to store coordinate of '**#**' and the value of this map is component number. And at the same time using another unordered map<int,int>cnt I am counting the size of the current component number and using a visited matrix I am keeping track of whether the neighboring '**#**' is visited or not, standard dfs stuff. Then for each row I am placing '**#**' and counting answers as follows: FOr each row ri, if the cell contains '**#**' then using a map I am checking whether the component to which this cell belong to has already taken or not. The compNum map gives the component of this cell. And if it is not '**#**' then I increment the current answer by 1 because I place a new '**#**' in place of '**.**' and now I check four neighbors if any neighbor is '**#**' and its component is not taken then I add the size of the component to my current answer and proceed. Finally when I am done computing the value of the current answer for a row then I try to maximize my final ans with the current answer same stuff I do for columns. But I don't know why it is giving TLE. Any help will be appreciated. Thank you for spending time in understanding my approach.

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

tomato

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

265582011 H1: I have used DSU for solving H1. It works for testcase1 but gives wrong answer for testcase2. could someone pls lemme know where I wen't wrong. I have been printing and debugging the last 6 hours. thx!

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

For H1 problem I have solved the problem but getting TLE on testcase 2. Any idea why it is giving TLE ? According to me the complexity is somewhat O(mn log(mn) ). Please correct me if I am wrong in assuming the complexity

include <bits/stdc++.h>

using namespace std;

const int buf_size = 1e6+9;

bool vis[buf_size]; char grid[buf_size]; int grid_comp[buf_size]; int n,m;

void dfs(int i, int j, int comp) { // cout<<"dfs at index "<<i<<" "<<j<<"\n"; if(i<0 || j<0 || i>=n || j>=m) return;

if(vis[i*m + j] || grid[i*m + j] == '.') return;

vis[i*m + j] = 1;
grid_comp[i*m + j] = comp;

dfs(i+1, j, comp);
dfs(i-1, j, comp);
dfs(i, j-1, comp);
dfs(i, j+1, comp);

return;

}

int main() { // your code goes here int t; cin>>t; while(t--) {

    memset(vis, 0, sizeof(vis));
    memset(grid_comp, 0, sizeof(grid_comp));
    map<int,int> mp;

    cin>>n>>m;
    int comp = 0;

    for(int i=0 ;i<n; i++)
    {
        for(int j=0 ;j<m; j++)
        {
            cin>>grid[i*m + j];
        }
    }

    for(int i=0; i<n; i++)
    {
        for(int j=0 ; j<m; j++)
        {
           // cout<<grid[i*m + j]<<" ";
            if(!vis[i*m + j] && grid[i*m + j] =='#')
            {
                comp++;
                dfs(i, j, comp);
                mp[comp]++;
            }
            else if(grid[i*m +j] == '#')
            {
                mp[grid_comp[i*m + j]]++;
            }
        }
       // cout<<"\n";
    }

   // cout<<"dfs done\n";

    int max_comp_size = 0;

    for(int i=0 ; i<n; i++)
    {
        set<int> st;

        int changed_cells = 0;

        for(int j=0; j<m; j++)
        {
            if(grid[i*m + j] == '#')
            {
                st.insert(grid_comp[i*m + j]);
            }

            if(i>=1)
            {
                if(grid[(i-1)*m + j] == '#')
                {
                    st.insert(grid_comp[(i-1)*m + j]);
                }
            }

            if(i<=n-2)
            {
                if(grid[(i+1)*m + j] == '#')
                {
                    st.insert(grid_comp[(i+1)*m + j]);
                }
            }


            if(grid[i*m + j] == '.')
            {
                changed_cells++;
            }
        }

        int ans = 0;
        for(auto it: st)
        {
            ans = ans + mp[it];
        }

       // cout<<"row iteration "<<i<<" ans:"<<ans<<" changed_cells:"<<changed_cells<<"\n";
        max_comp_size = max(max_comp_size, ans + changed_cells);
    }

   // cout<<"iteration over row done\n";

    for(int i=0 ; i<m; i++)
    {
        set<int> st;
        int changed_cells = 0;

        for(int j=0; j<n; j++)
        {
            if(grid[i + j*m] == '#')
            {
                st.insert(grid_comp[i + j*m]);
            }

            if(i>=1)
            {
                if(grid[(i-1) + j*m] == '#')
                {
                    st.insert(grid_comp[(i-1) + j*m]);
                }
            }

            if(i<=m-2)
            {
                if(grid[(i+1) + j*m] == '#')
                {
                    st.insert(grid_comp[(i+1) + j*m]);
                }
            }

            if(grid[i + j*m] == '.')
            {
                changed_cells++;
            }
        }

        int ans = 0;
        for(auto it: st)
        {
            ans = ans + mp[it];
        }
       // cout<<"column iteration "<<i<<" ans:"<<ans<<" changed_cells:"<<changed_cells<<"\n";
        max_comp_size = max(max_comp_size, ans + changed_cells);
    }

   // cout<<"iteration over column done\n";

    cout<<max_comp_size<<"\n";


}

}

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

good round, thx, i got green

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

tomato

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

tomato

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

I used binary search on F and got hacked since I defined r = 1e18. Then I changed to 1e13 and it worked, but I don't know exactly why it's working, since if all turns are 1 and a[i] = n (for n = 2*10^5), the possible maximum would be n * n * 1e13 (divided by 2), which it would be approximately 1e23 which doesn't fit on long long int, can anyone help?

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

    You might be using a break statement while checking the binary search condition. If you use r = $$${10^{13}}$$$, $$${a_{i}}$$$ = $$${2 \cdot {10^{5}}}$$$ and $$${c_{i}}$$$ = $$${1}$$$. So as soon as the value is >= h you break out of the loop, and the value for the first iteration is $$${r \cdot a_{i}}$$$ which is around $$${10^{18}}$$$ that fits in the range of LONG LONG INT and you are able to successfully break out of the loop. Meanwhile if you use r = $$${10 ^{18}}$$$ then the value is around $$${10 ^{23}}$$$ for first iteration itself and it overflows before the break statement can come into action.

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

      I didn't use break on the for of the binary search, from what I calculated, this shouldn't be accepted, but I could be wrong https://codeforces.com/contest/1985/submission/265654152

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        if(somatotal >= h){
                    cout << "1\n";
                    continue;
                }
        

        Because of this initial pruning, you are able to ward off cases where all $$${a_i}$$$ are $$${2 \cdot {10 ^{5}}}$$$. So, $$${\sum\limits_{i = 0}^na_i < 2 \cdot {10 ^{5}}}$$$, is needed to go to binary search condition. You can easily check $$${r \cdot \sum\limits_{i = 0}^na_i}$$$ will not cause overflow for r = $$${10 ^ {13}}$$$ but for r = $$${10 ^ {14}}$$$ it will overflow.265655706

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

          Ohh that's true, I didn't even notice it when I did it. r = 1e14 overflows because it might reach 1e19. Thanks a lot!! I will pay more attention now with overflow when doing binary search

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

    i've posted my solution, please checkout the comment section... .you will get it

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

I tried solving H1. Why am I getting TLE on test case 3 ?? My solution is pretty much same as tutorial.

Someone Please check TIA!

Here is my code - 265512050

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

this is my BS solution for the "F"

#define ll long long

#include <bits/stdc++.h>
using namespace std;

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll test;
    cin >> test;
    while (test--) {
        ll h,n;
        cin>>h>>n;
        vector<ll>a(n),c(n);
        for(ll i=0; i<n; i++)cin>>a[i];
        for(ll i=0; i<n; i++)cin>>c[i];

        ll firstattack=accumulate(a.begin(),a.end(),(ll)0);

        h=h-firstattack;

        if(h<=0){cout<<1<<endl; continue;}

        ll turn=1;

        ll maxturn=1e18;
        ll minturn=0;

        while(minturn<=maxturn){
            ll mid=minturn+(maxturn-minturn)/2;

            ll sum=0;

            for(ll i=0; i<n; i++){
                sum+= (mid/c[i])*a[i];
                if(sum<0){sum=h+1; break;} // this is the condition for the overflow, very nice question
            }

            if(sum>=h){
                turn=mid;
                maxturn=mid-1;
            }
            if(sum<h){
                minturn=mid+1;
            }
        }

        cout<<turn+1<<endl;
    }
    return 0;
}
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

tomato

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

how does max function works for pairs in c++ pair <int,int> a = {1,2} ; pair<int,int> b = {2,1}; max(a,b) ; ?

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

Can someone tell me whats wrong with this submission 265677247

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

How to prove the conclusion of question B?

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

tomato

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

In the problem G floor(9/k) + 1 why we are adding +1

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

    floor(9/k)+1 is helping us find the number of distinct digits d we can place in a single position without making k*d overflow 9.

    For example for k=4, possible no. of d are 9/4+1=3 and these are d=0(4*0<=9),d=1(4*1<=9) and d=2(4*2<=9). That +1 is for the digit 0.

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

H1 : Can some explain this part?

            // Update prefix sums
            R[minR] += sz;
            R[maxR + 1] -= sz;

            C[minC] += sz;
            C[maxC + 1] -= sz;
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If you need to add x to a range (i,j) in an array, you can iterate from i to j and add x to each array element. This would be in the O(n). Now if you have m such operations, it will be O(m*n).

    So a better way to do this is to use this prefix array trick. To add x in (i,j), you can add x to pre[i], and subtract x from pre[j+1]. Now if you make the prefix sum array of this array, it will give you a value for each index that's added to each corresponding array element.

    e.g: arr[]={0, 0, 0, 0, 0, 0} i=1, j=3 (0-indexing) After operation: arr[]={0, 1, 0, 0, -1, 0} The prefix sum array: {0, 1, 1, 1, 0, 0}

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

tomato

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

tomato

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

How can i write the solution of F in python?

and yes....... tomato

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

    use heapq.

    from heapq import heappop, heappush
    t = int(input())
    for _ in range(t):
        h, n = map(int, input().split())
        a = list(map(int, input().split()))
        c = list(map(int, input().split()))
        q = []
        for i in range(n):
            heappush(q, (1, i))
        while h > 0:
            turn, i = heappop(q)
            h -= a[i]
            heappush(q, (turn + c[i], i))
        print(turn)
    
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

F, just use i128 in rust to avoid overflow, haha

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

I am wondering if it is possible to solve problem G: D-Function using digit DP? Has anyone solved it?

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

    not exactly digit dp but say $$$n$$$ = $$$[9/k]+1$$$, then possible numbers between $$$10^{l}$$$ and $$$10^{r}$$$ is simply

    Since the first digit of these numbers cannot be $$$0$$$, $$$= (n-1)n^{l}+(n-1)n^{l+1}+...(n-1)n^{r-1}$$$ $$$= (n-1)n^{l}(1+n+...n^{r-l-1})$$$ $$$= n^{r} - n^{l}$$$

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

tomato

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

How to prove first statement in solution of G?

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

Why did my rating do down? after 8 days

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

DSU solution for H2 gives TLE pls help

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

tomato Why tomato? why not apple or something ?

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

I tried to solve H2 but I got STATUS_STACK_OVERFLOW on test 5. Can anyone help, please? 266847431

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

tomato

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

tomato

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

In F,how to get the high value as 1e12 or 1e11 or 1e18 in binary search solution

»