riadwaw's blog

TCO Round 2A
By riadwaw, history, 9 years ago, In English

Today, at 6 PM MSK (3 PM UTC)

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

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

I'm having problems with registration (It says that registration is by invitation only despite the fact I have automatically advanced to the Round 2). Any ideas how to fix this?

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

Hey where has cgy4ever gone?

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

Damn , my classmate wrote that stupidness :D idk wht's going on there so sry .

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

I'll be correcting the issue with those who have byes. Those compeittors will be automatically registered for this round. — said TopCoder

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

We just fixed it: "All competitors with a bye have been automatically registered, our apologies for the trouble. For everyone else competing today, be sure you register at least fifteen minutes before the match begins, thanks!"

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

WEB ARENA IS DAMN TOO SLOW -_-

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

I can't login now. I could several hours ago.

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

Sorry, you cannot perform this operation because you are not assigned to this room. The likely cause is that you did not successfuly register for the match during the registration period.

But I am registered...

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

Surprisingly my randomized solution for A passed.

I shuffled the array 1000 times and check if if possible to fix the first element and apply GCD or LCM using DP.

Unfortunately it was not enough to advance, my browser got frozen while testing sample cases.

I would like to know a deterministic solution.

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

Ugh. I failed 500 on slightly exceeding the memory limit (so slightly that changing long long to int in 4 places would've fixed it).

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

How to solve the first question?

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

Unfortunately most of passing 500's solutions were ugly (including mine).

Admins said the intended solution was meed-in-the-middle, but I just googled how to count the number of cliques (http://cs.stackexchange.com/questions/9209/finding-all-cliques-of-a-graph).

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

Why this code is TL on topcoder? 400pt

http://pastebin.com/1wxnCQhM

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

Would have pulled of successful last second submission. Did not change min->max in two lines during last sec updates. Two things 1. The excitement of a successful last sec submission would have been great. 2. Generally frustrated for missing because of typing miss!

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

My solution on 500 passes if fix stupid bug in 134ms.

Solution is following. We can count sum for each edge independently. For one edge answer is equal to ({Number of cliques with a} + {Number of cliques with b} + 1 — {Number of cliques total}). So the solution is to find number of cliques in graph except each vertex. It's well known, that dp on subsets, works in time 2n / 2 if don't count same mask twice, and choose to get or not to get smallest vertex each time. If use same cache, it's works even faster, than n*2^{n/2} (i think even in 2^{n/2} time, but I can prove, only n/2*2^{n} visited states).

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

    Would you mind elaborating that DP which counts cliques a little?

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

      dp[S] = count of cliques, which are subset of S

      Let's v be vertex in S.

      , where N(v) is set of neighbors.

      If always get as v vertex with minimal id, there is O(2n / 2) states reachable. If v is less than n / 2, there are less than 2n / 2 branches, if v is more, there are less than 2n / 2 states total. Order of vertices is imortant. For example, choose random vertex each time is bad (but choose random order one time is ok, of course).

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

        I did it in other way. Divide vertices on two equal parts. For first part precalculate for every subset A is it clique or not, and if it is clique calculate mask of vertices in second part which is connected with all vertices in A (both could be done by & incident masks of vertices in A). For second part calculate for every subset is it clique. Then calculate convolution of this array. For each query S, we look for subsets A of S in first part and if A-clique add number of subsets in second part which is clique and incident to A.

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

→ Reply
»
9 years ago, # |
  Vote: I like it +23 Vote: I do not like it
  1. Solve the first problem correctly, fast enough to be in top40.
  2. Think that you aren't in top40 because you are ~80-th right now.
  3. Blindly challenge a few participants.
  4. You are no longer in top40.
  5. ???
  6. Profit.
→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Same story here :(

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +31 Vote: I do not like it
    1. Submit a solution for 400 you think is incorrect, just so you submit something.
    2. Close topcoder arena after 1 hour of "not solving anything", seeing your rank is too low even if your 400 miraculously passed.
    3. Read this comment and see that just 400 was enough.
    4. Open arena 10 hours after round end and realize you qualified.
    5. WTF, how did this happen
    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think problem 400 was nice for people who like ifs a lot. I'm not sure I like ifs quite so much :(

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

    You can also solve the 400 by checking if any pair or triplet of numbers can reach the target (also handling the case where n=1 correctly).

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

    I solved it by bfs on reachable states. Every number 2i3j is a pair i, j. There 9 different types of pairs (first and second coordinate could be <,=,> then in t). It could be proven that every type of pair could be useful not more than twice. Then I made search on this 39 states.

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

      I had the same approach. How to prove it?

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

        Consider about 10 cases =) I haven't done it during round, and for sure submited 4^9 states solution.

        → Reply