deinier's blog

By deinier, history, 5 years ago, In English

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.

Please advise.

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.

Read more »

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

By deinier, 6 years ago, In English

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?

Thanks in advance.

Read more »

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

By deinier, 7 years ago, In English

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.

Thanks in advance!

Read more »

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

By deinier, 7 years ago, In English

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

Read more »

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

By deinier, 8 years ago, In English

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.

Thanks in advance.

Read more »

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

By deinier, 9 years ago, In English

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!!!

Read more »

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

By deinier, 9 years ago, In English

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.

Read more »

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

By deinier, 9 years ago, In English

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.

Read more »

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

By deinier, 9 years ago, In English

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.

Read more »

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

By deinier, 9 years ago, In English

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.

Read more »

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

By deinier, 9 years ago, In English

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!!!!

Read more »

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

By deinier, 9 years ago, In English

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.

Read more »

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

By deinier, 9 years ago, In English

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.

Read more »

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

By deinier, 9 years ago, In English

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.

Read more »

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

By deinier, 9 years ago, In English

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

Read more »

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

By deinier, 9 years ago, In English

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;
       }
    }
 }

Read more »

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

By deinier, 9 years ago, In English

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;
  • }

Read more »

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