msg555's blog

Michigan Invitational Programming Contest in CF Gym
By msg555, 10 years ago, In English

In the interest of learning a bit about Codeforces' Polygon and Gym services, I have set up and made available a contest that I worked on a few years ago. The contest was created with the help of Richard Peng, Danny Sleator, Dennis Matveyev, and Krzysztof Onak.

I believe the average problem difficulty should be relatively easy for strong teams although there's at least one fairly tricky problem in the set. Good luck!

As an aside, this contest actually has a bit of a story behind it:

This was an invitational contest hosted by the University of Michigan during the 2011-2012 ICPC season. With help from the contests' sponsor, Jump Trading, we were able to invite several of the teams from around our area for a contest prior to regionals.

While I personally found the logistics of setting up such a contest a bit frustrating to manage, lucky for North America, one of the teams we invited was the University of Chicago coached by Borja Sotomayor. Running with the idea, Borja has created something much bigger and much more meaningful with the NAIPC contests (which many of us hope will become an official NA super regional) from the past three years (thank you Borja and everyone else involved!).

You can check out these past NAIPC contests at the links below

http://icpc.cs.uchicago.edu/invitational2012/

http://icpc.cs.uchicago.edu/invitational2013/

http://naipc.uchicago.edu/2014/

Anyway, enough story time. Good luck solving problems! (And see if you can spot all the Pixies references)

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

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

For NAIPC 2014, where can I see the time limits for each problem?

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

    I cannot seem to find the time limits listed anywhere either. However, the time limits for the practice contest were all 5 seconds and I suspect it's the same here. I didn't see anything about memory limits.

    It looks like the data and judges solution link was never updated. These were released and are available at http://serjudging.vanb.org/?p=666

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

Any hints on solving A. My current strategy is to use a Fenwick tree. For each number P in the permutation, I count the number of crossing by summing how many numbers greater than P. But I already got dozens of WA. There's something wrong in this idea ?

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

    Looks like you aren't calculating the elements of P correctly.

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

      The number should be calculated as: (A * i + B) % N. As it can increase a lot and causes overflows, it's necessary to check whether it resulted in an overflow, then it should be summed with N and then, the 'mod' calculated again. What is the pitfall in this calculation ?

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

        When your calculations overflow it wraps the result modulo 2^32. It will not still be correct modulo N. Use 64 bit arithmetic.

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

    Another solution to A. is to count inversions in the sequence s obtained by sorting {0, 1, ..., n} using the comparator x < y if ((a * x + b) % n) < ((a * y + b) % n). A modified mergesort finds the answer in O(n lg n).

    → Reply
»
10 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Could someone give me a hint for problem E (spies)? At the moment the best I got is a brute-force, obvious solution which is easy to make it fall on TLE and a "smarter", wrong solution, but I have no idea on how to count the number of legal arrangements in a more clever way :(

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

    The best hint I can give is to think about the problem as a graph where cities are nodes and spies form edges. Think about what connected structures have solutions and how many solutions each has. There's a couple cases.

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

Thanks for making this contest available in CF GYM!

Is there a way to virtually participate NAIPC contests?

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

i can't solve the problem "I — Yawner" with a lot of thinking. help?

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

I was trying to solve problem D finding the smallest rectangle formed by each pair of red points, but I'm getting WA-1, can someone help me?

I can't understand why my solution fails.

I guess is a tricky test which I can't found.

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

    You can't describe rectangle by 2 red points only. Suppose that you have points (0,0), (5,10), (5,-10), (10,0) and want to build smallest rectangle which covers all 4 points.

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

      I noticed that.

      I tried generating all possible subsets of exactly required red points size, find minimum enclosing rectangle for these points and verify it not contain blue points.

      Still WA-1.

      I can figure out a complete search solution trying all possible rectangles but I think is too slow.

      → Reply