Welcome to Codeforces Beta Round #18

Authors of today's contest are Mike Mirzayanov, Edvard Davtyan and me. Thanks to Dmitry Matov for his help in statements preparation and Julia Satushina for translation of problems in English.

Good luck everyone!

- Problems
- Final standings
- Contest winner: I_am_Feeling_Lucky

I like them all.. :)

Well, when will the tutorial of this round

announced?

Problem A - Geometry with *many* possible solutions including Pythagoras's Theorem, checking for perpendicular line segments, using trigonometry to test angles...

Problem B - Simulation, with modular arithmetic to speed things up

Problem C - If you keep track of the sum to the right of a point, and the sum to the left of a point, you can compute the new left-hand and right-hand sums by just subtracting one number from one sum, and adding it to the other. In this way, you can try all possible cuts in O(n)

Problem D - This can be done as a Weighted Interval Scheduling DP, though as a friend pointed out, 2^x > 2^(x-1) + 2^(x-2) + ... + 2^0, so you can just take the largest intervals first, greedily, because they will be worth more than all other intervals that they conflict with.

Problem E - Row by Row DP. Determine all possible chequerings for one row, and get the cost of using that chequering (which can be done in constant time, not O(n)!). Then for the next row, try all possible chequerings and see which ones are compatible with the row above. Take the minimum cost of these. This is ~650x650x500 which is just a *bit* too slow. But if you sort the results of the previous row by cost, you can get an answer closer to 650*500.

because testdata are hidden..

example(as suggested by RAD)

0 0 1 0 4 1

Thanks RAD

like 0 0 0 1 0 3

I pass #31 test when add checking the S of triangle

I'm a rookie about algorithm, i just interested in the Weighted Interval Scheduling DP method, can somebody offer me more information about that? thx a lot! :)

There's also an O(n log n) algorithm, but it's a bit more complicated: http://pages.cs.wisc.edu/~shuchi/courses/787-F09/scribe-notes/lec3.pdf

The UVa online judge has a list of Dynamic Programming problems: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=114

I can't recall any UVa problems that are Weighted Interval Scheduling though... but solving DP problems will help you with other DP problems because they all have important similarities.

thank you so much!

i never expect somebody may answer such a primary question so detailed!

thank you very much!

I have never heard of Weighted Interval Scheduling DP before. Thanks for sharing your resource. You sir, are awesome! :D

Here, I found another source:

www.cs.cornell.edu/courses/cs482/2007su/dynamic.pdf

This contains both N^2 and NlogN idea.

I have a question though. How am I supposed to include the BigInt class in my solution? I'm writing in C#.

Thanks!

and is it enough to hold 2^2000?

In .NET 4.0:

using System.Numerics;

BigInteger a;

Then you can use it as a regular integer number. All the operators are overloaded, so you can easily do something like that:

BigInteger a = BigInteger.Parse( Console.ReadLine( ) );

BigInteger b = BigInteger.Parse( Console.ReadLine( ) );

BigInteger c = a + b;

But AFAIR this server doesn't support .NET 4.0, so anyway you will need to implement big integers by hands if you want to solve that problem using C#.