maryanna2015's blog

By maryanna2015, history, 3 months ago, In English,

SRM 721 will be held today.(in less than 18 hours)

Time: 11:00 UTC-4, September 26, 2017

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

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

»
3 months ago, # |
  Vote: I like it +26 Vote: I do not like it

Remainder: Contest starts in 4 hours, registration is open now.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve Div 1 250?

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    I used binary search to find element on day d1.

    If both left and right sum will turn out larger than needed, decrease high, and vice versa for smaller. If one is larger, the other smaller no solution is possible.

    Left and right sum with one given element can be checked by computing min and max possible sum with n*(n+1)/2

»
3 months ago, # |
  Vote: I like it +31 Vote: I do not like it

Wow, that was probably the easiest SRM I have participated in.

»
3 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Could someone explain how the Div1 800 could be converted to Max-Flows?

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +38 Vote: I do not like it

    Instead of moving tokens one by one at each time, you can imagine you move all tokens simultaneously, since if two tokens cross while moving, you can just uncross them.

    Here's the max flow graph.

    Create two nodes for every (node, time) pair (let's denote this a(n, t), b(n, t), meaning node n at time t). Create a source and sink. All edge capacities in the following will be 1.

    • For every node x with a token, connect source to a(x, 0).
    • For every node x without a token, connect b(x, t) to the sink.
    • For every edge in the graph (x, y) and every time j, 0 ≤ j < t, connect b(x, j) to a(y, j + 1) (and similarly b(y, j) to a(x, j + 1).
    • For every node x and every time j, 0 ≤ j < t, connect a(x, j) to b(x, j), and b(x, j) to a(x, j + 1).

    The max flow in this graph is the answer.

    You need two classes of nodes a, b because you need to encode the constraint "every node only has 1 token at each time".

»
3 months ago, # |
  Vote: I like it +3 Vote: I do not like it

how to solve div2 500?

  • »
    »
    3 months ago, # ^ |
      Vote: I like it -23 Vote: I do not like it

    I will try to give a hint. Probably, that will be enough.

    Every time you see a large problem space, you don't want to go through all of that space, but you want to consider only special points.

    In the case of this problem the space is the days: [1, 2, 3, ..., d1 + d2].
    We don't want to go through all of that space, but we want to consider only one special place.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there a reason to require that the graph in Div1 Hard is specifically a tree other than making the contestants explore the possibility of the solution being some kind of dynamic programming?

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Good question! One (admittedly weak) reason is that it is a natural way to reduce the number of edges in your flow graph, which helps in doing worst-case analysis for the maxflow algorithm (Dinic runs in time E^(3/2) for unit-capacity networks, for example).

»
3 months ago, # |
  Vote: I like it -31 Vote: I do not like it

I've won the match!

Aijuuuuuuuuuuuuuna would say some gauchos criollos in my area :) !!!! Poder gaucho FTW!

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I misread div1 B and started thinking about this problem:

Given n and d, what is the maximum number of pairs that can have a distance d between them?

Does it have a nice solution?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Any idea about div2 500 problem ( RememberWordsEasy ) ?

  • »
    »
    2 months ago, # ^ |
    Rev. 4   Vote: I like it +2 Vote: I do not like it

    Vary the number of words (say d1) learnt on the last day of the sem1 from 0 to w1. Let the number of words learnt in the first day of the sem2 be d2. Given d1 words learnt on the last day, let the maximum number of words learnt in sem1 be hi, and minimum be lo. For w1 words to be learnt in the first sem, the sufficient condition is hi >= w1 >= lo. For each d1 vary d2 from d1-1 to d1+1. Find a similar hi and lo here as well for sem2 and check conditions.

    To find hi and lo for a given w [words read on first day(or last)] and d [the number of days], hi = w + w+1 + .. (w+d-1)/2. And lo is w + w-1 + .. max(w-i+1, 0) ..d terms. So you get hi and lo in O(1). So the only thing that takes time is varying d1 from 0 to w1.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello, this comment can be off topic to this blog, sorry for that.

When I enter TopCoder Arena I can't read problems, it keeps loading, is there any way to fix it? Is problem in my internet/pc?

Thanks in advance.

»
2 months ago, # |
  Vote: I like it +25 Vote: I do not like it

Why did cgy4ever stop posting about SRM announcements?