Блог пользователя decoder123

Topcoder Single Round Match 694
Автор decoder123, 8 лет назад, По-английски

Tomorrow at 19:00 MSK will be held Topcoder SRM 694.

Let's discuss problems after contest!

Thanks to dened for pointing out the mistake.

  • Проголосовать: нравится
  • +67
  • Проголосовать: не нравится

»
8 лет назад, # |
← Rev. 2   Проголосовать: нравится +26 Проголосовать: не нравится

Did you mean tomorrow? Now fixed, thanks!

→ Ответить
»
8 лет назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

Starting in about 30 minutes.

→ Ответить
»
8 лет назад, # |
  Проголосовать: нравится +28 Проголосовать: не нравится

Looks like chrome quitted when he got what he wanted (top 10 contributors) ;)

→ Ответить
»
8 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

What is wrong with the Meet-In-The-Middle approach in 500? i tried it but got WA on example 4(my code returns 940008).

Also i have seen some coders in 250 were not care about condition "groups should't be empty". Is there countertest?

→ Ответить
»
8 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

How to solve Div1-900? I saw people used MaxFlow, but didn't figure out how.

→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +26 Проголосовать: не нравится

    Move from A[i] to A[i+1]-A[i]; there's flow V[i] from L[i] to R[i]+1. The condition for equality of all elements is now a flow condition (what flows in flows out).

    → Ответить
»
8 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Can someone please shortly describe the solutions for first two Div. 1 problems? Failed both of them on systests :)

→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    250 hint: achievable xors are small (up to 256).

    500 uses a well-known algorithm for computing something for supersets (or subsets) if we know it for given sets, in O(N·2N).

    → Ответить
    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      Could you please elaborate on the well known algorithm for the 500? Where does one learn such algorithm?

      → Ответить
      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится +20 Проголосовать: не нравится

        Idk, I figured it out myself.

        You start with something for each set of numbers from 1..n. You want the sums over all supersets of each set s, so you compute the sums over all sets s' where if x ≤ k and otherwise. For k = n, it corresponds to what you started with; for k = 0, it's what you want; for k < n, it can be computed using at most 2 values for k + 1. Think how.

        → Ответить
        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Looks like your solution is harder than mine.

          Let's fix two strings. They make some masks bad. All such masks are submask of mask constisting of all positions where these two strings have equal chars. We can find such bad supermasks for all pairs of strings in O(n2m). Now we should mark all the submasks of bad supermasks. It can be easily done in O(m2m).

          → Ответить
          • »
            »
            »
            »
            »
            »
            8 лет назад, # ^ |
              Проголосовать: нравится +20 Проголосовать: не нравится

            I was asked to describe in detail, and described in detail/formally/generally, the part

            Now we should mark all the submasks of bad supermasks.

            which I initially described as

            a well-known algorithm for computing something for supersets (or subsets)

            Our solutions are the same.

            → Ответить
            • »
              »
              »
              »
              »
              »
              »
              8 лет назад, # ^ |
                Проголосовать: нравится -12 Проголосовать: не нравится

              No way. Your approach is hard-to-come-up-with dp, mine is something like DFS or even easier.

              for (int mask = (1 << m) - 1; mask > 0; mask--)
{
    if (!bad[mask]) continue;
    for (int k = 0; k < m; k++)
        if ((mask >> k) & 1)
            bad[mask ^ (1 << k)] = 1;
}
              → Ответить
»
8 лет назад, # |
← Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

I noticed that many codes for 250 are incredibly similar. I mean that the algorithm is absolutely identical, most differences are variable names (the rest: order of two conditions, initialisation to 0 or -inf, omitting a redundant bitmask, making N global — all trivialities). This... can't be even cheating, it's too obvious. Could so many people be learning it by heart from the same resource?

Has cloning advanced so much?

→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    Maybe they googled the same solution to some similar problem.

    → Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    The problem is too simple to have different approaches, isn't it?

    → Ответить
    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится

      The simplicity necessary for this to be a coincidence is at the level of div2 50pt. Something like "add N numbers". The differences are cosmetic, most of them are just variable names. I initially thought I opened the same person's code several times in a row by mistake.

      My code looks completely different and uses a somewhat different way to count the same thing (no recursion, two less array dimensions). There are other codes somewhat similar to mine, although none as similar as this. There are a few outliers which look very similar to the template I'm talking about when I look better at what they're doing, but not first-glance identical, for example by using a loop instead of backtracking.

      It looks really weird.

      → Ответить
»
8 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

How to solve div2 1000?

→ Ответить
  • »
    »
    8 лет назад, # ^ |
    ← Rev. 4   Проголосовать: нравится +9 Проголосовать: не нравится

    This was my second TC contest.My solution failed in system test for case n=1. The problem can be solved using dynamic programming.



    for(int i=0;i<n;i++)

            ans = (ans + count( n-1 , k-(i*(n-1-i)) ) )%MOD;

    Basically we have to increment n from n-1..while making this change there are n positions possible for n.Suppose we add it in position i(starting from 0) , Then there will be i*(n-1-i) new triples.This causes the dp relation as I have mentioned in the code.(also remember that you have to store answers in dp table)

    → Ответить
»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why there are so strange limitations in 250div1? I was sure that O(nC3) will pass but wrote O(nC2) . I think that O(nC2) solution is nice but the problem is really bad because stupid solution passes.

→ Ответить
  • »
    »
    8 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    My O(nC2) solution with memoization got TLE on one of the sample test cases; therefore, I had to rewrite it in a bottom-up approach. I was very surprised when I saw O(nC3) solutions could pass. Maybe this is the reason why they wanted to extend the time limit a bit (which ultimately caused asymptotically slow solutions to pass).

    → Ответить