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

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

1996A - Legs

Problem Credits: cry
Analysis: cry

Solution
Code (C++)

1996B - Scale

Problem Credits: sum
Analysis: cry

Solution
Code (C++)

1996C - Sort

Problem Credits: cry
Analysis: cry

Solution
Code (C++)

1996D - Fun

Problem Credits: sum
Analysis: cry

Solution
Code (C++)

1996E - Decode

Problem Credits: cry
Analysis: cry

Solution
Code 1 (C++)
Code 2 (A Little Different) (C++)

1996F - Bomb

Problem Credits: sum
Analysis: cry

Solution
Code 1 (C++)
Code 2 (C++)

1996G - Penacony

Problem Credits: cry
Analysis: cry, awesomeguy856

Solution - Segment Tree
Code (C++)
Solution - XOR Hashing (by awesomeguy856)
Code (C++)
Разбор задач Codeforces Round 962 (Div. 3)
  • Проголосовать: нравится
  • +110
  • Проголосовать: не нравится

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

cry orz

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

Couldn't solve D. RIP my brute force skill.

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

After reading problem F You realize that nuclear bombs take so much time to bomb!

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

G reminds me of this JOISC problem

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

In problem F: We are searching for the largest x such that f(x)≤k

Won't we reach infinity by doing that?

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

My solution for problem F:

let's find the minimum number X, where X is the smallest number that all numbers in array a can be less or equal than using at most k operations.

then, you calculate the answer for making all the numbers in a less than X, and maintain values k and a[i] for each i.

After all you will be left with k operations, so you add to the answer : number_in_a_equal_X * k

link to my solution

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

    isn't that the same solution as mentioned in the editorial?

    oh, ohk i get it, you sped up the last part of solution by doing number_in_a_equal_X * k. That's good.

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

Amazing xor-hashing solution for G, love it!

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

great contest, really fun problems. i wish i managed to solve E on time as well but oh well

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

Can anybody tell why this solution for C is getting MLE?

Submission

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

please can anyone explain why my code works or if it can get hacked please hack it : ), i will be so happy (https://codeforces.me/contest/1996/submission/272827778)

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

    I think it can't be hacked because worst case I found O(2 * 10^9) , and it's fast enough for your code to pass because the operations sums and multiply aren't that heavy.

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

      If in the same code we replace int by long long, it gives tle on the first test case itself. Why is this the case?

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

        Arithmetic of long long (64 bits) is slower than int (32 bits)

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

Can anyone explain how this code works? I don't understand it. Also, can you provide some sources that explain how it works? Thanks! 272756177

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

cry sum Is there a penalty on unsuccessful hacking attempt?

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

Thank you for the editorial ! There is just a little typo in the explanation of problem E. You wrote in the line before the last one $$$(x+1) \cdot ((n-y_1+1) + (n-y_2+2) + ... + (n-y_k+1))$$$. It shouldn't be $$$n-y_2+2$$$ but $$$n-y_2+1$$$

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

Solved ABCD, hope to become pupil

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

O(n) solution of D :

wlog assume a <= b <= c

claim : atleast a, b <= √n

proof : if b > √n, b * c >= b * b > n which proves the claim so iterate on a and b till √n and count the permutations, this can be done in many ways

submission

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

Why will the "remaining operations will all add (x — 1)" in the solution for F?

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

    We know that there must be at least one element that is x-1, because otherwise it's clearly not the smallest x. Then, if there are less (x-1)'s than there are operations left, you could perform operations on those elements, and thus this not the smallest x. But if there were more (x-1)'s than operations left, then the they would all be (x-1).

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

    Let us note that $$$f(x - 1) - f(x)$$$ will mean how many element can start from $$$x - 1$$$ [check the last paragraph], because an increase in count between consecutive arguments can only occur if the smaller one is having some elements start for that argument,

    If x is the smallest value for which our $$$f(x)$$$ is $$$\leq k$$$, means $$$f(x - 1) > k$$$. This means that $$$f(x - 1) - f(x)$$$ number of elements have started from $$$x - 1$$$. We have $$$k - f(x) < f(x - 1) - f(x)$$$. Therefore the number of elements which will start from $$$x - 1$$$ is larger than the leftover operations.

    By elements starting from a number, I mean lets say $$$a_i$$$ = 7 and $$$b_i$$$ = 4, and $$$x$$$ = 4, then the AP of elements we can pull from this index is 7. Hence this element "starts from" 7. Also, within this example, consider what happens when $$$x$$$ = 3 (instead of 4), the AP of elements we pull is 7, 3. There is an increase in count from 1 to pulling 2 elements, and this change occurred because an element started from 3, (this 3 will not be pulled from this index if our $$$x$$$ is 4, but it will be ready to be pulled from the leftover operations).

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

DIV 3 — C

Easiest python implementation using 26 cross n array:

272842563

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

can anyone please explain me the editorial of Problem D "Since ab+ac+bc≤n , we know at the minimum, ab≤n . " or is their any other approach please share

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

    The constraint ab + ac + bc ≤ n implies that individually, each pairwise product should also be less than or equal to n . Thus, we know that:

    ab ≤ n , ac ≤ n , bc ≤ n

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

Did some people really did 4th one with brute force??

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

Why I'm Getting TLE 272870887 (problem C).

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

Great contest :) Hope to regain pupil title.

My math ain't mathing for D :( . What a mathy math

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

Anyone tried G with greedy then use segment tree? Like sort or pair by ascending order of min(b-a, n+a-b), assume a<b, then tried to input range [a,b] or [b,n],[1,a] to find which one is minimum. I do not know whether is works, as I tried sometimes but fail

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

Would a Randomizing Approach work for G? If you choose which edge to be deleted first there will be only one path which makes it clear which edges to remove after. Would randomly choosing the first edge to be deleted solve the problem (Assuming you only randomly choose from valid edges to be removed)? Too lazy to try coding it.

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

    no, consider the case where every adjacent points are friends except the two. in optimal answer only 2 of the edges can be removed so 2/n probability to choose right one

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

      I was actually thinking of only having the option to remove the edge from points that are not actually friends because it can be proven that either the answer is 1 or at some point you'd remove an edge from points that are not friends, I guess there must be a case that makes it fail but not on the top of my mind.

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

    That was my idea during the contest and it worked. However, I tried all possible edges to remove, not just by random.

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

in D, it is mentioned in the problem statement that the triplet (a, b, c) are positive numbers, i.e., > 0.

Given ab+bc+ca <= n, at minimum, ab+b+a <= n should be true, since c>=1 Which impliesb <= (n-a)/(a+1), instead of n/a as mentioned in the editorial.

When I apply these constraints, I get WA on test 2 for an unknown test case. Can someone please explain where I am going wrong ???

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

Can someone please explain why in problem 1996F - Bomb we need to add exactly (v*(k-all_ops)). In tutorials they just go through it and they don't even explain. I always trying to understand by myself till i'm done but its first time when im asking help(i watched all possible tutorials). My code 272878301 .

What i dont understand.
  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I guess there are \textbf{at least} $$$k - all ops$$$ values $$$=v$$$

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

    Like the other guy said, there would be at least k-allops values of v, because otherwise you could use the remaining operations to eliminate v and reach a smaller value in binary search

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

    Check my comment

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

    When we choose a value of x, the total count is less than k. However, when the threshold is set to x-1, the total count exceeds k. So, whenever I choose x, the total count is less than k. Other options always result in (x-1) every time because when we have b=1; b=(a[i]-x)/b[i]+1; we noticed that when we use (x-1), we always get (x-1) every time.

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

    Thank you guys. I guess yesterday was not the day for thinking because i woke up and instantly understood it.

    How i would explain this to somebody.
»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Anyone know any problems similar to D? If so can you recommend. Thanks in advance!

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

Why is this code not working?

为什么这段代码不起作用?

Почему этот код не работает?

このコードが機能しないのはなぜですか?

272886072

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

    First, don't use endl except the case which the problem is interactive problem(you will recieve an unknown verdict when you don't use 'cout.flush()' or sth like that, and endl will automatically perform cout.flush()). It is very slow.

    Second, you are outputing too much '\n'(ASCII 10)s. So even you switch it to '\n', you will still recieve a WA verdict.

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

    原来可以写中文的吗(雾)

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

非常难

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

Now i can't solve D just because i was thinking too complex... That's funny while I can solve E

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

Problem A is I think available on USACO guide or somewhere because I have solved same question with same problem statement.

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

F is equivalent to aliens' trick (A.K.A. wqs's binary search algorithm), for the functions mapping k (the number of operations) to answer (the maximum of sum selected by k operations) is convex.

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

Problem D provides an O(n) solution where no two numbers in a,b, or c are simultaneously greater than the square root of n, so the two square roots traverse a,b, find c, and then remove the duplicates.

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

HSR reference in the questions. Am I the only one?

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

For problem G there is an interesting property that if two edges (e.g. $$$(a,b)$$$ and $$$(c,d)$$$) cut with each other, they must connect to each other $$$(a,b,c,d)$$$. So finally we will reach a partition of a circle (here I indicate a partition of a circle means that there do not exist two edges which cut with each other in two complete maps of point sets), and we can find the answer quickly by some simple method.

The problem is how to find the partition of the circle. First, we sort the edges, and then we need to perform a stack of sets which indicates that all the points in a set needs to be connected. We can easily find whether an edge cuts an edge of a set. To lower the time complexity, you will find if we pile the stack by the time we build it, if the edge cuts with one set, all the sets which on the top of this set must cut with this edge. Then just merge the sets by size. The total time complexity is $$$O(n \log n)$$$.

I must mention that I haven't implement this, but I think it is an interesting approach of this problem.

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

    I am not sure if i not getting right what you are saying or your statement is false

    here's example for n=15, and 3 edges(1-4,3-6,5-15) according to your statement it should be connected by(1-3-4-5-6-15) but that would not be optimal solution(it should be 15-1-3-4-5-6).

    correct me if i am wrong.

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

      It's my bad not make it clear that I mean the points in a set means they should be connected by one path.

      In your example, for the edges $$$1-4, 3-6, 5-15$$$, they cut with each other, so they must be connected in a path. Both path $$$1-3-4-5-6-15$$$ and $$$15-1-3-4-5-6$$$ let them connected.

      If you still don't understand, you can see that if $$$(a,b)$$$ and $$$(c,d)$$$ cuts, we can add $$$(a,c)$$$, $$$(a,d)$$$, $$$(b,c)$$$, $$$(b,d)$$$ four edges and this does not change the answer, and that is what I mean "they must connect to each other". $$$(a,b,c,d)$$$ can be connected in many ways, like $$$a-b-c-d$$$ or $$$c-d-a-b$$$, but they must be connect by one path.

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

can anyone help why is this TLE ? problem 1996F - Bomb

Code

I literally cannot imagine edge case, feels like it should work logically

the idea is basically take the max of a[i] until it becomes smaller than second largest a[i] (if it exists)

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

    Your code will TLE in the case like this:

    Hack

    Where $$$n \ge 2$$$, and $$$k$$$ is sth very large.

    We have to compress these steps use binary search, then the rest "useful" operation will be at most $$$n$$$.

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

My thought process for C and D for newbies like me...

C

  • (obs) if we find the positions where the two sorted ranges differ we would be done
  • it was evident by the number of queries and input range that precomputation is required
  • but precomputation of where the two strings differ only if we don't have to sort each range...
  • (obs from examples) no need of sorting range, we just have to find that in the range which characters are extra in a
  • so precompute frequencies of all characters in the ranges:)
  • a hint could have been that it was mentioned only small latin chars

    D

  • (obs1): think of what the bounds on values of a,b and c are(makes sense as we need to find the count of possible tuples)
  • a,b and c can lie between 1 and min((n-1)/2, x-2) => O(max(n,x)^3) solution possible
  • (obs2): if we just iterate over a and b then number of tuples for given pair will be possible values of c and for this setup c is btw 1 and min(n-(ab)/(a+b),x-(a+b)) => O(max(n,x)^2)
  • (obs3 (which I missed in contest)) => ab is less than n so that gives us a bound on values of b too.(well this should have been obvious as otherwise why would we be given 2 inequalities one was enough for square complexity)
»
4 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

;

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

Didn't understand G's train of thought

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

    Here is the explantion of the solution with segment tree.

    So first we have a cycle of $$$N$$$ nodes.

    Then, it is obvious that when we force to delete an edge, this cycle will become a chain which can be assumed to be an array.

    And we just enumerate the edge we force to delete, then use sth fast to calculate the answer of the unique way to maintain the roads.

    And to do this, a segment tree is enough.

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

      I get it, because in the worst case there is a road that doesn't need to be repaired, so it's a matter of enumerating the roads that don't need to be repaired and then using the line segment tree to maintain the rest of the information

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

In problem F, I want to use slow solution for these remaining operations but get TLE on test 10. May I ask if there is any problem with this code?(https://codeforces.me/contest/1996/submission/272913613)

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

did anyone write the code for problem C in python. Mine is getting TLE

Code:

for _ in range(int(input())):
    n,q = map(int,input().split())
    a = input()
    b = input()
    dp1=[[0]*26 for i in range(n+1)]
    dp2=[[0]*26 for i in range(n+1)]
    curr1=[0]*26
    curr2=[0]*2
    for i in range(1,n+1):
        for j in range(26):
            dp1[i][j]=dp1[i-1][j]
            dp2[i][j]=dp2[i-1][j]
        dp1[i][ord(a[i-1])-97]+=1
        dp2[i][ord(b[i-1])-97]+=1
        
    for i in range(q):
        l,r=map(int,input().split())
        c=0
        for i in range(26):
            c+=abs(dp1[r][i]-dp1[l-1][i]-(dp2[r][i]-dp2[l-1][i]))
        
        print(c//2)
  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    for i in range(q):
            l,r=map(int,input().split())
            c=0
            for i in range(26):
                c+=abs(dp1[r][i]-dp1[l-1][i]-(dp2[r][i]-dp2[l-1][i]))
    
    

    u used same i,perhaps because of that ? i usually don't code in python, so is it allowed in python ?

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

在G题里面,为什么这样的维护道路方案是有效的? 我觉得sort道路长度的顺序应该也是可以的感觉

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

我不到啊orz

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

Problem E: why we have x+1 options as l? I think l should be in a range from 1 to x, then it's x , not x+1

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

Can anyone tell me how in F. How we came to know that all the remaining operation will add x-1 to the answer

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

D was such a head crusher

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

I am new and i was only able to solve A and B i solved C and F but until i wrote code time was up! Any tips how should i get better?

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

    bro, it was just your first contest , practice more , upsolve after each contest and start learning basics like binary search , prefix sums etc, you will definetaly improve

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

      what is upsolve??

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

        upsolve is basically solving those questions which you were not able to do during the contest, by using any help or looking at others solutions and looking at tutorials , its a great way to improve your cp skills

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

I have no idea how I'm getting a TLE from B. It was initially accepted, but it just got a TLE during the system testing phase. My solution looks similar to the one in the editorial, is there anything that I'm missing?

My submission

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

Bruteforces

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

Thanks!

Great tutorial and problem idea for G

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

D can also be done in a sort of O(n) complexity .

my approach was to deal with any 2 or more are equal in a separate case and all three distinct in a second case

well any 2 or more equal can easily be thought of in O(n) but for all three distinct without loss of generality

let's consider a>b>c

this means ab> c*c , bc > c*c and ac > c*c .

thus 3 * c*c < ab+bc+ac <= n

thus c can take a maximum value till sqrt(n/3) thus we can iterate over it's possible values in o(sqrt(n))

note : one must check if x is less than this sqrt(n) to get a faster code

now having fixed c let's think of b

ab > b*b , ac > bc thus , b*b + 2bc < n

now for each value of c we get an upper bound of b that can be calculated to be of the order of O(sqrt(n)) having fixed any 2 it's easy to calculate the number of possibilites for a

now since we are nesting 2 loops over O(sqrt(n)) the overall complexity would be O(sqrt(n) *sqrt(n))ie O(n)

My implementation : 272824868

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

why i get wrong answer at test 4 ? 272990203

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

There is an error in problem D's editorial i.e there should not be equality in a*b<=n and (a+b)<=x, although it also gets accepted but still this is logically incorrect since a,b,c are all positive numbers

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

Can someone please explain the difference in use case between the two binary search code?:

int l=0, r-INT_MAX, mid;
while(l<r){
  int mid = l + (r-l)/2;
  if(check(mid)) r = mid;
  else l = mid+1;
}

VS

int l=0, r-INT_MAX, mid;
while(r-l>1){
  int mid = l + (r-l)/2;
  if(check(mid)) l = mid;
  else r = mid;
}
»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I can't understand the thinking of G

It's too hard for me

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

Was G a standard problem? Can anyone share the standard problem or resource to learn about the idea if it was?

TY in advance.

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

In Problem F, why is it necessary that if any remaining operations, all those operations add x-1 to the final score? The condition for binary search was to add all scores as long as a[i] >= x, it may be possible that for an a[i] the final value remaining after all those operations is x-1 or x-2 or x-3... What am I missing here?

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

Problem D is such a low quality problem. I got hacked with verdict TLE but after the system testing I submitted same hacked code and got accepted . I was ranked 444(official) before hacked and finished at 2k+ after hacked . And lost my opportunity to be expert.

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

    All solutions at 19xx/2000ms? No, not a chance that the problem had a bad TL. You were having a suboptimal solution.

    $$$\mathcal{O}(n \log^2 n)$$$ time complexity is a very gray zone at $$$n \le 10^6$$$, and in most cases it should have been TLE'd long ago. It was only that this problem involved mostly basic arithmetics and virtually zero memory accesses that the constant factor tipped into your favor (partially).

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

      If I get TLE instantly in my first submission then maybe I could find an optimal solution. Which may guide me to Expert. Actually I am stucked in 1593 max. for a long time. That's why it hurts me a lot

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

Can anyone explain why when subtracting $$$f(x)$$$ from $$$k$$$, $$$k < n$$$ ?

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

In problem C, why do we have x + 1 options as 'l' for covering subarray [x, y]. As the array is indexed from 1 shouldn't it be x options?

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

F is similar to ABC216E.

The ABC problem is a version of $$$b_i=1$$$.

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

it's so hard

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

In problem f, how can it be proved that all excess operations over k (s-k) were done with the obtained ok (mid) of the binary search? Specifically how to prove the line, ans -= 1LL * ok * (s — k)

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

its difficult to understand D

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

E is a good problem

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

Can someone pls elaborate this? Not able to grasp this:

So, it suffices to run the slow solution for these remaining operations (as long as ai>0 ). Alternatively, we can notice that the remaining operations will all add x−1 to our answer (assuming x>0 ).

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

    Suppose f(x)<=k where x is the smallest number, then f(x-1)>k. Now why this is happening,you will be able to see that some value will be equal to x-1 and that will increase f(x-1). Now we have some extra move k-f(x) and for all this extra move we will find some x-1 to add in our final solution.

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

Problem F was nice.

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

How long have you played Honkai: Star Rail? ww