cgy4ever's blog

Topcoder SRM 705
By cgy4ever, history, 8 years ago, In English

Topcoder SRM 705

Time: 9:00 pm EST Wednesday, January 11, 2017

Calendar: https://www.topcoder.com/community/events/

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

Comments Comments (31)
| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by cgy4ever (previous revision, new revision, compare).

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

Update: we added one more SRM on Jan 11th and moved the SRM on 14th to 21st.

So we will have 3 SRMs in January! See details: 705, 706, 707

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

    Hope to some really creative problems, like all other problems that you set! :)

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

This round will start in 22.5 hours, it will be sponsored by Blizzard:

Topcoder Open Sponsor, Blizzard Entertainment, is hiring Topcoder members. Join Blizzard reps on January 11, 2017 at 20:00 UTC -5 just prior to SRM 705 for a chat session in the Arena to learn more about their career opportunities. They are going to be there answering your questions and telling you all about life at Blizzard.

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

Are there any ideas for Div.1 medium?

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

    Here's the idea. This problem is really tricky...

    Say that positions i, j are "equivalent" if they can be collapsed to the same box under some functions. You can compute equivalence just by a dfs.

    Now, let in[] denote nonempty boxes. If there are i, j such that in[i] = in[j] = 1 and i, j are equivalent, apply the sequence of moves to put i, j in the same box. If not, quit and return the number of 1's in in[].

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

      But, how to prove it's correct?

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

        Proof: Note that applying a move cannot increase # of boxes with a coin.

        Say some boxes are nonempty. If no two nonempty boxes are equivalent, then you obviously can't do anymore. Otherwise, say i, j are equivalent.

        It suffices to show that applying the sequence of moves to put i, j in the same box doesn't mess up the final answer.

        To show this, say up to the point before we start merging i, j, we've done some sequence S of moves. Now, after merging i, j, apply S again. Now, note the nonempty boxes now are a subset of the nonempty boxes before merging i, j, so we're happy.

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

          After we merge i, j, although the ans decreases, but the positions of nonempty boxes has changed.

          Do you mean apply S twice will make positions of nonempty boxes stay in original place(or some positions just disappear)?

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

    Let's compute whether we can force i-th and j-th tokens to be in the same bin (it is easy to see that this is equivalency relation). After that it is easy to calculate the answer (it is just the amount of equivalency classes). How to find all equivalent pairs of indexes: . Also if one of our functions is f and then . It is easy to see that we can generate all equivalent pairs by bfs-ing on reverse edges in graph of pairs of tokens where there are forward edges .

    UPD. Actually, this is not equivalence relation, see I_love_Tanya_Romanova comment below.

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

      Are you sure it is equivalency relation?

      Take an example with 3 bins and 2 rules:

      0 0 2
0 2 2

      We can force 0 and 1 to be in the same bin (bin 0) as well as we can force 1 and 2 to be in the same bin (bin 2) — but we can't move 0 and 2 to the same bin.

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

        Yes, you are right. Now I understand why my solution fails.

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

Pretests today are too weak. Why don't TopCoder add some big random test cases as usual?

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

    TopCoder has pretests? I didn't know,i thought there are only examples,there are always a lot of hacks.

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

What's the intended complexity of the hard? I think I had n/2 * 2^(n/2), but it timed out.

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

    Usually "Unusual Time limit" means TL is just 2x ~ 3x of reference solution in Java, so details mater.

    You may need to change 25 to something else to make it faster (or say, to improve it to O(2^(n/2) * sqrt(n))).

    Btw, TL looks more tie than I thought, somehow solutions run in Arena are much slower than MPSQAS.

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

      Btw, TL looks more tight than I thought, somehow solutions run in Arena are much slower than MPSQAS.

      If it's true, someone should investigate it. It's a serious issue.

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

I think I was lucky today:



My idea for finding cycle was inefficient and thought it would fail. But some how it passed. I ran system test for about 10 times. 8-9 times, the runtime for 6th test case was around 1.99s. For rest of the cases(1-2), it failed to pass.

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

My code for Div1 Hard is O(max(2^S*n,2^(n-S)))

I set S=28,And then I failed system test

After contest I set S=27 and I have accepted it

Good Game

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

Div 1 Medium of this contest is almost the same as problem TAP2016E on SPOJ.

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

    Hmm.. I'm not very surprise if this problem was studied by others before (even it is from a book or paper few centuries ago). What makes me surprise is that 'Nlogonia' appears in both TAP2016E and Div1-Easy.

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

      Its certainly related to the following problem whose name I can no longer recall... say that you have N boxes and some moves, and say that after applying some sequence of moves you can get everything to one box. How long can the shortest sequence of moves doing this be? There is an upper bound of O(N3) (proven using same technique as div 1 medium) and a lower bound of O(N2) (some construction that I can't remember). But its unsolved what the actual answer is.

      Its on Wikipedia, I'll link if I remember the name.

      EDIT: Its called a synchronizing word.

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

can someone give me a hint for div 2 hard? thanks

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

Can I get some help with Div 2 medium? Any pointers or reference to core algorithm?

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

    you form a graph with the characters in each word then the answer is possible if and only if the graph has no cycles

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

How to solve Div1 Hard?

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

    From above comments, it seems to be meet in the middle.

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

    Let s_i be the set of lamps that button i could change,then we could do gaussian elimination on {s_i}.Let x be the number of i that s_i has a pivot after elimination.For the small x,we can decide whether to choose each s_i with brute force and time complexity is O(2x).As for the big x,there are only 50-x lamps that are not pivots and we could do something like bitmask dp and the time complexity is O(x * 2n - x).So the final complexity is min(2x, x * 2n - x),which is approximately equal to

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

Hahaha, what a funny concidence. Today I read problems (I didn't participate since it was 3AM in Poland) and hard turned out to be almost exactly the same as problem J from Chinese contest from Petrozavodsk Winter 2015. What is funny is that together with Marcin_smu we virtually participated in that contest like 10 hours before that SRM xD. What is more is that I also perfectly knew medium problem (it appeared for example here: http://main.edu.pl/pl/archive/ontak/2008/ktb (only Polish version and it asks whether answer==1, but that is same problem)). It looks like I missed a good chance of scoring all problems and getting second place on TC two times in a row :P.

EDIT: OK, I just read in comments, that relation in med is an equivalence relation xD. So likely it would have turned out I will encounter some troubles :D.

→ Reply