CQXYM's blog

By CQXYM, history, 3 years ago, In English

Yesterday, I took part in Codeforces Deltix Round Spring 2021 [Div.1 + Div.2], and happened something incredible.

I solved out the problem D and pasted the pretest(37), but I failed the system test(36).

My original code

Later accepted one

The two codes are almost the same. Though my algorithm is to solve the problem randomly, it shouldn't exit a the time of 1.6s. Is there something wrong with my original code, or is there anything else wrong with the platform?

Thanks.

Full text and comments »

  • Vote: I like it
  • +26
  • Vote: I do not like it

By CQXYM, history, 4 years ago, In English

It's so strange. I can never get to the link http://codeforces.com/problemset/problem/1304/D . But other links are OK. Can anyone tell me why or how I can solve it? Thank you.

Full text and comments »

  • Vote: I like it
  • +1
  • Vote: I do not like it

By CQXYM, history, 4 years ago, In English

Why can we put the option onto a segment tree? What do the segment tree do?

Thank you

Full text and comments »

  • Vote: I like it
  • -13
  • Vote: I do not like it

By CQXYM, 4 years ago, In English

Hello!

You may have met these kinds of problems that require you to calculate the prefix sum with modifying, and you can use a fenwick tree SUM in order to solve it. When you want to lower_bound on it, you can reference this way as follows: You wonder the minimum index in the array SUM[L~R] satisfied SUM[index]≥K.

Set l=0, r=R, mid=R three pointers as the left, right, middle.
If log2(r-l) is a positive interger, mid = (r - l)/2, or mid = pow(2, ceil(r-l) ) + l.
If SUM[mid]≥K, r = mid, or l = mid.
Continue to do it if l < mid < r.
In the end, index = mid.

The Picture

For this algorithm, it's not difficult to prove that the time complexity is about log2(R). You can understand it better with the help of this picture. And also you can solve such problems with a segment tree If there is something wrong with my algorithm, please tell me. Thanks.

Full text and comments »

  • Vote: I like it
  • -31
  • Vote: I do not like it

By CQXYM, history, 4 years ago, In English

Can anybody tell me how to solve 1055F this problem with a 01-trie? I can't understand the algorithm's idea

Full text and comments »

  • Vote: I like it
  • +3
  • Vote: I do not like it