vlade087's blog

Usaco December Contest

By vlade087, 11 years ago, In English

I glad to invite to take part in USACO contest is from Dec 13 to 16, remember this contest is IOI style. good luck

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

Comments Comments (17)
| Write comment?
»
11 years ago, # |
  Vote: I like it -37 Vote: I do not like it

in problem 3 in Bronze division I can't underestand , we must only count number of pair of points that they will be trapped in cycle or any cycles ?

For example suppose we have 4 points that they form a rectangle and points on one diagonal have paired each other,then we must count this cycles ?

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

    Don't discuss the problems here before the contest ends!

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

It seems something is wrong with the USACO server right now.The website takes a long time to load,and my submission is shown as "Being Judged" instead of "sample case solved correctly".Anyone experiencing the same issue?

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

Well the site appears to be completely down now, so I'm wondering what's gonna happen.

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

I submitted now, and it seems to be working. Well, no server is truly stable.

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

The contest has ended.

How to solve 2nd problem of Gold division?

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

    Dynamic programming with segment tree.

    Each node of segment tree should contains dynamic array d[2][2]. d[hasLeft][hasRight] means what is the answer to the problem on the corresponding segment if the left machine from the segment used (hasLeft), and the right machine from the segment used (hasRight).

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

      Thanks, got it. What about the 3rd problem?

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

        The third problem is about permutations. It's hard to explain easy, but I will make a try.

        Consider your transformation as composition of two. The first one is multiplying the prefix of your permutation by the given permutation. The second one multiplying the prefix of your permutation my cyclic shift, so as to move the first number to the end of the prefix.

        The next step is to understand how the process works. It's not hard to get that it is possible to get the current k-th number from the card deck if you know the cycle of permutation p (that is composition of two described above) that contained the element |p|.

        I think with these two hints and with some thoughts you can get the whole solution.

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

        Also notice that only the first M and last M elements of the resulting permutation (of all N elements) are non-trivial: k > M + 1-th element will be k - 1-th incremented by 1.

        I imagine the superposition of permutations (P and right-shift) as some boring cycles and one non-cycle — a machine that's moving along a tape (some of the numbers 1..M are inside it already, and M+1..N are yet to go inside), and when moving along the tape, it always just moves the tape by 1. You can see that it takes the next number of the tape and ejects the first one still inside, so it doesn't change the order of elements on the tape. It'd be cool to construct such a machine :D

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

    I was lazy to implement segment trees, so I just did some sqrt-stuff.

    Notice that the upper bound on N is 40000 = 2002. So just split the array into sequences of 200 consecutive elements, do an initial DP (as Gerald describes) on each of them, and for every query, another DP on the one that changes. This allows you to count the DP answers (as in the bruteforce DP) for every 200th element, and compute the last N%200 states by bruteforce.

    It's easy to see that the same idea works on merging the DP answers for any 2 intervals, so you can take it as a motivation for the solution using segment trees...

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

      Nice, thanks. It is 50000*200 on the worst case as I understood. Is it ok? My solution for the first problem is O(K*logN+Q*K), which is nearly the same, and I thought it may timeout on large cases.

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

        It doesn't have to pass all the tests, and I don't care if it even contains a bug and completely fails. USACO is not worth it for me to exert any effort in getting my solutions to pass certainly — I don't gain anything from it. I'm just trying out various approaches, and "how fast is an sqrt solution here?" is one of them.

        Another one is making this training for no feedback. This is also training for the USA team for IOI, and I don't understand how anyone would deliberately try to decrease their chances of success at the competition by using completely different environment. IOI is a lot about strategy, and gaining some "guaranteed" points is a crucial part of it, especially if you're not aiming for all or nothing. Being able to code well without feedback may be good, but if you do have feedback, then being able to code equally well but with the additional benefit of feedback is even better...

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

3rd Problem, Silver Divison, help, please.

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

    In third problem we just had to build such a graph that would show us the sequence in which the cards will leave the deck. So this is easy to predict if we mention that after the shuffle(we have a graph on input that shows us the shuffle for M cards) when we take each card off we just send each card one position left. Let us shuffle the cards the first time and then build the graphs. So, we have 2 graphs that we have to unite into one. One graph that is given on the input(let's call it "S") and the other one that sends each card one position left let's call it "Co". So our final graph("Fin") would look like Fin[i] = S[Co[i]]. The first card that will leave the deck is the card that stands on the first pos after the shuffle. The second one is such a "j" for which "Fin[j] = 1". The third one is a j for which "Fin[Fin[j]] = 1" i.e. the ith card to go out will be such a j for which distance to the first node is i-1. We have to find first M cards according to the Fin graph and the N-M cards are the ones that are left in an order from smallest to biggest because we do not do the shuffle and card off after there are <M cards.

    So, we basically had to implement the shuffling and taking a card off processes and find the sequence in which the cards will go out.

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

    This is my submission for this problem.

    I hope it pass all tests and help you too.

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

Scores published, perfect one for me on bronze. Silver division \o/
Here

→ Reply