Можно ли обсуждать задачи? (а то тишина что-то)
Если да, расскажите пожалуйста как решаются задачи B, E, F.
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Можно ли обсуждать задачи? (а то тишина что-то)
Если да, расскажите пожалуйста как решаются задачи B, E, F.
Name |
---|
Unsolved:
I don't understand how you solve H. Could you be more specific?
I solved it using divide and conquer with bitset and a little heuristic.
But how to solve it in 4 mintes???
In I:
k=number of consecutive numbers
a=starting number
x=the number we want to get
x = a*k + k*(k-1)/2
Then i just thought
for a to 10e6:
for k to (while possible):
would pass XD
and it passed XD
assume gcd = g,
For G you can write a dp to calculate the worst case graph for number of shortest paths. The problem is to create a sequence of positive integers which sum to 34 where the product is maximized.
Here is the code in python:
The answer: (236196, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3)
or
236196 = 4 * (3 ^ 10)
yap, but at the same time, i think to choose/not to choose gold is a factor, but in this complete type graph that factor is 1, since you can always come back. So making a worst graph is a bit difficult, right?
This is the worst case graph for maximizing the number of shortest paths. This would be the worst case runtime for a brute force all shortest paths solution that used Dijkstra's Algorithm to pay back the necessary nodes.
There are many graphs you can make that require payback but they reduce the number of shortest paths in the process. So yes, depending on the solution, constructing a worst case graph is hard. :)
A solution that brute forces all shortest paths but then brute forces all gold usage on all shortest paths should TLE. I don't think the data is strong enough to break that solution. :(
A relatively complex, but non-hacky solution.
1) divide the nodes into levels according to BFS order from node #1; you can merge all levels starting from the one containing node #2 for convenience.
2) process levels in ascending order and apply the following dp:
dp(i, P) — maximum money we can get on the (shortest) path to i such that the current level of nodes has partitioning P.
Partitioning of nodes of a particular level means node arrangement into sets, where all nodes of a set are connected internally and disconnected from nodes in others sets. Two nodes are connected if there exists a path between them in a graph induced by nodes on current and all previous levels minus the nodes we have stolen gold from. Also, mark one or zero sets as special if the nodes in this set are also connected to node #1.
knowing dp(i, P), try all edges from i to j on the next level of nodes, and try both stealing and not stealing the money from i, and update dp(j, P) accordingly.
3) base case: dp(1, {{1}}) = 0
4)result: max of dp(2, P) over all P's, where node #2 is in the special set.
Hi! I already have an opencup account. I have tried "Sector admin tools -> Ejudge console"(under google translate XD), but didn't find recently contest. Could you tell me where to submit this contest's problem after the contest?
http://opentrain.snarknews.info/~ejudge/team.cgi?contest_id=9914
You can find all the problems from past 2013/2014 constests.
Oh, I have entered this page but didn't realize that it is the recently contest's problem…… Thanks a lot!