cry's blog

By cry, 5 months ago, In English

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++)
  • Vote: I like it
  • +110
  • Vote: I do not like it

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

cry orz

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

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

»
4 months ago, # |
  Vote: I like it +20 Vote: I do not like it
»
4 months ago, # |
  Vote: I like it +2 Vote: I do not like it

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

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

    sadly this is not the case in palestine!

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

    This is because all of 1,000 nuclear bombs are false and Sparkle-sama only want to fool you, haha.

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

    orz

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

G reminds me of this JOISC problem

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

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

Won't we reach infinity by doing that?

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

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

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

Amazing xor-hashing solution for G, love it!

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

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

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

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

Submission

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

    You use map. Try replacing it with arrays and you'll be fine.

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

      yeah I also used a hashmap, but why would arrays be faster? I thought Hmaps had O(1) look up. Unless I'm misunderstanding smth

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

        STL Map has O(nlgn)

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

          Oh I use Python, is the python dict also O(nlogn)?

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

            no, average case is O(1), worst case is O(n)

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

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

  • »
    »
    4 months ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

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

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

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

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

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

cry sum Is there a penalty on unsuccessful hacking attempt?

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

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

Solved ABCD, hope to become pupil

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

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

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

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

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

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

DIV 3 — C

Easiest python implementation using 26 cross n array:

272842563

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

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

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

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

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

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

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

Great contest :) Hope to regain pupil title.

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

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

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

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

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

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

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

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

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

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

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

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

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

    Check my comment

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

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

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

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

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

Why is this code not working?

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

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

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

272886072

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

    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 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

      Yeah, true, but please communicate in ENGLISH.

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

非常难

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 months ago, # |
Rev. 2   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

Didn't understand G's train of thought

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

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

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

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://mirror.codeforces.com/contest/1996/submission/272913613)

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

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

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

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

我不到啊orz

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

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

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

D was such a head crusher

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

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

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

      what is upsolve??

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

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

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

Bruteforces

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

Thanks!

Great tutorial and problem idea for G

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

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

why i get wrong answer at test 4 ? 272990203

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

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

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

I can't understand the thinking of G

It's too hard for me

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

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

    There's a subroutine used in G which is standard and recently appeared in Atcoder ABC343F : Second Largest Query. I talk more about the idea in this video

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

      It took me 3 video explations for me to understand it, but yours finally made me snapped on the logic of the solution. Thanks a lot!

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

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

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

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

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

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

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

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

F is similar to ABC216E.

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

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

it's so hard

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

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

its difficult to understand D

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

E is a good problem

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

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 ).

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

    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.

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

Problem F was nice.

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

How long have you played Honkai: Star Rail? ww