Tomorrow, SRM 629 will be held at 11:00 EDT. This SRM is 3 weeks after the previous one (SRM 628 was on Jul 22, my birthday :D ). 3 weeks without TopCoder (except TCO14 Round 3), I'm sure that many people and I miss TopCoder too much! A sad fact that the number of SRMs is decreasing recently. After some months with 4 SRMs each, July has only 2, August has 3, and it's still not sure about next months. I don't know the reason, but it will be a great pity if there aren't any more SRMs.

I like some SRM rules. The one I like most is that the ratings will change if we open a problem. This forces us to try our best to solve problems, or our ratings will decrease much (we can't keep our ratings unchange by not making any submissions). The next one is value of a problem starts decreasing when we open it (not from the beginning of the contests). We don't have to choose which problem to solve first, and next. I also prefer to have coding and challenging phase separately, since the cost of challenging will be reduced.

I hope there will be more SRMs in the future, as many as recent months. Wishing you a wonderful SRM and high rating. Don't forget to share your thinking about TopCoder and discuss the round problems here AFTER CONTEST ENDS.

Thank you.

So long time with no SRMs, and now we have just two SRMs ;)

"Two SRMs"? What are they?

SRM 629 and SRM 629.

wtf 2 shens!?!?!

SRM 629 and SRM 629 and both will be held at the same time :D

Actually I like Codeforces challenge rule more, because 1. You need a good "sense of hack" — that is, to notice some problems have some tricky point, if you lock problem early and start hacking you can get a lot more opportunity; 2. If someone else hacks you then you still have a chance to correct it (Of course lost some points, but better than nothing :p)

just after

coding phaseended, the arena went dead and now it is not opening forchallenge phase.is anybody else having this problem?

Challenges work well for me.

First time competing on TopCoder, lost 50 points from challenging correct codes. -.-

i had a good test case ready to challenge

Div-1 250, and my friend just told me that there were7 successful challengesin my room.how unlucky for me! :(

I think it happened for all people of our college . My arena went down during challenge phase too .

My arena did not go down. I tried challenging my own solution as I realized it was wrong(but it was not allowed, of course).

firstly, i am not in college at the moment.

secondly, i'm not sure about "all people of our college". venk13 (the same friend i mentioned)

isin college now, and he told me that everything was working well for him during the challenge phase (albeit he hadn't registered, and was just watching).There are so many successful challenges. The problem B is too hard for me. Are there any ideas about B?

I have no idea why we can't buy 6 candies of the 0th shape and 11 candies of the 2nd shape. Can somebody explain, please?

If you buy 6 candies of the 0th shape, they might all be of flavor 1 and thus you don't have anything for flavor 0.

Should have been replace

`cost[i] = Math.min(Number1[i], Number2[i]) + 1`

with`cost[i] = Math.max(Number1[i], Number2[i]) + 1`

T_TSame thing, but I have one more bug :)

Lol, it is much more complicated than that xd. You need to consider also "left cost" and "right cost", but my solution also hasn't passed xd.

Sure, but it made me to stare at the sample like for 15 minutes. The things could go much better without this bug)

I made a graph with costs ( edge from type1 <-> type2 with cost min(number1,number2)+1 ) and tried to add and replace edges increasingly by cost.

I have no idea what is the good abordation. Maybe some DP. I am not even sure I got the statement right.

i tried doing it with MCMF, but got successfully challenged ): the guy who challenged me did some DP i couldn't understand

How to make the flow network ?

i did this steps:

put edges from source to tastes with cost=0 and cap=1

put edges from tastes to target with cap=2 and cost=0

put edges from tastes to sizes with cap=1 and cost=amt of the other type of candies +1

(Tricky part here, probably where I got it all wrong) i've created a dummy vertex for each size and assigned edges from tastes to this w/ cost=0, cap=1, and from this vertex to its taste with cap=2 and cost=max(num[i],num[j])+1

EDIT: I realize now that it wouldn't work...

For each candy with the same shape, You have four options, get T1 flavor with cost N2+1, get T2 flavor with cost N1+1, get T1 and T2 flavor with cost max(N1,N2)+1, or get nothing, knowing this we could build a graph with edge (T1,T2), with special properties that each component will have exactly one cycle, which could be solve using dp tree.

Unfortunately, i didn't have enough time to debug my solution during the contest :(

EDIT : just realize that each component will be a simple cycle... which means it could be solved using linear DP :( , got mixed up with with another special case graph where each vertex have exacty one outgoing vertex...

Well I thought we must buy max(N1,N2)+1 or nothing, but that was wrong...

my solution can't even pass pretests

We can buy 0, min(N1, N2) + 1, or max(N1, N2) + 1;

I missed that point min(N1,N2)+1. Then I reduced the problem to vertex cover of set of cycles. But actually it's possible only to choose one vertex(by min(N1,N2)+1), so it got WA.

Yes, Vertex cover doesn't work here, because if we buy min(N1, N2) + 1 then there is a one condition must hold to another shape.

what would be the answer on this graph? I didn't get that.

it was to compute minimum vertex+edge cover of the graph.

for each vertex v, the weight was minimum cost to get flavor v

for each edge u-v, the weight was minimum cost to get flavor u and v

Why is that ? ( "each component will have exactly one cycle" )

EDIT : It's ok. Saw andreyv's comment. ( and read again the statement )

because all vertices in the graph have two degree, but i don't really know to prove it

EDIT : i was wrong, it will be a simple cycle :(

I had this idea. Consider a graph where the vertices are shapes, and two vertices are connected if both shapes can have the same flavor. Then notice how each vertex has exactly two neighbors, and thus the graph is a collection of simple cycles. Consider one such cycle. We need to choose some of its vertices so that each edge is connected to at least one chosen vertex. If we choose one cycle's vertex as first, we can run linear DP from it: on each step

iwe either take the vertexiand DP value from vertexi- 2, or we don't take the current vertex and use DP value from vertexi- 1. Then there is some trickiness at the end, when the last vertex is connected to the first. And the cost of taking each vertex ismax(Number1[v],Number2[v]) + 1.I couldn't finish the solution in time, so I don't know whether it's correct.

This does not pass the last sample case.

This is correct, except that you have to take into account one more thing.

If you buy Number1[v]+1, you are guaranteed to get at least one candy of type Type2[v]. In your graph, you can treat this as self-edges and modify the DP accordingly (the recurrence is very similar).

Observation:

Let's flavor

iconnected with shapeaandb. shapeaalso connected with flavorj, b also connected with flavork. Let's denote W(a, i) -> number of candies of shapeaand flavori.When we may not buy flavor of type

i?When number of bought candies of shape a <= W(a, j) because we can buy all flavor type of j and When number of bought candies of shape b <= W(b, k)

For every

shapea, there are two equationsmustn't hold:Assume they are:

a <= i && b <= j

a <= k && c <= l

So possible values of a: 0, min(i,k)+1 and max(i,k)+1

Graph can be divided into several circles, because every vertex has exactly two children. We can do dynamic programming on that circle.

Waiting for editorial of 950-problem. Maybe xiaodao will help me?

here

FST!

:((

how to solve Div 2 1000? No one in Div 2 got it :(.

I would like to know why my solution for 550 div 2 works. For each person, I take his density

d=weight[i] /Volume[i] and calculate the sum of the differences with this density . I take the minimum of this sums. At the end, I got Accepted and I saw a lot of solutions with the same idea. Why is this a correct idea? I thought about the average density at first but It didn't work. Thanks in advance.I used the same approach and it worked( don't know why), but first I approached it with minimizing sum of squares ( to minimize this-> |a1-d*b1| + |a2-d*b2| ... I tried to minimize this function-> (a1-d*b1)^2 + (a2-d*b2)^2) like it is done in linear regression using differentiation, but it did not work. Can somebody also explain why this approach was wrong? Thnx

did the same thing here... this is what i am trying here:

(

weight_{i}-d*vol_{i})^{2}=weight_{i}^{2}- 2 *d*vol_{i}*weight_{i}+d^{2}*vol_{i}^{2}, soIf we call , , , we have a parabola:

a*d^{2}+b*d+cThis function will never be negative, since it's just some algebraic manipulation from a sum of squares, so it must be convex and it's critical point must be it's minimal. we just have to derive

a*d^{2}+b*d+cand equal it to zero to find the density to which it's minimal:I wish someone would point out what's wrong with this ):

Your problem is on the very first line. It is simply not true that minimizing the sum of the absolute values is the same as minimizing the sum of the squares, and I wonder why you thought that.

Example: the minimum for the sum

f(x) = |2 -x| + |3 -x| + |10 -x| is 8, which happens for x = 3.The minimum value for the sum

g(x) = (2 -x)^{2}+ (3 -x)^{2}+ (10 -x)^{2}is 38, which happens for x = 5. We can seeg(3) = 50 is not optimal.ah, my line of thought was exactly this one:

If , I can just ignore this root and work with the square.

We have to minimize function f(x)=sum(i=1..n, abs(x*volume[i]-weight[i])). So, we have to find its extremum. One easy idea of proof if graphical =) If you draw this function, you can see that it consists of segments connecting points (d[i],f(d[i])), where d[i]=weight[i]/volume[i], i=1..n. On each interval between these points our function is linear.

A possible thought for this problem:

Expand |ax + b| to |x + b/a| + |x + b/a| + ... + |x + b/a| (a items) For example, |2x-3| + |3x-6| + |x-7| = |x-1.5| + |x-1.5| + |x-2| + |x-2| + |x-2| + |x-7|

In a result the question become to find the median of {1.5,1.5,2,2,2,7} (assume you may know the fact). So the best value of density will occur among weight[i] / Volume[i].

Best explanation. Thanks! I had this intuition that it has got something to do with the median. I took the coefficient of x out but did not know what to do then.(Though I got it accepted by working out the answer from the test cases).

Maths is awesome!

Solution of Div.2 hard problem:

First, if

x= =y, then obviously answer is 0. So assumex>yLet

rem= money left on dayt,cur= candies left on dayt(both taken at noon);Initially

rem=xmody,cur=xdivy.Then, since

x>y, aftercurdays Alice buys anothercurcandies, her money left will increasecur* (x-y), and letdiff=cur* (x-y); Notice that ifrem+diff≥y, Alice will actually buy more candies.We will split into two cases then:

if

rem+diff<y, Alice needsperiod= ⌈(y-rem) /diff⌉ times to iteratecurdays untilcurincreases. In such case,curonly increases by 1 afterperiod*curdays;if

rem+diff≥y,curimmediately increases aftercurdays, and becausediffcould be very large becausecurwill increase, we need modulars here. Aftercurdays, Alice will getrem+diffadditional money if she still buys onlycurcandies, socurwill increase by (rem+diff)divy, andrem= (rem+diff)%y.The first case takes

period*curdays, and second takescurdays. If days left < days to be taken, we should calculate the final result and terminate. The result is trivial: in first casefinalResult=rem+ (daysLeft/cur) *diff+ (daysLeft%cur) *x, in second case it's justrem+daysLeft*x. If days left ≥ days to be taken, we will keep iterating the process.Complexity analysis: Both cases can be done in

O(1), so we just care about number of iterations. After one iterationcurincreases by at least 1, thus afterkiterations days passed = Ω(k^{2}), so running time for one test case is , enough to pass all tests.Code in C++

PS: This is the first time that I try to write a solution with

Unable to parse markup [type=CF_TEX]

and I was reading AoPS LaTeX tutorial while I was writing this solution... BTW, I think that tutorial is very great to someone who don't know how to useUnable to parse markup [type=CF_TEX]

.someone can provide an explanation of div 1 500?, thanks.

And now there are only two SRMs in month... I like SRM competition (also I like CF), so I think we will be happy if there are more (like 3 or 4 SRMs in month).

But I think the quality of problem is improving much :P