dalex's blog

Codeforces Gyms: Samara SAU ACM ICPC 2013-2014 Quarterfinal Qualification Contest
By dalex, 11 years ago, translation, In English

On Satudray, Oct 12, at 12:00 PM another 5-hour contest in Codeforces Gym will be held. It's the second time we prepare qualification contest for Samara SAU teams to determine who deserves to participate in Southern Subregional Contest in Saratov (the previous such contest can be found here).

Maybe you know that team Teddy Bears is no longer able to take part in ACM ICPC. It resulted in renaming and renumbering the teams in the university. You have an unique opportunity to defeat new first team of Samara SAU and show them at what place they can finish in Subregional Contest. Don't miss this chance!

Contest is over. Now you can just solve the problems or take part in the virtual contest.

Many thanks to Xellos who made a tutorial.

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

»
11 years ago, # |
  Vote: I like it +26 Vote: I do not like it

Now that the contest is over, I can ask: what's the solution for G? I tried to find some conditions for the tiling to exist, but every one of them failed...

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    if n is sum of two squares then answer is Yes

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      can anybody prove it?

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

        We found this problem in old Soviet literature. But we don't want to say where exactly, because some other problems from there will appear at some programming contests soon.

        About the proof: it is not so small to publish it so easy. We thought that the picture can make you think about the orthogonal triangles and their sides' lengths, that then can easily lead to the correct solution (as it happened with me when I firstly saw this problem).

        → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
        ← Rev. 2   Vote: I like it +11 Vote: I do not like it

        Not a rigorous proof, but some ideas I used to solve problem. (Sorry for my bad English)
        Lets assume that basis vectors are p1(x, y) and p2(y, -x), where gcd(x, y) = 1. Consider point (0,0). Lets find the nearest point of the same color in the same line, which belongs to our coordinate system.
        k * y + b * (-x) = 0 (equation k * p1 + b * p2 = (X, 0)) Nearest solution is k = x, b = y (because gcd(x, y) = 1).
        Then we can find corresponding X = x * x + y * y. It means, that colors in that line have period X. Because of gcd(x, y) = 1 each line contains all possible colors, and it have same period X.

        In case gcd(x, y) != 1 each line have period X / gcd, and each consecutive gcd lines have different sets of colors, so answer is also x * x + y * y.

        → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone provide a hint or algorithm for Problem I (Meteor Shower). It seems to be a DP problem but I am unable to formulate the DP, if any.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    I'll write something about all problems. Just wait.

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Here It's not DP, at least not as far as I can see.

    → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

in gym,when i turn the coach mode off,i find that the web page says that i hava ac all the problem,why?

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    You (or your teammate?) have sent all jury solutions in the coach mode.

    → Reply