Dutzul's blog

TCO 2015
By Dutzul, 9 years ago, In English

Tomorow , 11 april TCO 2015 Round1A will take place ,

http://tco15.topcoder.com/algorithm/schedule/

time-date :

http://www.timeanddate.com/worldclock/fixedtime.html?msg=TCO15+Algorithm+Round+1A&iso=20150411T12&p1=98

good luck to all the participants !!!

ps : how do i register to it ? its the same like any regular srm?

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

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

Yes, it runs exactly like an SRM. It's still a match, just not a single-round one :D

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

    so registration starts five minutes before round, right?

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

      RIP English; it should start 3 hours before and end 5 minutes before the round. I guess.

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

codeforces is unnecessary

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

    You know what is unnecessary? Spam comments. (as in: comments that are unrelated to the topic of the blog post)

    When spam appears, downvotes are necessary.

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

Does anyone know how exactly byes work this year? If I am among 250 top rated members, does it mean that I automatically advance to round 2 and I cannot take part in Round 1A?

If yes, will there be any parallel round?

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

Can Division 2 competitors in TopCoder register for TCO 15?

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

rated?

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

I'm new to Topcoder. So, can anybody tell, how to hack here (is it similar to Codeforces)

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

    Hacking round (Challenge phase) starts five minutes after coding phase and lasts 15 minutes.

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

I can't register. It said registration was by invitation only. Did anyone meet the same problem?

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

Does anyone have problems with opening web-site (http://topcoder.com/tc) or arena? I can't enter. Thanks.

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

broadcast after the round:

Any positive score advances to round 2. Congratulations to all advancers!

lol ... even easier than gcj prelims. (I only solved 250. I don't feel that I should advance).

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

What is the solution for 1000?

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

    Hall's theorem. Then just check every subset of one side of the graph.

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

      So, the best overall way of how I could have solved it is by typing "bipartite graph perfect matching conditions" into Google. Hall's theorem comes up a lot on the first page.

      I guess that's an important skill too: intuition about when to go to the library.

      I converted the problem into something to do with the structural rank of the nxn matrix, then got stuck in that idea and fell asleep.

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

        Yyyyy, man, Hall's theorem is the first thing one should learn after getting know what a "matching" is. It is absolutely basic theorem when dealing with matching and you dare to say that main difficulty was to google it >_>...

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

          Judging by the voting pattern, my guess is you have 7 socks.

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

          I think many people learn new stuff when they see a problem that uses it. I've probably solved more than hundred matching / flow problems but this is the first one that I used Hall's theorem, so I don't find this surprising at all..

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

    Another keyword is a constricted set.

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

Any cool solutions for the first problem with bigger constraints?

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

    If the range is long enough (10^10 is plenty), the answer is 10. Otherwise use brute force. This is an O(1) solution for the general case. Does that count as "cool"? :)

    Oh okay, 10^20 is a lot. Instead you can construct all reachable sets of digits like this: go from the left to the right, remember the set of digits you already used, and whether you match the prefix of L so far, the prefix of R so far, or are already somewhere inbetween. (In the first two cases the set of digits you can use next is restricted.) Then do the less-brute force step in (2^10)^2 to find the best solution. (Disclaimer: I haven't tried actually implementing it.)

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

      I've implemented your second approach during the contest, but with brute force instead of DP, but the idea is clear here. But DP doesn't seem to be cool :p

      If the range is long enough (10^10 is plenty), the answer is 10. Otherwise use brute force.

      What do you call "brute force" here? Is it fast enough? I am looking for solution which would work for some giant constraints, arbitrary numeral system, etc.

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

        You kind of missed my first point. What I tried to say is that this problem is cool because all large instances are actually very easy, and you have to solve only the small ones. That is an unusual property.

        If you skip that optimization and always run the solution I sketched in the second paragraph, its time complexity will be O(n2^b + 4^b), if L and R are n-digit numbers and we are solving the problem in base b. In particular, this is fast enough for huge numbers and base 10.

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

          Actually you can do second part in O(2b * b) -- just push numbers to all submasks cutting bit by bit.

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

    cannot prove it, but my thought is like this:

    for each bitmask 0 ... 2^10-1 (representing digits) find the smallest number in [L, R] that has the corresponding digits. find next number with those digits (and that is not next_permutation) and check if it is in [L, R].

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

BTW, on 250, this solution also passed:

For each i in [L,R] and each j in [i+1,i+1000], ans = max(ans,shared_digits(i,j))

Even replacing 1000 with 100 still passes :P

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

    Why 100, I tried with 9 in the contest. The logic was to swap last two digits and get all the matched characters. There are many flaws in that. Can you prove why 100 is sufficient?

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

      Sorry, I cannot prove it. The main idea reason I thought it would work is for swapping the last two digits as you said (and catching a couple other things). 9 is only sufficient for swapping the last two digits if those digits are 45->54 though, like 37-73 requires a lot more.

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

Hey, can someone explain how the 250 point problem has to be done?

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

    Here is my idea (passed)

    first , given two numbers how can i find their similarity?

    Assign to both number a list of 10 bits , (bit number i is one if the digit appears at least once in the given number otherwise its 0) ;

    One can see that this list can be stored using an integer <2^10 using binary representation;

    Now you just iterate from L to R and for each number you brute-force (using backtracking) any combination of its digits (one number can have at most 5 digits) and then you check whether the resulting bit-mask has appeared before in some past value.

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

How to solve 500?

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

    Notice that if two tokens are ever on the same square, they will continue to be on the same square for the remaining turns, so a sufficient and necessary condition for two tokens to be on different squares after any of 1, 2, ..., K turns is for them to be on different squares after K turns.

    Then, find, for each square s, where a token on that square would be after K turns. Call this square out(s). For a set a1, a2, ..., ai of squares such that out(ai) = s for all i, at most one of them can have a token, so multiply the final answer by i + 1. Do this for all s to finish.

    One implementation detail is to find out(s) without doing a dfs of depth K ≤ 109. You can note that there must be a cycle after at most N turns. From here, either do something like K = min(K, N + 1) or do cycle detection (keep track of last_visited for each square).

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

      Thanks!!

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

      The last part can also be solved using the same principle for finding the lca of a tree. Pre calculate the distance between every power of 2 up to 2 ^ 30 and for each token its final position can be calculated in O(logN).

      → Reply