cry's blog

By cry, 6 months ago, In English

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

1985A - Создание слов

Problem Credits: cry
Analysis: cry

Solution
Code (C++)
1985B - Максимальная сумма кратных чисел

Problem Credits: cry
Analysis: cry

Solution
Code (C++)
1985C - Хорошие префиксы

Problem Credits: sum
Analysis: cry

Solution
Code (C++)
1985D - Манхэттенский круг

Problem Credits: cry
Analysis: cry

Solution
Code (C++)
1985E - Секретный ящик

Problem Credits: cry
Analysis: cry

Solution
Code (C++)
1985F - Финальный босс

Problem Credits: cry, sum
Analysis: cry, sum

About Hacks
Solution
Code (C++)
Bonus
1985G - D-Функция

Problem Credits: cry
Analysis: cry

Solution
Code (Python)
1985H1 - Максимизация наибольшей компоненты (простая версия)

Problem Credits: sum
Analysis: sum

Solution
Code (C++)
1985H2 - Максимизация наибольшей компоненты (сложная версия)

Problem Credits: sum
Analysis: sum

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

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

tomato

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

got hacked on F :(

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

Hopefully rating changes will come out soon!

»
5 months 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 months 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 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    +1 did the same

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

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

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

        Your comment literally says its because of overflow :D

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

      Youtube Link this video might help you.

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

Thanks for the editorial. I learned a lot.

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

tomato

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

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

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

Was it a unrated contest??

»
5 months 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 months 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 months 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 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

tomato! got hacked on F ;(

»
5 months 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://mirror.codeforces.com/contest/1985/submission/265355482

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

      Oh, that's interesting! Thanks!

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

          That makes more sense now :0

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

tomato

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

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

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

      Thanks, in a few hours ill study DSU then I'll sit and understand your solution soon. :D

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

      I used the same approach but how will you extend this approach for H2 ?

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

      neal did a very neat implementation using DSU.

      Link: 265272303

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

      i am using DSU but this code is giving TLE can you tell me why?

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

        Your code have overflow because your arrays parent and Size are too small when you want to iterate from 1, no 0 (but generally you want to have some reserve). Quick fix is setting MAX_N=4e6,also you can change i*m+j to i.e.(i-1)*m+j-1. On the other hand, i suggest to cin whole string rather than char (this is faster)

        string a[n+1];
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                cin>>a[i];
        

        (but then you iterate from 0), and you have a lot of 'shadow declaration' — your i.

        I wonder why you don't have SF

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

          thank for answer will try after contest. btw what is SF?

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

            Segmentation fault, but like runtime error

  • »
    »
    5 months 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://mirror.codeforces.com/contest/1985/submission/266763301

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

tomato

»
5 months 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 months 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 months 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 months 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 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The editorial contains bonus problem solution which uses 1e12

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

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

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

tomato

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

Fast Editorial!

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

Tomato

»
5 months 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 months 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 months 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 months 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 months 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 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ok , thankyou for your suggestion

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

tomato

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

tomato

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

what does tomato mean?

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

Tomato

»
5 months 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 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Same. I just guessed it

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

    Yeah shitty editorial.

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

Problem G was ProjecteulerForces XD

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

tomato

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

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

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

When will start System testing?

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

Is there a formal proof for B?

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

      Really intuitive and clear explanation, thanks a lot.

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

      3(2) = 2

      3(3) = 3 3>2

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

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

got hacked F, ha.

»
5 months 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 months ago, # |
  Vote: I like it +3 Vote: I do not like it

write proof for G, please

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

For G, i solved this problem by Matrix Multiplication

Spoiler
»
5 months 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 months 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 months ago, # |
  Vote: I like it 0 Vote: I do not like it

tomato

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

Tomato

»
5 months 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 months ago, # |
  Vote: I like it +3 Vote: I do not like it

So how many testcases are there now in problem F?

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

tomato

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

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

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

tomato

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

Meow

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

tomato

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

tomatooooo

»
5 months 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 months 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 months 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://mirror.codeforces.com/contest/1985/submission/265647792

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

      k <= 1e9?

      • »
        »
        »
        »
        5 months 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)

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

Tomato

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

H1 can be solved using RollbackUnionFind

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

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

tomatoo

»
5 months 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 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    share code

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

tomato

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

tomato

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

tomato

»
5 months 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 months 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 months 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 months 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 months 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 months 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 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What a prove!!! Pretty good, thanks.

»
5 months 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 months 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 months ago, # |
  Vote: I like it -8 Vote: I do not like it

tomato

»
5 months 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 months 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 months 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 months 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 months ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

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

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

TOMATO!!

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

tomato

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

good round, thx, i got green

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

tomato

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

tomato

»
5 months 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 months 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 months 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://mirror.codeforces.com/contest/1985/submission/265654152

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

tomato

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

Can someone tell me whats wrong with this submission 265677247

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

How to prove the conclusion of question B?

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

tomato

»
5 months 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

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

»
5 months 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;
  • »
    »
    5 months 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}

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

tomato

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

tomato

»
5 months 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

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

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

»
5 months 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?

  • »
    »
    5 months 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}$$$

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

tomato

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

How to prove first statement in solution of G?

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

Why did my rating do down? after 8 days

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

DSU solution for H2 gives TLE pls help

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

tomato Why tomato? why not apple or something ?

»
5 months 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

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

tomato

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

tomato

»
5 months 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

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

tomato

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

tomato

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

Can anyone explain me the C tutorial why is the equation mentioned even true ??

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

A harder variation of problem E. is "What's the sum of all the valid ways to place S for all valid S".

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

tomato

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

tomato

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

我是帅哥

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

tommato

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

To satisfy D(k*n)=k*D(n), each digit d in n must become k*d after multiplying n by k

In solution of G how do we prove it? Can't there be a case where k*n has higher number of digits and it satisfies the property?

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

tomato

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

still did not find out why it is optimal to take 2 except for 3, tried to do a recurrence relation but could not carry out the calculation, can somebody give me a solid proof ?

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

tomato

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

For H2, Note that doing this naively will pass because of low constant factor and the fact that we could not cut this solution without cutting slow correct solutions

I believe the following test case will blow up naive calculations for the subrectangle of B

Test:

Spoiler

Result: Prefix sum solution 277004120 = 400ms. Naive solution 277003713 = 3400ms (in practice AC with 400ms since this test is missing)

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

Thank's a lot ! It didnt end in "Time limit exceeded",which is strange...

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

cry and sum , hello sirs, really needed a help if you may. or if anyone else could, appreciated.

so., can anyone please help in letting me know whats wrong with this approach for 1985H1 — Maximize the Largest Component (Easy Version) ?

for a given row , i calculated for each # just above and just below it , the no of components its connected with , used a unique k-code , in the pair {no of connected components,k code of that component}

k code is only to identify unique additions in my count ct;

similarly i did for columns and thus have the ans.

submission: https://mirror.codeforces.com/contest/1985/submission/285054943

ik it is a bit messed up code but this is what i came up with and thought was a good idea nonetheless. if you could help me with it , it would be appreciated. thank you...