Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

By RAD, 13 years ago, translation,

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!

• +35

| Write comment?
 13 years ago, # |   0 Is it intentional that now the only way to submit is to select a file instead of pasting the code? I made a pair or mistakes because of that, because using the current way forces me to lose the tab with the problem.Is it possible to restore the submit pasting functionality back?
•  13 years ago, # ^ |   +3 It will appear soon :)
•  13 years ago, # ^ |   0 Thanks :), I always preferred pasting the code. Also, my status during the match dissapeared, and now it only shows the practice submissions.
 13 years ago, # |   0 Nice problems!I like them all.. :)Well, when will the tutorial of this roundannounced?
•  13 years ago, # ^ |   0 Participant ArtDitel told that he will write it. Lets wait!
•  13 years ago, # ^ |   +13 If you want a quick overview...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 upProblem 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.
•  13 years ago, # ^ |   0 what can be test#31 for problem A-Triangle?
•  13 years ago, # ^ |   0 Hmm.., we don't know.. ;)because testdata are hidden..
•  13 years ago, # ^ |   +1 I found that, Actually its related to "checking  whether length of sides becomes zero , while changing the points"example(as suggested by RAD)0 0 1 0 4 1Thanks RAD
•  13 years ago, # ^ |   0 I am also interested about case 31 for problem A. can anyone(admin/problem writer) tell us what can be the case?
•  13 years ago, # ^ |   0 I am also interested about case 31 for problem A. can anyone(admin/problem writer) tell us what can be the case?
•  13 years ago, # ^ |   0 Consider three points in a linelike 0 0 0 1 0 3
•  13 years ago, # ^ |   0 I pass #31 test when add checking the S of triangle
•  13 years ago, # ^ |   0 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! :)
•  13 years ago, # ^ |   +1 This lecture explains the O(n^2) WIS algorithm pretty nicely: http://www.cs.illinois.edu/class/fa08/cs473/Lectures/lecture12.pdfThere'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.pdfThe UVa online judge has a list of Dynamic Programming problems: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=114I 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.
•  13 years ago, # ^ |   0 thank you so much!i never expect somebody may answer such a primary question so detailed!thank you very much!
•  13 years ago, # ^ |   0 Welcome :)
•  11 years ago, # ^ | ← Rev. 2 →   -6 I have never heard of Weighted Interval Scheduling DP before. Thanks for sharing your resource. You sir, are awesome! :DHere, I found another source:www.cs.cornell.edu/courses/cs482/2007su/dynamic.pdfThis contains both N^2 and NlogN idea.
 13 years ago, # |   +3 Hi,i'm  a newbie
 13 years ago, # |   0 Nice problems!I have a question though. How am I supposed to include the BigInt class in my solution? I'm writing in C#.Thanks!
•  13 years ago, # ^ |   0 long long int i guess.
•  13 years ago, # ^ |   0 How do I declare a long long int?and is it enough to hold 2^2000?
•  13 years ago, # ^ |   0 I dont know about C# but as for C/C++ long long int can cover only 2^63 . long long unsigned can 2^64
•  13 years ago, # ^ |   0 So how could this be solved in C#?
•  13 years ago, # ^ |   0 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#.
 13 years ago, # |   +4 For D I could find the greedy solution but can't do it in time because I have to right a big int power :(  I hate big int. Why you just can ask for a moded result?