Tommorow, the SRM 632 will be held at 7:00 EDT. This is the last chance for you to use the web arena and be able to win TC prizes (a trip to TCO14 or a T-shirt!). Don't forget to use the web arena and "test your luck".

I wish you would be "lucky enough" to win prizes!he

Happy coding.

P/s: The SRM schedule of this year is fully updated.

I_love_tigersugar is a lot more reliable at reminding me of SRMs than topcoder's email reminders...

Oh really? I always save all programming contest events in my phone's calendar and it always reminds me one day before each contest. I don't usually check for new email so I don't know when they send email about upcoming contest.

Btw, sorry for any inconvenience.

Hey! Quick question for Java-Guru Topcoders: when I run "javaws ContestAppletProd.jnpl" in terminal, applet creates two configuration files in my home directory *.conf and *.conf.bak. How can I avoid such behavior? Can I set location of these files in command line of Java Web Start?

When I try to open arena (file ContestAppletProd.jnlp) in ubuntu using Iced Tea I got this error , I tried to press "clean all cache" but it's unable to delete the cache , How can I fix it ?

Same problem. However, I managed to clean cache after rebooting computer. Didn't help.

I tried to reboot but still unable to delete the cache :(

Now it works. No idea what happened.

I am an ubuntu newbie, but typing "ControlPanel" in terminal and deleting temporary Java files in "Temporary files setting" helped me.

You should try command "javaws -Xclearcache" to clear cache.

Tried web client of arena. Looks fine, but problems were listed in wrong order (medium — small — large). Damn.

Could you please explain a DP in div1-hard?

Key observation: you can delete the node after you visit it. Let's create the sequence from the end. Let

DP[i][j] be the number of ways to create a pattern and end up withinodes in first row andjnodes in second row, while you start from the first row. Transitions: you got here from the other row ((j+ 1)·DP[j+ 1][i]) or from one of two neighbors in the same row (2·DP[i+ 1][j]). Answer is 2·DP[1][0].First thing to notice is that all configurations of x unused dots in a row are equivalent, because you can only move to the next dot to the right or left anyway.

Let s(x, y) be the number of ways you can make a pattern, if you have x unused dots in first row, y unused dots in second row, and you can be anywhere in first row.

You can move to the left or right in the first row, either of this leads you to s(x-1, y). So sum 2*s(x-1, y) to answer.

You can also go to the second row, this brings you to s(y, x-1). Remember you can be anywhere on first row, so add x * s(y, x-1) to answer.

what's the meaning of “you can be anywhere on first row”?I have got it.

I don't get how this part works:

_ You can move to the left or right in the first row, either of this leads you to s(x-1, y). So sum 2*s(x-1, y) to answer._

How about when n=2? You van only go one direction, as there aren't two neighbours in the same row for any node

Say you are calculating s (2,2) , so you can be in 2 different positions in first row.

If you are in the right position and move left, you can now only be in a single position in first row, so s (1,2).

If you are in the left position an move right, you can only be in the right position, so you get s (1,2).

The total is still 2*s(1,2). What you may have missed is that the edges are already accounted for when you move left and get s(x-1, y), that is, you can only move left from x-1 different positions (the "-1" is the edge, and you can't go left from there).

got it, thanks!

I solved div1 medium using DSU and passed system test , Who too solved it using DSU? I think it's not the intended solution because it quite strange solution and I couldn't prove it , see my code it's quite clear.

It is rather easy to see that you basically add edge to graph from end to start and you do not add edges that would make 0 and N — 1 connected, but add theit cost to the answer. That is the intended solution, you just make it linear while it was easier to do it in qudratic time

I think it is the intended solution. Only one thing I still don't get is why the cost is 3

^{i}instead of 2^{i}. Is the power of 2 too mainstream?Next time they should use something like 1337

^{i}or 747474^{i}for extra coolness.Giving 3

^{i}instead if 2^{i}is enough to make somebody fail system test because of calculating pow like x=(x*3)%MOD in integers:)Sounds like another reason to use 2

^{i}to me, do you really want someone to fail because of this?I am writer. I don't notice the potential bug. I use 3

^{i}becuase I think using 2 is too normal. I prefer unusual thing >_<.why not? and Python is always there.

Or 998244353, to make people think a very bizzare FFT is necessary?

DSU is what I intend exactly. Because max flow equal to min cut, we can try to find min cut instead to max flow. In a cut, points of a graph will be divide to two group. we will try to make the edge of larger costs connect the points of same group due to 3

^{i}> 3^{1}+ 3^{2}+ ... + 3^{i - 1}Can you please explain your max flow solution in slightly more detail especially the cut part?

Anyone could help me out with Div2 1000? The code I have gives me TLE on only 1 of the 93 cases. Anything I could do to optimize it?

I'm actually kinda surprised the bruteforce only times out for a single case.

But you can transform it into correct solution easily: note that if your current product is not a divisor of goodValue, it's impossible to make it equal to goodValue by doing multiplications. So you should only add something to buffer when it divides goodValue.

This code passes systests spending less than 10 ms per case.

What is the solution for DIV 2 HARD 1000 pts problem ? I tried it using DP in the practice , but 2 tests are getting TLE while the others passed. The reason to me seems that I use map to represent the state and in these two cases the size of the map gets very large.. Still if any one has a better approach please share it.

I found my mistake , at each stage we have to ensure that the current product is a divisor of the GOODVALUE. Thanks ffao.

As I see, the way to solve Div2 1000 is to use Map.

Can someone tell me what is algorithm to solve that problem and how does Map help us?

Thank you

People used dynamic programming to solve the problem. state dp(i,p) // i is the ith element and p is current product. Problem is p can be up to 2000000000. So we can not use such a huge memory for memoization purpose. For that people used map to save the states.