BekzhanKassenov's blog

Topcoder SRM 634
By BekzhanKassenov, 10 years ago, translation, In English

Hello everyone!

Topcoder SRM 634 will take today at 21.00 EDT.

Good luck and have fun!

P.S Still cannot find decription of the match using their new site. Can anyone help me? I got it using clist.by

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

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

Another 3:00 AM-ish round (in my country). Hope I won't go to school disappointed from my failure :D

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

What is the solution to Div2 500pt problem?

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

    Let A_i be the minimum amount of people who have bought all items from 0 to i.

    Then, we have A_0 = s[0] as our base case.

    Then, we can find a formula for A_i = max(0, A_(i-1) + s[i] — N). We can derive this since we know at least A_(i-1) people have bought items 0 to i-1, s[i] people have have bought item i and there are N total people. Thus, A_i is minimum size of the intersection between the people who've bought items 0 to i-1 and people who've bought item i.

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

Just waked up 30 min before the contest and decide to enter the contest open 250
OUTAGE
open electrical generator the internet was like FLIP-FLOP ON-OFF ON-OFF waiting for ON then submit 250 but there are no another ON during contest
MY WORST SRM EVER

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

How to solve 500?

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

    It's maximum weight independent set on a bipartite graph.

    First, make a node for each red or blue segment you can draw. Then, connect two nodes if they can not occur in a configuration together. We can see that this resulting graph will be bipartite. Our answer will be an independent set of this graph, so we want to maximize the weight of it. We can do this with max flow as follows:

    • connect the source to each blue node with the score of that blue segment
    • connect each red node to the sink with the score of that red segment
    • connect a blue and red node with infinite capacity if they conflict

    We can see the maximum weight independent set is just the sum of all blue/red scores we can get minus the minimum cut. We know we can solve min cut on a bipartite graph with max flow.

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

      I got stuck in finding maximal weight independent set. How can you show a bijection between cuts and independent sets here?

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

        There is a nice explanation here (the problems are similars): http://discuss.codechef.com/questions/44798/twocomp-editorial

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

        I have an informal argument that relates independent sets to vertex covers and then vertex covers to cuts.

        We know the complement of an independent set is a vertex cover. So finding a maximum weight independent set is equivalent to finding a minimum weight vertex cover. So, now we have the problem of finding a minimum vertex cover in a bipartite graph, and it's much easier to relate covers to cuts. If we remove all the nodes in a cover, we will be left with no edges (by definition). Now, we can't cut the original edges, so we set them to infinite capacity, but we can "cut" nodes out of our graph. By doing the above reduction, we can relate cutting nodes to cutting edges, and then we can relate this to a minimum cut which we know how to solve.

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

          Now it makes sense for me, thanks a lot!

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

How to solve div-2 1000 ???

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

    Here's a rough sketch.

    Start with the string "11111...111". Then, for each character in order, try greedily setting it to zero. It can only be set to zero if the resulting string is special and is also strictly greater than current. The reason we need to check if the resulting string is still special is if ST is not a special string, where S is some arbitrary string, and T consists of all 1s, then ST' will definitely not be special, where T' is some arbitrary string that is the same length as T. The running time of this is O(N^2)

    Alternatively, there is a different solution to this that is also google-able (but it seems no one had this solution). You can see it here: http://en.wikipedia.org/wiki/Lyndon_word#Generation The running time of this method is O(N)

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

In Div 1 — 250, I simulated the process as follows: Maintain a set of all the people with number of items purchased as the key. For a new item with frequency say x, first give to all the big-shoppers then the remaining is given one by one to the shopper having minimum number of items in his bag and then the list is updated. But, needless to say, I failed the system test (got WA). What is wrong with the logic?

→ Reply