Topcoder Single Round Match 669

9 лет назад, # ^ |

← Rev. 2 →

Overall profit is $\text{[math]}$ . Given that it is easy exercise to notice that it is best to cut to almost equal sizes.

→ Ответить

maksay

9 лет назад, # ^ |

Informally: If at some point you have pieces of size (A1,...,Ak), to "assemble" them back into a whole slime would require sum of all pairwise products Ai*Aj, regardless of the order. Therefore, the optimum division into K parts is such that it maximizes the product. And that would be division into equal parts.

→ Ответить

rushilpaul

9 лет назад, # ^ |

← Rev. 5 →

Another proof for the division into equal pieces being optimal is if you have n = a+b, you need to maximize f(n) = a*(n-a) where 1<=a<=n. Differentiating that function wrt a and equating it to 0 to find maxima, you get d(an-a*a)/da = 0. You can apply that to the pair of variables in each term in your final expression to maximize the product of that term.

→ Ответить

beatoriche

9 лет назад, # |

-9

going to be unrated because of d1 hard?

→ Ответить

9 лет назад, # ^ |

Doesn't look like it. My rating changed.

→ Ответить

9 лет назад, # ^ |

It is really strange decision.

→ Ответить

9 лет назад, # ^ |

Strange? To rate it?

→ Ответить

9 лет назад, # ^ |

Yes it is strage, because somebody could take huge advantage. May be they asked all people who solved it today and none of them solved this problem before.

→ Ответить

9 лет назад, # ^ |

← Rev. 2 →

+15

Even if somebody knew it beforehand — how much did it affect whole contest considering that hundreds of people competed? It is a really often case that some problem appeared somewhere else (if I remember well — take a look at contests created by Bayan (not Thanks round) — almost half of problems there appeared somewhere earlier, bad luck) and I don't see many unrated contests because of that. We have to deal with fact that number of reasonable problems is finite and that birthday paradox is in fact true.

→ Ответить

9 лет назад, # ^ |

AT first everybody should try to avoid using well-known problems in contest. At second it is a big difference between problem "similar to some problem which was years ago" and completely the same problem, which was used on the same judge and probability that somebody knows it (and even has code for this problem) is very high.

→ Ответить

9 лет назад, # ^ |

← Rev. 2 →

I think that it didn't happen to me that I copied code and didn't change anything, but it happened few times that I copied code and slightly adjusted it, e.g. 5 lines out of 100 (once even one line in a really tough problem), which is still not what you want. Such unfortunate things happen, there is no way to prevent this in general and unrating contest for hundreds of people would be definitely too forward.

→ Ответить

9 лет назад, # ^ |

Btw, lol, don't know if you read this "exactly the same problem" http://community.topcoder.com/stat?c=problem_statement&pm=11155&rd=14552, probably not — if you did then you wouldn't be talking that they are exactly the same :P.

Indeed the problems are very similar, but you can't simply copy code.

→ Ответить

9 лет назад, # ^ |

Ok, you right, code is not the same, so all is ok.

→ Ответить

Egor

9 лет назад, # ^ |

+29

Well, as someone who participated in both competitions and solved this problem in both competitions — I had not remembered that problem during the contest and my solution is completely different from the one I used 4 years ago. Petr even hadn't solved it this time despite solving it 4 years ago

→ Ответить

-XraY-

9 лет назад, # ^ |

I remembered this problem and wrote the same wrong solution as in the previous srm.) It didn't pass pretests, and I finally got what I'd done.

→ Ответить

beatoriche

9 лет назад, # ^ |

Good then, because my 250 survived three challenges, including one from Petr xD

→ Ответить

MikeMirzayanov

9 лет назад, # ^ |

I didn't take part. What is the story about d1 hard?

→ Ответить

9 лет назад, # ^ |

← Rev. 2 →

It's a copy of a d1 hard from a previous srm here. (They have some slight differences, though the way to solve is basically the same).

→ Ответить

Egor

9 лет назад, # ^ |

Not exactly true. My solution specifically use condition that ratio of 2 consecutive coin values is at most 1000. As far as I know author solution uses this as well. So you cannot solve problem from 4 years ago using my current solution

→ Ответить

9 лет назад, # ^ |

Oh whoops, I had made the same assumption in my solution as well. Thanks for pointing this out.

→ Ответить

-XraY-

9 лет назад, # ^ |

I see the only problem with my solution: I count dp[k][sum] -- if we have k different types of ones, what's the number of ways to take exactly sum ones with less than m of each type. As you said m in the previous problem could be very large, so I need to count this value for only one pair (k, sum). Is there any formula? Or maybe I should think from different direction?

→ Ответить

9 лет назад, # |

Haha, 7 successful hacks (and 1 not), what a hacking spree for me :v. It is even more funny for me, because hacking anybody is a really rare case for me, recently I few times omitted hacking phase on purpose, because it happened to me few times that only thing I did was to unsuccessfully challenge somebody :P.

→ Ответить

TerryMcGinnis

9 лет назад, # |

Could someone tell me what is the error in the greedy approach of taking S and breaking it into two almost equal halves, keep them in a set and then repeat this process using the largest element present in the set?

Also, How to solve Div 1 B?

→ Ответить

9 лет назад, # ^ |

+11

Better question — could you tell me the proof of that solution? Solution is incorrect as long as you don't have a proof, not correct as long as you don't have a counterexample.

→ Ответить

Madiyar

9 лет назад, # ^ |

← Rev. 7 →

+27

Div1 B

Let's dp(n, x) = answer for the problem, if n is number of vertices of a graph, x is maximum cost of edge that this graph can have.

Let's associate cost x to edge of vertices i and i + 1 on a line. Every edge (u, v) where u <= i and v > i cannot have cost smaller than x, because we want (i, i + 1) to be in MST, thus they can contain costs between x..L

so dp(n,x) = dp(n, x-1) + sum dp[i][x-1]*dp[n-i][x] * (L-x+1)^(i*(n-i)-1)

UPD.
dp[i][x-1] to avoid counting one MST more than once.
Answer for the problem is dp(N, L) * fac(n) / 2

→ Ответить

k0st1a

9 лет назад, # ^ |

← Rev. 2 →

why do we have dp[i][x-1]*dp[n-i][x] but not a dp[i][X]*dp[n-i][x] ? I mean why we do not have dp[i][x] instead of dp[i][x-1] in your formula?

→ Ответить

Madiyar

9 лет назад, # ^ |

← Rev. 3 →

It is written in the bottom of my explanation. But I think it is hardly visible.

Shortly, you don't want to count the same MST twice, so the FIRST edge with associate cost x will be (i, i + 1).

→ Ответить

I_love_Tanya_Romanova

9 лет назад, # ^ |

Here is the test for you.

10 33.

You can reach 33 in two moves by dividing 10 into 7 and 3, and then 7 into 3 and 4 again. However, your greedy gives 10=5+5=5+2+3 with 31 points.

Trick is — you are interested in having almost equal parts (3-3-4 in this case) at the end of your process, not as a results of every single move.

→ Ответить

Ferrumit

9 лет назад, # |

← Rev. 2 →

Hi guys,

Could someone explain, what is mathematical proof of SRM669 Div2 500's problem's solution, so that it does not matter what numbers you would take in array, the result will be the same?

Thank you!

→ Ответить

ksurv

9 лет назад, # ^ |

← Rev. 2 →

Answer is always sum of the product of pairs. So it doesn't matter in which order you select two nos. Let say elements of array is a,b,c and d then ans is ab+ac+ad+bc+bd+cd. Proof directly comes from the distributive property of addition.

→ Ответить

dj3500

9 лет назад, # |

+11

→ Ответить

9 лет назад, # |

→ Ответить

9 лет назад, # |

what about Div2 Hard, I tried to right dp solution with the index of the edge and number of ones and twos as my state 120 X 120 X 120 but I found that its counting non-line MSTs too.

What is the right approach ??

→ Ответить

9 лет назад, # ^ |

← Rev. 3 →

Note, this is a solution to the harder Div1 version (an exponential approach will probably work for the div2 version, though I don't see what it is immediately now).

First, let's rephrase the problem. Instead of generating graphs, then counting line MSTs, let's generate line MSTs and count graphs.

A line MST looks like a permutation of the n nodes, where adjacent nodes are neighbors. There are a total of n!/2 ways to arrange the nodes (there are n! ways, but we double counted lines because it doesn't matter if we're going forward or backwards on the line).

So now, WLOG, we can label our line MST so it looks like 1-2-3-...-n (we'll multiply our answer by n!/2 afterwards).

Let dp[i][j] denote the number of graphs with i nodes and a line MSTs on 1-2-...-i, where the maximum edge has a value of at most j.

First, if no edges have value j, then the number of ways is just dp[i][j-1]. Otherwise, we can enumerate through all positions k where the first edge with value j appears. After determining this edge k, there are a total of dp[k][j-1] * dp[i-k][j] * exp(L — j + 1, k * (i-k) — 1) ways (this will be explained a bit more below). We can sum over all k to get our answer. Thus, this dp takes O(n^2*L) time.

Now, about the product I'll explain it as follows:

After we choose that the k-th edge has value j, all edges crossing the cut from {1,2,..,k} and {k+1,...,i} must have value at least j. Thus, there are a total of k*(i-k)-1 cross edges (not including the edge from k to k+1), and each edge has L-j+1 choices. This gives us the exp(L-j+1,k*(i-k)-1) term. Note that this follows from the cut property of an MST (any edge with minimum cost crossing a cut is included in some MST).
Since we said that k is the first edge with value j, all edges in {1,2,..,k} has value at most value j-1, so this gives the term dp[k][j-1]
Lastly, the remaining cut {k+1,...i} has a total of dp[i-k][j] (we can still use edges of at length at most j, and we relabel nodes so they're now {1,...,i-k} instead).

There's probably a much simpler method for div2 hard, since constraints are so much smaller.

→ Ответить

k0st1a

9 лет назад, # ^ |

Thanks for a such explanation! I finally understood the solution.

Could you kindly shortly explain solution of Div1 Hard?

→ Ответить

9 лет назад, # ^ |

← Rev. 2 →

+12

Sure. My solution is a bit complicated, so there is probably a way to simplify it. I'll present a very summarized version here. The key ideas for this problem are matrix exponentiation, so I hope you are familiar with that topic.

First, let's assume for simplicity that X is a power of M (i.e. X = M^k for some k). Now, in order to count distinct ways to sum up to X, we'll first order our summands in decreasing order.

Now, to make X, we can either just have the term M^k, or we can have M blocks that sum up to M^(k-1). Now, these M blocks must be in decreasing order, so we need to know what the first and last element of each blocks are. This suggests a dp approach with three states. That is, let dp[i][j][k] be the number of ways to make M^i where the first term is at most M^j, and the last term is exactly M^k (note each of the dimensions in this dp is at most log_2(10^18), which is about 60).

We can compute dp[i] almost as dp[i-1]^M. We need to modify dp[i] a bit to accomodate for the fact that we also have M^i that we can use as a summand (dp[i-1] only uses M^0,M^1,..,M^(i-1)).

Thus, to solve when X is a power of M, you can sum over all entries in the first row of the matrix dp[k].

To solve for general X, write X in base M. Suppose it's X = a_k * M^k + a_(k-1) * M^(k-1) + ... + a_0 * M^0. Then, the answer is the sum of the first row of all entries in the matrix prod(dp[i]^(a_i)).

→ Ответить