miniluigi's blog

By miniluigi, history, 8 years ago, In English

Hello,

I have spent a good amount of time trying to debug 587C. However, I am getting WA Test 30.

There seems to be something wrong with merging (not necessarily the method itself), as in my answer I end up outputting a duplicate of each number in the second line of the Output on test 30

10 1 1 4 4 5 5 6 6 8 8

However, I believe I designed my code so that the code should not be merging overlapping vectors. If someone could be so kind as to help me pinpoint the error, I would be very thankful.

EDIT: User Benq helped me find the error; it was just because my LOG value was not big enough :(

Full text and comments »

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

By miniluigi, history, 8 years ago, In English

Hello, I recently solved Snail Trails (problem statement here, and I have no idea why my code did not TLE. In fact, it finished in 0.011 seconds on all test cases. To summarize my approach, it's a brute-force DFS on every possible option. Can anyone help me analyze the time complexity of my code? Any help and insight would be appreciated. Thanks!

Full text and comments »

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

By miniluigi, history, 8 years ago, In English

When I was coding a solution for 633E, I noticed that using

int log(int x) {
    int ct = 0;
    int k = 1;
    while (k <= x) {
        k *= 2; ct++;
    }
    return ct-1;
}

over floor(log2(x)) allowed my program to run in time. Could someone please explain to me why one is faster than the other? Thanks!

See here for my code and use compare to see that nothing else is different:

log(x): http://codeforces.me/contest/633/submission/18990265

floor(log2(x)): http://codeforces.me/contest/633/submission/18990181

Full text and comments »

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

By miniluigi, history, 8 years ago, In English

I have tried to use the Sparse Table Algorithm in order to compute the RMQ in this problem. However, this ends up timing out. I thought it was O(nlogn)?

http://codeforces.me/contest/689/submission/18959912

Full text and comments »

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