Topcoder Single Round Match 669

9 years ago, # ^ |

← 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.

→ Reply

maksay

9 years ago, # ^ |

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.

→ Reply

rushilpaul

9 years ago, # ^ |

← 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.

→ Reply

beatoriche

9 years ago, # |

-9

going to be unrated because of d1 hard?

→ Reply

9 years ago, # ^ |

Doesn't look like it. My rating changed.

→ Reply

9 years ago, # ^ |

It is really strange decision.

→ Reply

9 years ago, # ^ |

Strange? To rate it?

→ Reply

9 years ago, # ^ |

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.

→ Reply

9 years ago, # ^ |

← 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.

→ Reply

9 years ago, # ^ |

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.

→ Reply

9 years ago, # ^ |

← 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.

→ Reply

9 years ago, # ^ |

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.

→ Reply

9 years ago, # ^ |

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

→ Reply

Egor

9 years ago, # ^ |

+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

→ Reply

-XraY-

9 years ago, # ^ |

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.

→ Reply

beatoriche

9 years ago, # ^ |

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

→ Reply

MikeMirzayanov

9 years ago, # ^ |

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

→ Reply

9 years ago, # ^ |

← 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).

→ Reply

Egor

9 years ago, # ^ |

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

→ Reply

9 years ago, # ^ |

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

→ Reply

-XraY-

9 years ago, # ^ |

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?

→ Reply

9 years ago, # |

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.

→ Reply

TerryMcGinnis

9 years ago, # |

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?

→ Reply

9 years ago, # ^ |

+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.

→ Reply

Madiyar

9 years ago, # ^ |

← 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

→ Reply

k0st1a

9 years ago, # ^ |

← 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?

→ Reply

Madiyar

9 years ago, # ^ |

← 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).

→ Reply

I_love_Tanya_Romanova

9 years ago, # ^ |

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.

→ Reply

Ferrumit

9 years ago, # |

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

→ Reply

ksurv

9 years ago, # ^ |

← 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.

→ Reply

dj3500

9 years ago, # |

+11

→ Reply

9 years ago, # |

→ Reply

9 years ago, # |

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

→ Reply

9 years ago, # ^ |

← 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.

→ Reply

k0st1a

9 years ago, # ^ |

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

Could you kindly shortly explain solution of Div1 Hard?

→ Reply

9 years ago, # ^ |

← 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)).

→ Reply