alpenglow's blog

By alpenglow, history, 3 days 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?

Read more »

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

By alpenglow, history, 5 days 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?

Read more »

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

By alpenglow, history, 7 days ago, In English

How to solve 10022 — Delta-wave from UVa?

Read more »

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

By alpenglow, history, 2 weeks 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?

Read more »

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

By alpenglow, history, 3 weeks 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.

Read more »

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

By alpenglow, history, 4 weeks 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.

Read more »

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

By alpenglow, history, 5 weeks ago, In English

I am trying to solve 633 — A Chess Knight from UVa. I can not spot the mistake in my code. Basically what I do is I just do bfs from the starting cell and remember the last type of move (not to match with the next). I never revisit cells. However, it turns out to be incorrect (WA) I can't get why.

Code

Read more »

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

By alpenglow, history, 5 weeks 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?

Read more »

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

By alpenglow, history, 5 weeks 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.

Read more »

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

By alpenglow, history, 7 weeks 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.

Read more »

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

By alpenglow, history, 2 months ago, In English

I'm interested in the following — Why do we usually consider adjacent elements in exchange argument technique? It would have more sense to consider any two elements and then consider swapping them. I will try to explain what I want with a classical example from UVA: 10026

Here if we consider two events $$$A = (T_1, S_1)$$$ and $$$B = (T_2, S_2)$$$ and assume $$$A$$$ comes before $$$B$$$ in the optimal solution that is smth like this $$$...A,B...$$$

If we say $$$X$$$ is the time before $$$A$$$. Then having $$$A$$$ first and then $$$B$$$ (which is optimal as assumed) will contribute to the total answer $$$X * S_1 + (X + T_1) * S_2$$$ and placing $$$B$$$ before $$$A$$$ will give us $$$X * S_2 + (X + T_2) * S_1.$$$ Then solving the inequality which means that placing $$$A$$$ to the left of $$$B$$$ is optimal will give us $$$T_1 * S_2 <= T_2 * S_1.$$$

$$$X * S_1 + (X + T_1) * S_2 <= X * S_2 + (X + T_2) * S_1$$$ will give us $$$T_1 * S_2 <= T_2 * S_1.$$$

This means that in the optimal answer $$$A$$$ comes before $$$B$$$ means $$$T_1 * S_2 <= T_2 * S_1.$$$.

This is a right answer, but if we don't consider them to be adjacent we will have smth like this $$$...A...B...$$$ and again $$$X$$$ is the time before $$$A$$$ and $$$Y$$$ is the time between $$$A$$$ and $$$B$$$. Then we will assume the same but now with $$$Y$$$ and try to solve the following inequality to get $$$T_1 * S_2 <= T_2 * S_1.$$$

$$$X * S_1 + (X + T_1 + Y) * S_2 <= X * S_2 + (X + T_2 + Y) * S_1$$$

$$$(T_1 + Y) / S_1 <= (T_2 + Y) / S_2.$$$

We can not get $$$T_1 * S_2 <= T_2 * S_1$$$ from this inequality with even considering non-negative integers!

and what does it mean now?

I concluded that in Exchange argument we should always consider the adjacent elements or what? I don't think so, so what is the problem with my logic?

Read more »

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

By alpenglow, history, 2 months ago, In English

I remember many people suggested filtering rated/unrated contests on CF and they implemented it!

Check the rating graph and contests section.

P.S In the unrated section it shows every contest you've been registered for, this is not probably the best way imo.

Read more »

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

By alpenglow, history, 3 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.

Read more »

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