| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | jiangly | 3810 |
| 2 | Benq | 3676 |
| 3 | Kevin114514 | 3655 |
| 4 | maroonrk | 3463 |
| 5 | strapple | 3447 |
| 6 | Um_nik | 3387 |
| 7 | heuristica | 3322 |
| 8 | turmax | 3317 |
| 9 | tourist | 3307 |
| 10 | jiangbowen | 3291 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 155 |
| 2 | nik_exists | 150 |
| 2 | maspy | 150 |
| 4 | Um_nik | 143 |
| 5 | Errichto | 139 |
| 6 | adamant | 137 |
| 7 | AmShZ | 136 |
| 8 | BledDest | 132 |
| 9 | maroonrk | 131 |
| 10 | qwexd | 129 |
The last blog got downvote bombed into oblivion, but I have enough contribution to spare.
TC SRM 638 takes place soon (ಠ_ಠ).
Feel free to discuss the problems here after the round ends (because TC apparently doesn't have placeholders for new matches in its forum anymore...).
I bet you are the problem setter today.
Actually, there's almost enough information to deduce this: https://apps.topcoder.com/forums/?module=Thread&threadID=826777 and related threads.
Some additional information: problems from that incentive were for SRM and TCO.
I have never used/read topcoder forums. Are they alive?
Holding on to bits of life, rather. There's something to be found occasionally (discussion of ACM WF problems, or this writers' incentive), but not much.
I must admit, the AC rates on 300 and 600 are similar to my 250. Only much, MUCH worse.
Start with the hard problem, they said... It's only 800, they said...
Still better than 250.
Everyone gets challenged (at least in my room...).
But everyone who opened the 600 beat me >.>
For the 300, what's the testcase that kills the solution which checks if the number of connected components is <=1 (instead of checking whether at least one of the components is "good enough")?
Edit: The check lots of people forgot is {"Y"},{"N"},{"N"}, but my question still stands.
Edit2: The testcase is {"YNY","YYY","YYY"},{"YNY","YYY","YYY"},{"YNY","YYY","YYY"}. Topcoder chat scrolled away so I can't see who to give credit to, sorry :(
is answer for this test: {"Y"}, {"N"}, {"N"} Impossible? Sorry for stupid question, but i just can't understand trick of this test.
Yes. The trick is that you would see the whole cube should be empty, therefore connected, and you'd think it's all ok if you don't check that it actually covers everything it needs to cover.
And what should be answer for the second? I suppose "Impossible" too?
The second should be possible. Even though the maximal shape is not connected, one of its connected components is good enough.
Thanks for the hint!
Some stupid stuff should pass, they said... It's only 300, they said...
TC apparently doesn't have placeholders for new matches in its forum anymore...
From Chat Room 1:
It seems that the nubmer of people solved 300 is nearly same as the number of who solved 600 :(
600 has around 80 successful solutions, 300 has around 55 (much less).
My sides.
How to solve 600?
Considered the largest wolf wolfi, if wolfj + wolfi ≤ limit,then this wolfj is free, it can be anywhere in the sequence. But somehow there are some wolves can only be in the left of the largest one, some should only be in the right. Now we get two small subproblems. You can use divide-and-conquer to solve it.:D
Consider f(start, end) = number of possible permutations on the subsequence [start — end]:
Otherwise: - Find the smallest wolf and remember its position min;
Find the largest range [minStart, min] such that minStart <= start and the sum of wolf[i] + wolf[min] <= maxSizeSum for every i in this range;
Likewise find the largest range [min, maxEnd] such that maxEnd <= end and the sum of wolf[min] + wolf[i] <= maxSizeSum for every i in this range;
Swap positions min and minStart;
The answer will be: f(start, minStart — 1) * (maxEnd — minStart + 1) * f(minStart + 1, maxEnd) * f(maxEnd + 1, end).
This is because in the range [minStart — maxEnd] for every i in this range wolf[min] + wolf[i] <= maxSizeSum so wolf[min] can occupy any position within this range but can't go outside this range. So you are left with calculating the number of possible permutations in this range such that wolf[min] isn't there and multiply by the length of the range because wolf[min] can occupy any position. Of course you still have to multiply by the number of permutation on the left and right side of this range which is f(start, minStart -1) and f(maxEnd + 1, end) respectively.
There is a simple solution. Find a smallest element. Find the number of places (it can go right and left as long as swapping rule is not violated) it can be in.Let it be k. Now, remove that element from the array.Let the new array be v' Answer is ans(v)=k*(ans(v') .
This is O(n^2) (using recursion,n steps at each level)
Credits : [user:msaikrishna17394]