Topcoder Single Round Match 661

Блог пользователя akulsareen

Автор akulsareen, история, 11 лет назад, По-английски

I usually like to wait for chrome or someone else to remind all you good folk about an upcoming SRM but it seems like they have forgotten. So here goes.

Hi there!

Tomorrow at 6:30 IST will be held Topcoder SRM 661.

Let's discuss problems after contest!

GL && HF.

topcoder, srm

akulsareen
11 лет назад
38

Комментарии (37)

Показать архивные | Написать комментарий?

noogle

11 лет назад, скрыть # |

Anyone knows about the goodies, rankwise or random?

→ Ответить

Zzyzx

11 лет назад, скрыть # |

Will you be able to wake up in time? :P

→ Ответить

const_int_magic

11 лет назад, скрыть # ^ |

real question is, how you are still awake? :P

→ Ответить

Xellos

11 лет назад, скрыть # ^ |

-8

(source: prequeladventure.com, go read it)

→ Ответить

akulsareen

11 лет назад, скрыть # |

Reminder for anyone who is awake but not registered. 5 minutes left till end of registration.

→ Ответить

I_love_Tanya_Romanova

11 лет назад, скрыть # |

+68

Congratulations to Swistakk on finally getting into top5 :)

BTW, can someone please explain where does that magic formula for div1 450 come from?

→ Ответить

Reyna

11 лет назад, скрыть # ^ |

+58

if you mean i(k — 1) + 1 then i can explain : we either take no edges for the i'th node then we can color it with k colors else we can take either of the (i-1) edges and since this nodes color can't be the same as the node where the edge is pointing we can color it with k — 1 colors thus it's (k-1)(i-1) + k = i(k-1) + 1

→ Ответить

I_love_Tanya_Romanova

11 лет назад, скрыть # ^ |

+34

Thanks... Now after your explanation it sounds so obvious and easy)

And I had to write a brute force to get the formula :(

→ Ответить

Reyna

11 лет назад, скрыть # ^ |

you're welcome xD it took a time for me to get it that's why i couldn't complete it :((

→ Ответить

tenshi_kanade

11 лет назад, скрыть # ^ |

+13

Yeah, similar situation here too. I came to a formula thas was wrong, coded it, forgot to add a couple of lines and it magically worked (yeah, coding it wrong fixed the formula). I was really lucky there.

→ Ответить

akulsareen

11 лет назад, скрыть # ^ |

Daaaamn. Just noticed that we had to pick only one edge. I was making a formula thinking if at the ith node I have degree 0, or degree 1, or degree 2.... to get a recurrence with binomial coefficients in it.

Is my misread version of the problem solvable?

→ Ответить

Reyna

11 лет назад, скрыть # ^ |

sounds pretty damn hard

→ Ответить

Sumeet.Varma

11 лет назад, скрыть # ^ |

i noticed it just after seeing your comment :(

→ Ответить

kingofnumbers

11 лет назад, скрыть # ^ |

to Sumeet.Varma and akulsareen:

it's always better if you check that you completely understand the samples before you start thinking of the problem, even if you think your self that you understand the problem completely

I learnt that lesson after one of my previous contest I participated

→ Ответить

pranshul

11 лет назад, скрыть # ^ |

Can somebody tell me what is the problem with this code for Div1 450? Thanks in advance!

int ColorfulLineGraphs::countWays(long long N, long long K, int M)
{
ll ans,term,times,start,end,y;
ans = 1;
for (int i=0; i<M; i++) 
{
	y=((i==0)?M:i);
	start = y;			// smallest x (1<=x<=N) such that x%M = i
	end = N/y*y;			// largest x (1<=x<=N) such that x%M = i
	if(end>=start)
	{
		term = (i * (K-1) + 1) % M;
		times = (end - start)/M + 1;	// how many x (1<=x<=N) such that x%M = i
		ans =(ans * power( term, times, M ) )%M; // (term^times) modulo M
	}
}
return ans;
}

→ Ответить

I_love_Hoang_Yen

11 лет назад, скрыть # ^ |

+152

Congratulations to Swistakk on finally getting into top5 :)

Plot twist: Petr forget to cover today's SRM

→ Ответить

sanban

11 лет назад, скрыть # ^ |

Whats your handle on TC?

→ Ответить

Emilbek

11 лет назад, скрыть # |

How to solve Div2 500?

→ Ответить

minimario

11 лет назад, скрыть # ^ |

← Rev. 2 →

Since constraint is only 11, we can simply iterate over all possible combinations of bridges to build and then run a Floyd-Warshall on each of them to find the diameter. (By finding max of distance between 2 nodes)

→ Ответить

Emilbek

11 лет назад, скрыть # ^ |

Thank you! minimario we were in one room. my handle is leon_kg on topcoder

→ Ответить

parash93

11 лет назад, скрыть # ^ |

Hey, can you explain the recurrence for div2 1000?

→ Ответить

LashaBukhnikashvili

11 лет назад, скрыть # ^ |

it's easy DP

→ Ответить

404Error

11 лет назад, скрыть # ^ |

You have to choose k elements out of n elements(k <= n);

So iterate from 0 to (1 << n), if number of set bits is equal to k , use all pair shortest path(floyd-warshall).

My implementation of Floyd was wrong which made me nervous and I could not complete in Time.

→ Ответить

fresher96

11 лет назад, скрыть # |

950 < 500 < 250

Div-2 contestants will understand -_-

→ Ответить

Xellos

11 лет назад, скрыть # ^ |

+18

Well, I did solve only 1000 in div1 :D (why did I have to misread 250...)

→ Ответить

Swistakk

11 лет назад, скрыть # ^ |

← Rev. 2 →

Positions of guys who have solved 1000 — 1, 2, 3, 4 and 63 xD

→ Ответить

sanban

11 лет назад, скрыть # |

How to solve div2 1000? Was there some magic formula there?

→ Ответить

misof

11 лет назад, скрыть # ^ |

Imagine that you are constructing the same graphs but in a different way: for each i between 1 and N, inclusive, you:

choose whether you want an edge from node i
if you do want it, choose where it points (i-1 possibilities)
color the node (K possibilities if you didn't draw an edge, K-1 if you did)

→ Ответить

sanban

11 лет назад, скрыть # ^ |

Now I think I should have spent a little more time on the 1000(in today's case 950) rather than the 500. :(

→ Ответить

parash93

11 лет назад, скрыть # ^ |

Okay, so for some i<=n, shouldn't the correct relation be

ans = ans * (k + (k-1)*(i-1)*k) ?

Where the second term means : Colour the current value in k ways, and have i-1 possible edges leading to k-1 different colours?

→ Ответить

fresher96

11 лет назад, скрыть # ^ |

no the recurrence is something like

f(1) = K, as we can choose one node with colour 1, 2, ..., K

f(n) = K*f(n-1) + (n-1)*(K-1)*f(n-1)

the first term is translation to: put the n-th node on the right side of the f(n-1) old graphs choosing its colour to be 1, 2, ..., K

and about the (k-1)*f(n-1) it is about: for some i in the range 1<= i <=n-1 (so there is (n-1) such i) put the n-th node and connect it with an edge to this i-th node we can do that only if n-th colour is different from i-th colour which allows to choose (K-1) colour

→ Ответить

parash93

11 лет назад, скрыть # ^ |

Yes, but regarding the second term, Shouldn't you select the current element's colour in K ways, and the for each of these colours, an edge which leads to the n-1 elements each with k-1 colours?

→ Ответить

fresher96

11 лет назад, скрыть # ^ |

yes I understand what you mean, the approach written above is about another approach from what you are thinking. In my opinion it is simpler. However if you want to solve it considering the idea you have, you have to change the definition of f(n), for the approach above f(n) = the number of graphs that can be constructed in the way mentioned in the problem statement (and have n nodes) using all K colours. Maybe for your approach you have to define something like f(n, m) = the number of graphs that can be constructed in the way mentioned in the problem statement (and have n nodes) using m colours or something else.

→ Ответить

noogle

11 лет назад, скрыть # |

Approach to solve Div1 250 plaease?

→ Ответить

Xellos

11 лет назад, скрыть # ^ |

Since LCM(N + 1..M)|LCM(1..M) (think why) and LCM is the product of maximum prime powers dividing some number in the respective ranges, you only need M large enough for any p^k that divides some number ≤ N (i.e. any p^k ≤ N, but you don't need this) to divide also some number x between N + 1 and M (the smallest such x), so M is the maximum of these x. Therefore, you just need to factorise all numbers up to N by the sieve of Erathostenes.

→ Ответить

Swistakk

11 лет назад, скрыть # ^ |

Btw, Can you prove that in fact we only need to consider p^k - > 2p^k and that all cases xp^k - > (x + 1)p^k are not needed? It is sufficient to prove that there is any power in an interval $\text{[math]}$ and that is in fact true even for just primes (maybe for sufficiently large n's), but it's some freaking hard math xd.