Egor's blog

SNSS Round #4
By Egor, history, 9 years ago, In English

Contest is finished, you may discuss problems

My screencast

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

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

Is it really finished? It says "end: 25 Aug 2015, 22:00:00". Though looking at the screencast, now it should be forcibly finished...

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

    It seems both views were by myself, so I think it should be ok

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

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

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

I appreciate that all of you was able to find out link when the contest was still up, but had you noticed that video on that link wasn't available at the time?

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

How to solve C? And question about B, could you please give me an counter-example for my algo?
Algo is greedy. Start from the leftmost disk to the rightmost. Build machine queue, starting from empty queue. For each disk try to match machine type from the queue. If machine is not found add new machine with certain type to the end of the queue. Calculate max time.
Example,
disk -1: 3-2-1
disk -2: 1-2-3
Start building queue from 1-2-3. Since machine queue was empty from the beginning, after disk(-2) it looks like: 1,2,3. Steps = 4
Start matching disk(-1): type 3 matches last machine in the queue, so add 2 more machines with types 2 and 1. After disk(-1) queue looks like: 1,2,3,2,1. Total number of steps = 5. Got WA on 6th test.

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

    Counter-example:

    3
1 2 3
2 3 1
3 2 1

    Correct answer is 6.

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

    If gcd(a.len, b.len) = 1, then we compare each character of a to each character of b corresponding number of times

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

      Thank you, Egor! Your answer and screencast helped me.

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

How to solve A and E?

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

    A — for each connected component in the graph check that it is bipartite. Then use DP similar to knapsack putting all components there to find out what sum close to N / 2 you can get. DP[x][y] should be something like whether you can get a total of x people in one hall if you put people from last y components. After that you can restore the answer greedily starting from the component containing first scientist, if you can you need to assign him to the first conference hall which will give lexicographically smaller result string.

    → Reply