VaibhavAgarwala's blog

By VaibhavAgarwala, history, 7 months ago, In English

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.

Full text and comments »

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

By VaibhavAgarwala, history, 8 months ago, In English

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.

Full text and comments »

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

By VaibhavAgarwala, history, 13 months ago, In English

Yes!

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

And it's not too bad to implement.

Full text and comments »

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

By VaibhavAgarwala, history, 14 months ago, In English

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.

Source — Problem 2

Thanks.

Full text and comments »

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

By VaibhavAgarwala, history, 15 months ago, In English

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.

Full text and comments »

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

By VaibhavAgarwala, history, 15 months ago, In English

How to solve this problem about coin changing? Btw, it has a short problem statement.

Thanks.

Full text and comments »

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

By VaibhavAgarwala, history, 19 months ago, In English

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

Full text and comments »

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

By VaibhavAgarwala, history, 19 months ago, In English

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

Full text and comments »

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

By VaibhavAgarwala, history, 20 months ago, In English

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.

Full text and comments »

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

By VaibhavAgarwala, history, 20 months ago, In English

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?

Full text and comments »

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

By VaibhavAgarwala, history, 20 months ago, In English

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?

Full text and comments »

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

By VaibhavAgarwala, history, 20 months ago, In English

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?

Full text and comments »

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

By VaibhavAgarwala, history, 21 month(s) ago, In English

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.

Full text and comments »

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

By VaibhavAgarwala, history, 21 month(s) ago, In English

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.

Full text and comments »

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

By VaibhavAgarwala, history, 21 month(s) ago, In English

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?

Full text and comments »

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

By VaibhavAgarwala, history, 21 month(s) ago, In English

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.

Full text and comments »

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

By VaibhavAgarwala, history, 22 months ago, In English

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.

Full text and comments »

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

By VaibhavAgarwala, history, 23 months ago, In English

Please help me solve the following problem:

Given N (N <= 100 000) small sets (size at most 7). find number of non-intersecting pairs among these sets.

Thanks for your attention.

P.S. I'm reposting this because the previous blog got heavily downvoted for nothing and does not get bumped up in the recent actions. Nobody has yet found the correct solution.

Full text and comments »

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