dustbite's blog

By dustbite, history, 3 years ago, In English

http://codeforces.com/contest/982/problem/D

I don't get why we need to add +1 to a[i]. I understand that we need to add if n = 1. But why do we need to do so in other cases?

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By dustbite, 4 years ago, In English
#include <vector>
#include <utility>
#include <cassert>
int main() {
    std::vector<int> vec;
    vec.push_back(0);
    int & r = vec[0];
    if (r == 0) {
        r = 1;
        vec.push_back(0);
    }
    assert(r > 0);
    return 0;
}

Find out why this code is dangerous :D

I became a victim of this problem while solving a problem using logic similar to the code shown.

Read more »

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

By dustbite, history, 4 years ago, In English

While solving problem F of 394 div 2 I needed to solve the problem, fill rectangle (a,b) to (c,d) with value V. There are Q queries of this form.

I need to find for each cell, the total value of it i.e. F[i][j] where F is the final array after all the updates are performed.

I extended the simple 1d method. to update range [l, r] set F[l] = F[l] + 1, F[r + 1] = F[r + 1] — 1, and taking cumulative sum.

In 2d, I took two 2d arrays, start[i][j], finish[i][j]

whenever i see a rectangle (a,b) to (c,d), updates are

start[a][b]++

finish[a][d]++

start[c + 1][b]--

finish[c + 1][d]--

Think of this method as when a segment from column b to d starts i.e. at a and when the segment should be removed i.e. at c + 1

Now for each row, I take cumulative sum as in 1d which is take cumulative sum of start[i][j] and subtract finish[i][j] when leaving the cell, also push start[i][j] and finish[i][j] down

This method works, but I have seen other methods while using just one 2d array.

Can anyone explain the method?

Read more »

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

By dustbite, history, 4 years ago, In English

Hello guys!!!,

I have been observing that without time constraint, I often feel lazy. So, I think I should first list few problems to solve and fix a time limit to solve.

So instead of using different timer, I'd like to use codeforces itself (if the feature is available).

I need the following feature.

  1. Create a list of problems(any two problems can be from different contests)
  2. Set time limit
  3. Start contest

This is similar to virtual contest except that I'd be the only participant of it. Also, if the codeforces judge stalls, it should automatically pause the timer.

Is this feature available?

Read more »

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

By dustbite, history, 4 years ago, In English

http://codeforces.com/contest/758/problem/F

Guys can anybody explain why the upper bounds for x and y for the ratio d = x/y is n-1 th root of 'r'?

I know it myself but I want to know what other coders think about it.

So basically explain why x <= power(r, 1 / (n — 1)) and y <= power(r, 1 / (n — 1))?

Read more »

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

By dustbite, history, 5 years ago, In English

http://codeforces.com/contest/439/problem/D

Ternary search can only be used on strictly increasing or decreasing sequence.

But, I think the problem is special in the sense that the search space is strictly decreasing first then some equal values and then strictly increasing.

Thus, ternary search can be used here. But I need to prove that if two f(p) == f(p + 1), then the value must be the answer (if f(p) == f(p + 1), f(p) = our_answer to the problem, in case f(p) = f(p + 1) for any p).

Read more »

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

By dustbite, history, 5 years ago, In English
 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By dustbite, history, 6 years ago, In English

Guys, please answer this, it won't take much time for those who have already solved this.

http://codeforces.com/contest/552/problem/C

In this problem, if X ≤ wk for where k is the largest possible, then we don't need to use all coins that have higher power than k + 1, i.e. coins wk + 2, wk + 3, ...wn will not be used.

To start with the proof, I will take wk + 2 first.

I need to prove that wk + 2 is not used in all of the valid solutions which means, wk + 2 doesn't occur either on the left or right side of the equation shown at the top. Now, if I could somehow prove that using wk + 2 in left side or right side, I cannot arrive at a solution I would be complete with my proof. I will first put wk + 2 in the left (along with X) and see. I have X + wk + 2 on the left, I also know that X ≤ wk. I can't work any further.

I am not able to prove how.

Ok, guys I got it!!!! (someone helped me). Here's a more easy proof.

Lets think a different way. What are the coin changes that I can make using wk + 2. What is the smallest such change? The smallest change is equal to when we put wk + 2 on the left and all smaller weights on the right i.e.

wk + 2 - wk + 1 - wk - .... - w0

wk + 2 — (wk + 2 - 1) / (w - 1)

But this amount is greater than wk.

Thus, if we use wk + 2, the change must be greater than wk. But, X ≤ wk. So, we can't make any such X. Proof is complete.

Read more »

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

By dustbite, history, 6 years ago, In English

We have two groups of nodes, group A consisting of N items, group B consisting of M items. There is an edge connecting node a of group A and node b of group B, where

a = i mod N

b = i mod M

where i is an integer.

Image description of the problem (http://codeforces.com/predownloaded/5a/b5/5ab5c142069cd987264c765383e682f622a7f0bf.png)

We need to find for each node if there is a path connecting to another node in the graph.

To create the adjacency matrix, I iterated from i from 0 to LCM(N,M) — 1, since after that, we would get same edge pairs. Now, discarding this approach, how can one find mathematically, if two nodes of the graph are connected by a path or not? This is actually my trimmed version of this problem (http://codeforces.com/problemset/problem/515/B)

The tutorial doesnot explain the GCD method to get O(N + M) complexity. I tried myself but couldnot go far. Any help regarding how it was derived will be immensely helpful.

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By dustbite, history, 6 years ago, In English

http://codeforces.com/problemset/problem/518/B

I wrote two naive solutions that should have both resulted in TLE. But one is showing wrong answer.

The only difference in both the solutions is that in Sol A, I mark the character to be removed as '0' whereas in the next one I actually remove the character from the string. But the solution in which I remove

the character is showing wrong answer instead of TLE. Could andybody explain what caused the judge to produce different decisions?

Solution A : TLE http://codeforces.com/contest/518/submission/11545724

Solution B: Wrong Answer http://codeforces.com/contest/518/submission/11545764

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By dustbite, history, 6 years ago, In English

http://codeforces.com/problemset/problem/482/A

if k = n — 1, all of the differences must be different and one of them is d = n — 1, which means 1 and n must come together. till now we have [1 n]

to get d = n — 2, either 1 and n — 1 would have to come together, or n and 2

so, [n — 1, 1, n] or [1, n, 2] are correct.

I know that adding each element greedily to [1, n] at the back i.e. [1, n, 2, ].... does work[or to the front]

[1, n, 2, n — 1, 3, n — 2]

But, how does one think through it during the contest? Is it grabbing pen and paper and trying brute force like

approach to find solution? That would take a hell lot of time (at least for me). But this was an specific case, [k =

n — 1] and using this case, general solution is obtained. So, is looking for some special cases a problem solving

strategy?

I cannot infer how people reach such a simple and sweet solution for such a seemingly complex problem.

Any suggestions would be helpful.

Read more »

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

By dustbite, 6 years ago, In English

(Actually this is a question) So I thought I knew the intuition behind the Manber and Myers algorithm. Here is what I understood.

Suppose the string is "banana"

We first partition the suffixes in terms of similar first character as

a, anana, ana => bucket 1

banana => bucket 2

na, nana => bucket 3

Then to get the partition by the next 2h characters, my algo is:

  1. scan each bucket one by one

  2. take the first bucket

  3. for each suffix in this bucket, find the position of sa + 2h, if we go out of bounds assign position = 0

So picture looks like this:

a = 0, anana = 3, ana = 3 (since a + 1 > n, nana is in 3rd bucket and na is also in third bucket)

  1. Now, sort the assigned indices of the bucket using counting sort.

  2. Scan the new indices one by one and create new partitions, here we get

[a], [anana, ana]

  1. Do this until buckets = n

My problem is in 4th part, where I use counting sort.

First I coded as I had thought that I had understood the algorithm. But then I ran into trouble. As the number of buckets goes on increasing during each iteration, my algorithm approaches O(n^2) (as I assign ranks during counting sort according to the location of s + 2h suffix). So with some modification to the algorithm can I get O(nlogn)? If not what should I do?

Ok. I removed the code. So please answer me now.

Read more »

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

By dustbite, 7 years ago, In English

I thought for many days about how do i solve this problem: http://codeforces.com/contest/475/problem/D But it seems to me that I cannot get any better than O(N^2). I think there is a knowledge gap(mathematics). I looked through the editorial too. But I cannot understand. I want to understand the solution. I even looked many of the submissions(using sparse tables, segment trees...). But staring the code doesn't seem to be beneficial(or may be I am too dumb for the problem). So, please help me solve this problem. I just want the idea. Thank you coders!

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it