Nope, I'm too lazy to maintain both versions :)

Thanks for the contribution everyone. Sorry for the delay, I don't receive e-mails about new comments for some reason.

I'm not sure I understood you right. There's no need in additional loops as you describe. It's a standard DFS.

If you process the nodes in this order, then for example when you run dfs(2), the vertex 1 won't be visited again and dfs_low[2] = 2.

The sum of Manhattan distances over all cells: = = .

Now we need to subtract the sum of Manhattan distances with occupied cells. Suppose (x, y) is one of occupied cells, then . Since there are at most max(n, m) occupied cells, we can just sum over all (x, y).

Finally, the pairs of occupied cells were subtracted twice and we need to add them back. It's O(max(n², m²)) as well.

And don't forget that the order of cells matters, so for example the sums in the second paragraph above need to be multiplied by 2.

Try this one.

The Russian version seemed hard to understand to me as well. I probably spent more time reading the statement rather than coding the solution.

A simple link to the tag search would suffice (and be in line with the whole Web 2.0 idea of the site), but tags need to be kept consistent for that. (And they need to actually work, e.g. this doesn't find anything.)

Here are my results for N=200. (gcc 4.4.3, Ubuntu 32bit).

g++  0.899s
g++ -O2 4.733s
g++ -Os 0.413s
g++ -O2 -fno-tree-ter 0.390s

One would think that the optimization ftree-ter is broken. However it seems that it's enabled at -Os as well. In fact, the only difference in optimizations between -O2 and -Os is -finline-functions at my system. I tried turning it on, but to no effect.

Here's the relevant part of the man page:
-ftree-ter

Perform temporary expression replacement during the SSA->normal phase.  Single
use/single def temporaries are replaced at their use location with their
defining expression.  This results in non-GIMPLE code, but gives the expanders
much more complex trees to work on resulting in better RTL generation.  This is
enabled by default at -O and higher.

Very nice problem D...
Kudos to the author.

Read the problem statement carefully. The operations are:

1 1 1 1

+
2 1 1

+
3 1

*
3

I had the same line of reasoning. Would love to know the solution…

http://codeforces.com/blog/entry/1112

> k - is the length of each part
But the parts may have different lengths.

> Also in transition we should be careful with the equal numbers (I used set).
Can you explain the details? For example, how do you make sure that in the sequence (1,3,2,1,3,2) the subsequence (1,3,2) is counted only once?

OK, I figured it out. Apparently test files have Windows line endings but the input in the custom test has Unix line endings.

Yes, and my program worked correctly for the first sample when I ran the custom test. It didn't pass the pretests though. Then I added handling extra whitespace and it passed.

I think in tests for problem A there is extra whitespace. Can you check the first pretest?

Is this award displayed somewhere on the site? I was expecting to see medals or badges in laureates' profiles.

I didn't use either of these optimizations but avoided the 'strictly less' flag (so, the number of states is only 2 times less, while with these optimizations it's 48*5 = 240 times less). Still got AC…

Just to clarify: these are not bugs. 1<<42 is undefined behaviour, and the other one is also well-known.

-ffloat-store compiler flag solves the floating-point problem for me. The other one I don't have.

Configured with: ../src/configure -v --with-pkgversion='Ubuntu 4.4.3-4ubuntu5' --with-bugurl=file:///usr/share/doc/gcc-4.4/README.Bugs --enable-languages=c,c++,fortran,objc,obj-c++ --prefix=/usr --enable-shared --enable-multiarch --enable-linker-build-id --with-system-zlib --libexecdir=/usr/lib --without-included-gettext --enable-threads=posix --with-gxx-include-dir=/usr/include/c++/4.4 --program-suffix=-4.4 --enable-nls --enable-clocale=gnu --enable-libstdcxx-debug --enable-plugin --enable-objc-gc --enable-targets=all --disable-werror --with-arch-32=i486 --with-tune=generic --enable-checking=release --build=i486-linux-gnu --host=i486-linux-gnu --target=i486-linux-gnu
Thread model: posix
gcc version 4.4.3 (Ubuntu 4.4.3-4ubuntu5)

> let's talk about gay-on team
So… how many people on your team are gay?

I thought 2011 is the year of white rabbit, not red :)

Yep, now it seems to happen more frequently :)

Great analysis!
In problem E to find integer roots I just iterated over all possible roots x and for each of them over all possible coefficients c (they must be divisible by x). Knowing x and c, we can find the second root and coefficient b and check the conditions. The time is .

Look at the time that question was asked. Mike meant that during the contest the test cases are not available.

Wow, the tests are now available? It's very nice!

Why is negative result allowed in task E? It doesn't make sense. It's also sad that the solution using iostream doesn't pass the TL, because usually at CF it's OK to use iostream and some of us got used to it:)
But overall, the problems are very nice, thanks!

Is there a schedule for December already?

If you participate 'out of competition', then when you enter the contest you appear in room number 1 instead of the room you were assigned to. (It's a bug.) To move into your room, select it from listbox in top right corner, it's marked with a star.

Ah, yeah, sorry

Try 1 2 and 1 4

Seems that two of the problemsetters of this round are Fefer and RAD
I don't see what's wrong with your solution either.

The idea is to assign some numbers a_i to vertices and the lengths a_i + a_j to edges. Then the condition about hamiltonian cycles will be fulfilled. To ensure the condition about different lengths, just choose the numbers a_i one by one so that it was always true that a_i + a_j ≠ a_i' + a_j'. In other words, when you choose a new number, it mustn't be equal to a_i + a_j - a_k and a_i - a_j - a_k, for any already chosen a_i, a_j and a_k. It turns out that if n ≤ 20, this process never needs numbers more than 500, so all edges have lengths less than 1000.

I haven't found the algorithm, just some observations and I don't even remember them :)

I don't know… During the contest I came to some conclusions similar to the proof in the paper, so in principle it's possible to obtain it independently. It's only 1 page long, after all.

It's based on a theorem from this paper

It's a new Russian currency. One bourle = 100 pokeikas  ≈  0.032 laddors.

Here's my solution to I, maybe it'll be useful for someone.
First note that Gray code is 'circular': the last element differs from the first one in one digit. So, we can start enumerating subsets from any position in Gray code.
Now we'll enumerate partitions recursively. Fix the minimal element x and iterate over the (Gray code of the) subset of elements which are in the same subset with x. If M is the subset of all other elements, call our procedure recursively for M. We'll obtain a 'good' sequence of partitions. Unfortunately, if M₁ and M₂ are two consequent values of M, the sequences of partitions for them could not 'glue together': the last partition obtained from M₁ can be very different from the first partition obtained from M₂. But we can always apply a circular shift to the second sequence so that it glued together with the first one. I don't know what's the complexity of this but it passed the tests.

When you register for the competition you are asked to read this

By the way, when you registered for the contest it was written that it would be rated for everyone.

It's not true here that R_i ≤ r_j

It'll give a negative result here, so at least it should be pointed out that we must take a maximum of zero and Δ_ij.

Maybe I'm missing something, but where does this case belong to? (i-th bowl is the higher one)



It seems that it's case 2, but the formula will give a wrong answer.

Why are you writing 'codeforce' everywhere? It's 'codeforces'!

Replace 200 with something larger. The minimum path length may be upto 100*25

Output the smallest possible area of the ancient arena. This number should be accurate to at least 6 digits after the decimal point.

"Nothing" doesn't conform to this specification, hence PE.

Ah, I see, now it's completely clear.

What do "bs" and "RP" mean?

For the problem C you can simply note that if you stand at position k (0-based), then the number of positions you can reach is 1 + k/s + (n-k-1)/s. Then just calculate this number for each k and find the number of occurrences of the maximal one. This saves some thinking, IMHO.

They should make a T-shirt with this print.

How one gets his AC's is his own business, my point is that any variant would be better than what we have now.

I think there should be a strict policy: either don't show the test cases at all (I mean, don't answer the questions in this thread as well), or make a centralized place for them once and for all. (For example, show a link to a failed test on the status page near the submission's verdict.) The way it's done now is the worst possible one: I don't want to see a 'discussion' consisting mostly of requests to reveal a test.

Rather than switching compilers, why not fix your solution? Do you understand what WA means?

Could you post a link to the spoj problem?

For the problem C, try this test:
4
1 2 4 3

> i can solve it when all the rooks are considered of different color
Then just divide this number by z!, since now you can rearrange the rooks and still get the same configuration.

Welcome! Where are you from?

Accessing prime[max] is undefined behaviour, AFAIK.
BTW, your code passes under GNU C++

What error?
Here's a sample Java solution for problem A from beta round #1

You can't simply ignore primes larger than 70. For example, the number 142 is almost prime, but according to your code it's not.

Lady Java

I wanna program like they do at Oracle,
Let you feel my Hotspot, let you through my firewalls.
I'm object-oriented and I'm ready to browse,
So come into my house and I will let you click my mouse.

You can download me anywhere,
You can get me for free.

If you say "Voulez vous coucher avec moi",
I'm up for it if you can write it in Java.
From software application to web application
My booty shakes the heap in just in time compilation.

Some people prefer other languages,
And that's OK if you're retarded I guess.
They can go home with all their .NET mates
And jerk off to a picture of William Henry Gates.

Well, instead of counting the number of 'good' graphs, we count the number of  'bad' ones and then subtract it from the total number of graphs, that's all :)

Of course we should have w  ≤  sum(n_i) as well. Try my tutorial
:)

Where would I take it from? =)

You should avoid putting dollar signs in the posts. If you need to paste an exception stack trace or something, you can do it here

3 vertices, 2 edges:
1--2--3

At the first step no one gets eliminated, since there are no vertices of degree 0.
At the second step the vertices of degree 1 get eliminated and only vertex 2 stays. Now 2 has degree 0.
At the third step no one gets eliminated, since there are no vertices of degree 2.

In a complete graph everyone will leave at the last step.

> whatever the configuration, there will be no one with exactly N friends, so everyone will have to leave...

When a person leaves, the number of friends for other people changes.

Thanks!
Hope that the lack of comments indicates that everything is clear rather than the opposite :)

Actually, this system is better for beginners (compared to topcoder), because their solutions can be checked by strong coders. It can increase the gap between best and medium coders, but remember, not all problems will be so 'hackable' as in these alpha rounds.

Just look at the code and see what's wrong with it. If you solved the problem yourself, it shouldn't be difficult.
Also, while you're coding, remember what pitfalls you had to escape and search for similar mistakes during hacking.

It's written when you enter your room:
You may double click into cells (or ctrl+click) to view the submissions history or hack the solution

Yes, you need an O(n) solution

Is it just me or everyone has this awful font in the code window?
http://img96.imageshack.us/img96/9440/44506589.png

Oops, formatting with line numbers is broken but you got the idea :)

Maybe something like this (you need to check "Combine style and HTML code" option)

It's a bug, the question was about rules.

dp[m][s] = min(dp[m-1][s], c[m] + dp[m-1][s-t[m]-1])

Let M be the set of items we choose to pay for; then we need n-|M| seconds to steal other items; it means that sum of t_i >= n-|M|, that is, sum of (t_i+1) >= n.

Please see what I replied below, CF is not only algorithm contest.

To summarize what I think: it's already important to know language features during the hacking. Introducing 'rare' languages makes it only a little more important, since you'll rarely see them anyway.
Code obfuscating, on the other hand, would be much more common, it can even be automated :)

Agreed :)

And what if I use a rare algorithm that is easy to code but hard to prove? It presents the same problems. Should I be banned because I know this algorithm and use it, but others don't?

dp[m][s] = the minimal cost of a subset of items that you choose among the first m items so that the sum of (t_i+1) >= s (here i runs over the indices of the chosen items).
The answer is dp[n][n]

I think most solutions will still be in common languages, because people know them better.

Have you participated in Alpha Round #20? It was very fun! :)
IMHO, with your system the whole idea of combining the coding and the hacking phases together almost doesn't make sense. I agree that the importance of hacking is now emphasized, but well, that's the feature of the format. By the way, in alpha round #20 ivan.popelyshev started to hack solutions only after he submitted all 3 problems himself, and still made it to the 1st place.

As for the tracking of the scoreboard — I'm sure there will be improvements of the interface that will make this easier.

In Alpha round #20 I wrote 3 solutions in 3 different languages (Ruby, Java and C++) just because it was more convenient. Although I could write the solution of A in some other language, but it would be slower and more error-prone. That's the main advantage of being a polyglot, not the ability of others to hack you.

Let me draw an analogy. Suppose you aren't aware of some feature in a language you already know. (Variadic parameter list in Java or something.) If you see it in some solution, what will you do? I suppose, you'll learn about it and later, perhaps, will use it when it's convenient. The same thing with multiple languages.

With current rules there is an important trade-off: you either try to hack solutions (but then the points for problems that you haven't submitted yet are decreasing) or solve other problems (but then you risk missing a lot of points for hacking). With what you suggest the second problem becomes much less critical, if not disappears at all.

"Let through" goals, i.e. the goals that your opponents scored in matches against you.

You need to submit the problem, and it needs to pass "pretests"

Only one.

We'll see it later, when the problems will be harder and with less solutions submitted.

He sold 2^5 to the 1st customer, but now he wants to know what was the optimal way to sell memory sticks, and for that he should have kept 2^10.

My problem was with precision, I didn't output enough digits =\

In short: there is no challenge phase; during the coding after you submit your solution you can "block" it, and then you can challenge other people's code. (But if you block, you cannot resubmit it anymore)