### VaibhavAgarwala's blog

By VaibhavAgarwala, history, 6 weeks ago, I have polygon and its vertices represented with randomly shuffled 2d points, how can I find the correct order?

In correct order I mean order so that segment between P[i] and P[(i + 1) % n] is a side of polygon.

Or if this is hard, how to solve it for 4 sides?

I'm looking for an efficient solutions. Many thanks.

By VaibhavAgarwala, history, 2 months ago, Let's add to Codeforces profiles (probably not directly) stats — how many times a person was exposed to share a same solution code with somebody, at least they won't cheat with main accounts.

By VaibhavAgarwala, history, 7 months ago, Yes!

Because we could collect some statistics like: What percentage of competitive programmers touch type?

And it's not too bad to implement.

By VaibhavAgarwala, history, 9 months ago, How to solve this problem?

Given an array of $n \leq 10^5$ positive integers ($\leq 10^9$) and an integer $m < 10^{14}$, find the subarrays with sum $\geq m$ and sum up their $min \cdot max$.

My Idea was to binary search from each position, then for a fixed $l$ we would have a range $[r_{min},n-1]$ of valid $r$-s. And then probably we need some kind of segment tree, but I wasn't able to figure out that.

Thanks.

By VaibhavAgarwala, history, 10 months ago, Hi, let's consider this problem.

If you have a connected graph with edges colored red or blue, to find out whether you can construct the spanning tree with exactly $K$ number of blue edges then — find the minimum number of blue edges that can be used, also find the maximum. If $K$ is in $[min, max]$ then it's possible, otherwise, no.

What is the proof of it?

I was thinking like this — If it is possible to construct the tree with $A$ vertices, and also with $A + 2$ vertices, then $A + 1$ is also possible, but why, how? Can we probably relate the solution with $A$ vertices to $A + 2$ vertices?

Thanks.

By VaibhavAgarwala, history, 10 months ago, How to solve this problem about coin changing? Btw, it has a short problem statement.

Thanks.

By VaibhavAgarwala, history, 14 months ago, The problem can be found here.

Abridged problem statement: You are given $n$ bandits and each of them you should give some number of keys (subset of $1$ to $k$) such that to get every key ($1$..$k$) you should use at least $m$ bandits and not less! What is the value of $k$?

By VaibhavAgarwala, history, 14 months ago, How do I prove that the Complete Graph with $n$ ($n$ is even) vertices can have as much as $n / 2$ disjoint spanning trees (spanning trees that does not share an edge between them)?

By VaibhavAgarwala, history, 14 months ago, Trying to solve this problem. I got the last non-zero digit by working with $2$-s and $5$-s, but here's an easier solution by using $10$ directly.

Can anyone explain why this works? How taking modulo $10^9$ does not make it wrong?

Code

Thanks.

By VaibhavAgarwala, history, 15 months ago, Recently I was solving the problem which said that I have to find the smallest number consisting of only 1-s (1, 11, 111, ...) which will be divisible by the given number $n$. This problem is easy, but I was surprised that it is possible for any $n$ not divisible $2$ and $5$. (at least for $<= 100 000$). How can I prove this?

By VaibhavAgarwala, history, 15 months ago, Given numbers $1$ to $n$, we have to make all those number equal to zero by choosing some subset and subtracting same value from all of them, we have to use minimum number of operations.

My idea was to always split it into two parts and get two {$1,2..n/2-1,n/2$} sets from {$1,2,..n$} set and continue like this recursively. This approach is correct and leads to $ceil(log_2(n))$ solution. What is the proof this being optimal?

By VaibhavAgarwala, history, 15 months ago, How can I include a header file without writing #include "header.h" for example using cmakelists.txt?

For example without writing #define DEFINE I defined it from cmakelists with the command add_definitions(-DDEFINE)

Can I do the similar thing?

By VaibhavAgarwala, history, 15 months ago, What is the proof of the fact that: if we want to traverse the tree with the minimal cost then we should traverse through the diameter, so visit diameter edges once and visit other edges twice.

This is kinda obvious, but I can't find the proof of it.

By VaibhavAgarwala, history, 16 months ago, How to solve this kattis problem? It is a multi-source but not once, one by one. You should count the number of vertices with the distance at least k after each source is added. Restarting dijkstra every time is not enough.

Thanks.

By VaibhavAgarwala, history, 16 months ago, Recently I was solving the problem from kattis and typed DFS solution and got Memory Limit Exceeded, then I typed exactly the same thing in C++ and got AC. After not figuring out the fix, I went with BFS and it passed (in Java).

This is my DFS:

DFS Code

This is my BFS code:

BFS code

Full Codes:

Full code - with DFS (MLE)
Full code - with BFS (AC)

What can cause this kind of thing?

By VaibhavAgarwala, history, 16 months ago, Please help me find the solution to this problem, which basically asks to find MST in grid which goes to all the columns from left to right. We can go to the adjacent cell in the grid (no diagonals).

There can be other solutions but I'm looking for one with Kruskal's or Prim's algorithm. Note that MST always has maximum weight edge as small as possible.

Thanks.

By VaibhavAgarwala, history, 16 months ago, Hello, I'm interested in the solution of "E — Coffee Central" from the following CF GYM contest. It's actually ICPC World Finals 2011 problem.

I've searched on internet but wasn't able to find the full solution. Some briefly mentioned you should rotate the points by 45 degree, but I don't understand why should I and how then proceed.

By VaibhavAgarwala, history, 17 months ago, 