Блог пользователя cry

Автор cry, 6 месяцев назад, По-английски

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++)
Разбор задач Codeforces Round 952 (Div. 4)
  • Проголосовать: нравится
  • +113
  • Проголосовать: не нравится

»
5 месяцев назад, # |
  Проголосовать: нравится +33 Проголосовать: не нравится

tomato

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

F : Boss Fight Detailed Video Tutorial Priority Queues and Maps

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

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

got hacked on F :(

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hopefully rating changes will come out soon!

»
5 месяцев назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

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 месяцев назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

  • »
    »
    5 месяцев назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    +1 did the same

  • »
    »
    5 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    5 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Your comment literally says its because of overflow :D

        • »
          »
          »
          »
          »
          5 месяцев назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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 месяцев назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            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 месяцев назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              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 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      5 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Youtube Link this video might help you.

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Thanks for the editorial. I learned a lot.

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

tomato

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Was it a unrated contest??

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    5 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

tomato! got hacked on F ;(

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.me/contest/1985/submission/265355482

  • »
    »
    5 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Oh, that's interesting! Thanks!

      • »
        »
        »
        »
        5 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        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 месяцев назад, # ^ |
      Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

      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 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    5 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    265361398

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

tomato

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    5 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 месяцев назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      5 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      5 месяцев назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится

      neal did a very neat implementation using DSU.

      Link: 265272303

    • »
      »
      »
      5 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        4 месяца назад, # ^ |
        Rev. 6   Проголосовать: нравится +3 Проголосовать: не нравится

        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

  • »
    »
    5 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.me/contest/1985/submission/266763301

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

tomato

»
5 месяцев назад, # |
Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

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 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    5 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      The editorial contains bonus problem solution which uses 1e12

      • »
        »
        »
        »
        5 месяцев назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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 месяцев назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

tomato

»
5 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Fast Editorial!

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Tomato

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      5 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    5 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

tomato

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

tomato

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

tomato

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Нормально протестить за 3 недели не судьба?

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

what does tomato mean?

  • »
    »
    5 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 месяцев назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Tomato

»
5 месяцев назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

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 месяцев назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    Same. I just guessed it

  • »
    »
    5 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 месяцев назад, # ^ |
    Rev. 4   Проголосовать: нравится +7 Проголосовать: не нравится

    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 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    5 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Yeah shitty editorial.

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 месяцев назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Problem G was ProjecteulerForces XD

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

tomato

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

When will start System testing?

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Is there a formal proof for B?

  • »
    »
    5 месяцев назад, # ^ |
    Rev. 8   Проголосовать: нравится +14 Проголосовать: не нравится

    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 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

got hacked F, ha.

»
5 месяцев назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
5 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

write proof for G, please

  • »
    »
    5 месяцев назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    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 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

For G, i solved this problem by Matrix Multiplication

Spoiler
»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

WHen will ratings come out?

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

tomato

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Tomato

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

So how many testcases are there now in problem F?

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

tomato

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

tomato

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Meow

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

tomato

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

tomatooooo

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    5 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.me/contest/1985/submission/265647792

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

https://codeforces.me/contest/1985/submission/265300819 Why my sol for C got TLE in testing?

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Tomato

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

H1 can be solved using RollbackUnionFind

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

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

tomatoo

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    5 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    share code

    • »
      »
      »
      5 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      • »
        »
        »
        »
        5 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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 месяцев назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

tomato

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

tomato

»
5 месяцев назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    Spoiler
»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

tomato

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    $$$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 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 месяцев назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    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 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 месяцев назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

tomato

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 месяцев назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

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 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

TOMATO!!

»
5 месяцев назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

tomato

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

good round, thx, i got green

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

tomato

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

tomato

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 месяцев назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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.me/contest/1985/submission/265654152

      • »
        »
        »
        »
        5 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        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 месяцев назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Spoiler
»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

tomato

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone tell me whats wrong with this submission 265677247

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to prove the conclusion of question B?

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

tomato

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    5 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

H1 : Can some explain this part?

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

            C[minC] += sz;
            C[maxC + 1] -= sz;
  • »
    »
    5 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

tomato

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

tomato

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How can i write the solution of F in python?

and yes....... tomato

  • »
    »
    5 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    5 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

tomato

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to prove first statement in solution of G?

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why did my rating do down? after 8 days

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

DSU solution for H2 gives TLE pls help

»
5 месяцев назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

tomato Why tomato? why not apple or something ?

»
5 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

помидор

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

tomato

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

tomato

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

tomato

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

tomato

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

tomato

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

tomato

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

我是帅哥

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

tommato

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

tomato

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

tomato

»
3 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 недель назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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://codeforces.me/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...