sohelH's blog

ACM ICPC World Finals Warmup @UVa Online Judge
By sohelH, 12 years ago, In English

ACM ICPC World Finals Warmup is scheduled to take place at UVa Online Judge on Saturday, 25th May 2013.

Contest Link: ACM ICPC World Finals Warmup

Date: 25th May, 2013

Day: Saturday

Start: 9:00 AM, GMT

Duration: 5 hours

If you are getting a redirect loop when trying to access the link, remove the cookie onlinejudge.org and try again.

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

»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Reminder: The contest starts in under 12 hours.

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

how to solve problem C (Rectangle XOR Game) ?

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

The problem J is still broken.
I have sent a detailed e-mail to Miguel Revilla.
When it will be fixed?

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

    Yep. The fact is that the 10^9 upper bound mentioned in the problem statement does not apply to the test cases. Instead, a larger upper bound of about 3*10^9 should be considered in order to solve the problem (so that (3*10^9)^2 still fits into a long long). I'm sure this mistake caused a lot of contestants to keep getting WA with an otherwise perfectly correct solution (I spent more than 2 hours during the contest trying to debug my actually correct solution ; only several hours later, when I tried to find which cases made my solution fail, I found the problem with the test cases).

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

      How to solve problem J? Any particular hint?

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

      They have already fixed the bug with upper bound and rejudged all submissions.
      But now they allow equal numbers in the solution
      and without this you can't find the solution in some situations.
      So after rejudge a lot of contestants lost their AC (including me an you).

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

        That's weird, because I have a check in my program that ignore all solutions that have equal numbers, and I still got accepted :D

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

        Oh, I see. I haven't checked for rejudges. I now see that I lost the AC from the contest. I resubmitted my code in the problem archive without the explicit check that the numbers should be different and I got AC. Anyway, it seems that they just can't get this problem right :)

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

          We are aware of the issue. There should be another rejudge after the correction. Sorry about all these!

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

Any suggestions on problem E? I've solved its first part with "dp[A] — number of subsets which gcd is A", but can't apply this dp to case of K-subsets faster then O(nk). I think such kind of problems "2 in 1" are not good cause it doesn't distinguish participants who spent on this problem several hours and solved one of subtask and participants who haven't ever read the statement. Thanks

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

    Both sub-problems can be solved by inclusion-exclusion principle.
    Let cnt[d] be the number of elements divisible by d.
    It can be found in , where V = 100000 is an upper bound for numbers, by some kind of sieve.
    Then answer for the second sub-problem is

    where

    is the number of subsets with size $k$ and .
    For the first sub-problem binomial coefficient should be replaced by 2cnt[dx] - 1.
    The complexity for finding such double sum is as well after precomputing Moebius mu function, powers of two and binomial coefficients (for example, by computing factorials and their inverses).

    → Reply