chrome's blog

Single Round Match 639
By chrome, 9 years ago, translation, In English

Tommorow will be held Single Round Match 639 at 15:00 MSK.

Let's discuss here problems after the contest.

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

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

I like your ID.

→ Reply
»
9 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Another 3-week period between two SRMs

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

    There was TCO, which should count as several SRMs.

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

250 was cruel!!!

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

It was the HackRound :)

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

    15th place: l0l h4x

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

      See the 33th place. No problem solved)))

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

        Yeah, well 15th place is no problem attempted.

        Also, I guess this gives us simple proof that the "positive points for challenging" rule has been removed.

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

          The rule is "non-negative points for challenging", so you still have one chance if your score is 0.

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

            Oh, okay. I'm not too familiar with TC rules, because I never read rules. I just try out stuff for practice and check what the most important stuff means (and go by common sense). And TC has a lot of more obscure ones that don't apply to me much (like this one, since I'm almost never challenging).

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

      256th lol) But I was speaking with chinese contestant in chat and discovered that "erfen" is "lower_bound" and "huangjin" is "golden_section".

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

How to solve Div 2. 500?

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

    find N such that N*(N+1)/2 == x+y, if you can't — return -1;

    and find the answer by greedy substractions x := x — N..1.

    UPD but I wasn't sure that greedy will work, so I've created array a[2*10^6] with some strange values and used binary search to find the answer "i" such that a[i]<=x

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

      (Edit: This is for d1-250, not d2-500): In your greedy subtractions, make sure to never leave 2 as a remainder, because it's the only number you can't make.

      (...and if you do find that corner case, make sure to write the if condition correctly or you'll end up failing like me anyway u.u)

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

        Did you think greedy only because input size was an indication that DP won't work? Or were you able to see the greedy solution from the beginning?

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

      yep I wonder why return is long long :D int is enough

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

      UPD: removed, I didn't notice div2 500 was similar to div1 250

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

      Can you share code?

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

      x=9, y=0, no such N exists

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

    This is my solution. I forgot to check the corner case when x = 0 and my solution was challenged. But I fixed and sent it after contest and it passed all the test. It is sad because I only forgot to include &&x =  = 0. Next time I will be pending for small details.

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

      Your solution is great i was able to understand it . But seeing other submissions in topcoder i came across this solution Topcoder Solution unable to understand logic

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

How to solve 1000? I've reduced it to some problem of linear programming with integer values, but do not know how to solve it in these constraints.

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

    I reduced 1100 to the form X * case1 + Y * case2, where case1 is if you feed first pet on t=0, and case2 is if you feed second pet on t=0 (eventually you'll reach a time t in which you can choose again, so you'll end up choosing case1 X times and case2 Y times).

    I couldn't finish during the contest time, but I managed to solve it in the practice room with ternary search on X. Now have fun dealing with all of the corner cases and overflows! :D

    As I can see, Petr and tourist solved it differently, so maybe their solution is a bit closer to what you came up with.

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

      I did the same as you (talking about idea), but did not come up with the ternary search approach.

      By the way, why ternary search works in this problem?

      → Reply
»
9 years ago, # |
← Rev. 4   Vote: I like it +35 Vote: I do not like it

I like the 500 problem very much though I didn't solve it in the contest. (With some array doesn't clean up and one more stupid mistake.) But I'd like to share with you guys my O(N2) solution. I am going to write a post about it. Will be updated soon. :D

UPD LINK

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

Can someone explain why in Div 1 500 folding row-wise and then column-wise independently and at the end multiplying the two values gives the correct result? My main problem is that I don't really understand why they are independent? Intuitively I thought that if the number of remaining rows is smaller, the possible column-wise folding should be smaller.

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

    Take a vertical and horizontal fold. Show that if you can fold vertically first and horizontally afterwards, the board is such that you can swap them.

    → Reply