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 phase ended, the arena went dead and now it is not opening for challenge 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 were 7 successful challenges in 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". Zzyzx (the same friend i mentioned) is in 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]) + 1withcost[i] = Math.max(Number1[i], Number2[i]) + 1T_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 i we either take the vertex i and DP value from vertex i - 2, or we don't take the current vertex and use DP value from vertex i - 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 is max(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 i connected with shape a and b. shape a also connected with flavor j, b also connected with flavor k. Let's denote W(a, i) -> number of candies of shape a and flavor i.
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 shape a, there are two equations mustn'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 MinakoKojima 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:
(weighti - d * voli)2 = weighti2 - 2 * d * voli * weighti + d2 * voli2, so
If we call
, 
, 
, we have a parabola:
a * d2 + b * d + c
This 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 * d2 + b * d + c and 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 see g(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!
Ребят, стыдно задавать такой вопрос, но все же, как решать 1000 див2?
Если X/Y (округленное вниз) > 1, то можно моделировать. За один ход проскакивать количество дней равное количеству конфет, затем пересчитывать деньги и конфеты. При таком условии количество конфет из итерации к итерации будет расти экспоненциально. O(logZ).
Если X/Y (округленное вниз) == 1, то можно моделировать. Заметим, что изначально у нас 0 конфет (после первого вечера). Через несколько дней остаток накопится (если X != Y, но этот случай совсем тривиален) и в некоторый день у нас появится 1 запасная конфета. Заметим, что теперь каждый раз, когда мы будем покупать конфеты у нас будет хотя бы одна запасная. Через несколько ходов уже не 1 конфета, а 2, 3, 4... За одну итерацию можно проскакивать все дни, в которых одно и то же количество запасных конфет (суммарный остаток должен в очередной раз переполнить Y, ..., какие-то вычисления на бумажке). Так как если у нас k запасных конфет, то и дней мы промоделируем хотя бы k, то в итоге за n итераций мы промоделируем 1 + 2 + 3 + 4 + ... + n = O(n2) дней.
.
Solution of Div.2 hard problem:
First, if x = = y, then obviously answer is 0. So assume x > y
Let rem = money left on day t, cur = candies left on day t (both taken at noon);
Initially rem = xmody, cur = xdivy.
Then, since x > y, after cur days Alice buys another cur candies, her money left will increase cur * (x - y), and let diff = cur * (x - y); Notice that if rem + diff ≥ y, Alice will actually buy more candies.
We will split into two cases then:
if rem + diff < y, Alice needs period = ⌈(y - rem) / diff⌉ times to iterate cur days until cur increases. In such case, cur only increases by 1 after period * cur days;
if rem + diff ≥ y, cur immediately increases after cur days, and because diff could be very large because cur will increase, we need modulars here. After cur days, Alice will get rem + diff additional money if she still buys only cur candies, so cur will increase by (rem + diff)divy, and rem = (rem + diff)%y.
The first case takes period * cur days, and second takes cur days. If days left < days to be taken, we should calculate the final result and terminate. The result is trivial: in first case finalResult = rem + (daysLeft / cur) * diff + (daysLeft%cur) * x, in second case it's just rem + 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 iteration cur increases by at least 1, thus after k iterations days passed = Ω(k2), 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