decoder123's blog

Topcoder Single Round Match 694
By decoder123, 8 years ago, In English

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.

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

Comments Comments (27)
| Write comment?
»
8 years ago, # |
← Rev. 2   Vote: I like it +26 Vote: I do not like it

Did you mean tomorrow? Now fixed, thanks!

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

Starting in about 30 minutes.

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

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

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

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?

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

    If some group is empty — you can move any element from other group to this one and it will not decrease your score (because a^b<=a+b).

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

    How can you meet in the middle? I guess on masks? Mask halves are not independent, e.g. 10|00 and 00|10 may be bad masks, but 10|10 is good.

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

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

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

    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).

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

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

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

    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).

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

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

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

        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.

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

          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).

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

            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.

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

              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;
}
              → Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it +5 Vote: I do not like it

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?

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

    Maybe they googled the same solution to some similar problem.

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

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

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

      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.

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

How to solve div2 1000?

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

    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)

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

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.

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

    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).

    → Reply