RAD's blog

Codeforces Beta Round #18 (Div. 2)
By RAD, 14 years ago, translation, In English

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!

  • Vote: I like it
  • +35
  • Vote: I do not like it

Comments Comments (26)
| Write comment?
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
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?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    It will appear soon :)
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Thanks :), I always preferred pasting the code. Also, my status during the match dissapeared, and now it only shows the practice submissions.
      → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Nice problems!
I like them all.. :)

Well, when will the tutorial of this round
announced?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Participant ArtDitel told that he will write it. Lets wait!
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it
    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 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.

    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      what can be test#31 for problem A-Triangle?
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Hmm.., we don't know.. ;)
        because testdata are hidden..
        → Reply
        • 14 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it
          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 1

          Thanks RAD
          → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        I am also interested about case 31 for problem A. can anyone(admin/problem writer) tell us what can be the case?
        → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        I am also interested about case 31 for problem A. can anyone(admin/problem writer) tell us what can be the case?
        → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Consider three points in a line
        like 0 0 0 1 0 3
        → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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! :)

      → Reply
      • 14 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it
        This lecture explains the O(n^2) WIS algorithm pretty nicely: http://www.cs.illinois.edu/class/fa08/cs473/Lectures/lecture12.pdf

        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.


        → Reply
        • 14 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          thank you so much!

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

          thank you very much!

          → Reply
        • 12 years ago, # ^ |
          ← Rev. 2   Vote: I like it -6 Vote: I do not like it

          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.

          → Reply
14 years ago, # |
  Vote: I like it +3 Vote: I do not like it
Hi,i'm  a newbie
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
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!
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    long long int i guess.
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      How do I declare a long long int?
      and is it enough to hold 2^2000?
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        I dont know about C# but as for C/C++ long long int can cover only 2^63 . long long unsigned can 2^64
        → Reply
        • 14 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          So how could this be solved in C#?
          → Reply
          • 14 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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#.

            → Reply
14 years ago, # |
  Vote: I like it +4 Vote: I do not like it
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?
→ Reply