### deinier's blog

By deinier, history, 5 years ago,

I have a friend. He is trying to create a new account to start competing here. He is not receiving the confirmation email to activate his account. This is the second time hi is trying to create a new account without any success.

PS: I do not need to create a new account. I have been participating on regular codeforces round for the last 4 years. I do not need a fake account.

• +9

By deinier, 6 years ago,

Hi community!

I was requested to solve this problem few months ago in an onsite interview and I would like to know the best approach to solve it.

Problem statement:

You have a n * m grid with B (building), # (wall) and . (empty) and we want to know the coordinates i,j of a empty cell where the sum of the distances from all the buildings B to this cell is minimized. In each step you can move up, down, left and right. Each empty cell i,j is reachable for each building B.

My approach:

dist[i][j] -> sum of the distances from cell i,j to all buildings. (if we have B1 and B2 then dist[i][j] = distB1ij + distB2ij)

For each cell with a building B, apply BFS and increment dist[i][j] for all positions i, j reachable from B with the min distance from B to i, j in the grid.

Answer: min(dist[i][j]) where grid[i][j] is an empty cell.

Complexity:

O(n * m * (|V| + |E|)) where |V| is vertex amount (n * m) and |E| is edge amount (n * m).

at the end, I think my approach is O((n2)(m2))

My bad: I did not ask for any constraints. (Maybe I was a bit nervous that day)

Do you have another approach to this problem?

Am I wrong with this approach?

• +6

By deinier, 7 years ago,

Hi people,

What is the best approach finding the shortest distance between a point and a polygon or a route (route = first and last point are not connected)?

I think that the brute force here is take the shortest distance between this point and all the segments and It takes O(n) time where n is the segments amount of the polygon or the size of the segments set in the route, but ...

Can we do it better?

Is O(logn) possible if we know this segments set and we can store it sorted using some criteria?

Any hint or documentation will be appreciate.

• 0

By deinier, 7 years ago,

Is this SRM a private event or it will be a special SRM at this time?

• +3

By deinier, 8 years ago,

#### Hello community:

I am trying to solve B task in Abbyy Cup and I would like to know how can I build all the possible sums in an array of integers.

I am making all the components in the graph using dfs and I am using the PosF() function to get the position of X in its component.

At the end, I have a vector with the size of each component but I need to get all possible sums. Maybe it would be solved either by dp or by two pointers but right now I do not know how solve it.

It is something like this: Array of Components (I do not add the component that include X) = {3 8 1} and X is in the first position in its component -> Possible positions in the queue: 1, 1 + 1, 3 + 1, 4 + 1, 8 + 1, 9 + 1, 11 + 1, 12 + 1.

Here is my solution.

• +11

By deinier, 9 years ago,

Hi everybody: I don't know why my solution for Prob 550 div 2 fails in this test case. I am getting 2 as expected, and system test got 1. I got WA but maybe system test is wrong, (I don't think so). Thanks in advance.

I sent the same code now in practice rooms and I got 549.88 of 550. How it is posible????

Solution in ideone got 1 too as TopCoder System, for this test case. But, I don't see why!!!

• 0

By deinier, 9 years ago,

Hi friends, TopCoder Single Round Match 560 will be at 12:10 PM EST. Have a great contest.

You can also read this blog, it will be a great contest in Latin American.

• -20

By deinier, 9 years ago,

Hi everybody: I have a doubt. I don't know why this solution http://codeforces.com/contest/234/submission/2385675 gives me "Runtime Error" in test case # 1 while It is fine in my computer. I will appreciate your help. Thanks in advance.

• -11

By deinier, 9 years ago,

### Hi Friends:

We have other Topcoder contest. You can go to: http://community.topcoder.com/tc?module=MatchDetails&rd=15175 and register starting at 06:00 PM EDT. The contest will start 3 hours after. If you want to see quickly, what time will be in your country, go here: http://www.timeanddate.com/worldclock/fixedtime.html?&day=22&month=08&year=2012&hour=21&min=00&sec=0&p1=179. Have a nice day and enjoy in this contest.

• +14

By deinier, 9 years ago,

Hi, --- Remember that tomorrow will be this round in TopCoder. Here you have the link: http://community.topcoder.com/tc?module=MatchDetails&rd=15174. Registration will start at 06:00 PM EDT and the contest will be at 09:00 PM EDT. You can check the time for your country here: http://www.timeanddate.com/worldclock/fixedtime.html?&day=16&month=08&year=2012&hour=21&min=00&sec=0&p1=179. See you there and have a great contest.

• +40

By deinier, 9 years ago,

## Hi everybody:

Remember that tomorrow will be this round in TopCoder. Here you have the link: http://community.topcoder.com/tc?module=MatchDetails&rd=15173 and registration will start at 09:00 AM EDT and the contest will start at 12:10 PM EDT. You can check the time for your country here: http://www.timeanddate.com/worldclock/fixedtime.html?&day=04&month=08&year=2012&hour=12&min=10&sec=0&p1=179. Have a nice contest!!!!

• +26

By deinier, 9 years ago,

## Hi everybody:

Tomorrow will be this round in TopCoder. Here, I give you the link: http://community.topcoder.com/tc?module=MatchDetails&rd=15170. Have a nice contest and enjoy the EURO final game if you like football.

• +20

By deinier, 9 years ago,

#### Hi everybody:

Remember that tomorrow will be this round in TopCoder. Here, I give you the link: http://community.topcoder.com/tc?module=MatchDetails&rd=14739 and I wish you a great contest. Have a nice day and have fun tomorrow.

• +36

By deinier, 9 years ago,

#### He everybody:

I just want to remember that tomorrow will be this Topcoder's round. The link is : http://community.topcoder.com/tc?module=MatchDetails&rd=14738 and the registration will begin at 09:00 AM EDT. Good luck everybody and have a nice contest.

• +27

By deinier, 9 years ago,

Hi everybody: Next Thursday will be this round. Good luck and have a nice day. http://community.topcoder.com/tc?module=MatchDetails&rd=14737

• -18

By deinier, 9 years ago,

Hi, everyone. I want to know if the i — term (mod 1000000007) to the Catalan series could be calculated by this way. Do you, please, can explain me, if this way I get the answer by dp or if I need to do other thing? Thanks everybody.

fact[1][1] = 1;
for(i=2;i<=1000;i++)
{
for(j=1;j<=i;j++)
{
if(j == 1)
fact[i][1] = 1;
else
{
if(i == j)
fact[i][j] = fact[i][j-1] + fact[i-1][j-1];
else
fact[i][j] = fact[i][j-1] + fact[i-1][j];
fact[i][j] %= 1000000007;
}
}
}


• +1

By deinier, 9 years ago,

Hi, everyone. I want to know the i — term (mod 1000000007) to the Catalan serie and I really don't know if my solution works. Do you, please, can explain me, if this way I get the answer? I need some help, thanks everybody.

• long long c,n,i,j;
• long long fact[1005][1005];
• int main()
• {
• fact[1][1] = 1;
• for(i=2;i<=1000;i++)
• {
• for(j=1;j<=i;j++)
• {
• if(j == 1)
• fact[i][1] = 1;
• else
• {
• if(i == j)
• fact[i][j] = fact[i][j-1] + fact[i-1][j-1];
• else
• fact[i][j] = fact[i][j-1] + fact[i-1][j];
• fact[i][j] %= 1000000007;
• }
• }
• }
• scanf("%d",&c);
• while(c--)
• {
• scanf("%d",&n);
• printf("%ld\n",fact[n][n]);
• }
• return 0;
• }