cgy4ever's blog

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

Topcoder SRM 711

Time: 5:30 am EDT Saturday, March 25, 2017

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

Update: we moved the SRM 1 week later (and the start time has been changed).

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

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

It clashes with VK Cup 2017 — Round 1.

→ Reply
»
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 +2 Vote: I do not like it

I've started Data Science Weekly Challenges series for competitors in Algorithm and Marathon tracks. SRM 711 is the chance to jump in the first challenge — the lowest-rated person who will get a bye to Stage 2 of Algorithm Competition will get a TCO'17 t-shirt!

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

Contest will start in 17.5 hours.

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

Can someone please explain solution for Div1 500?

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

Hello, I was the writer of this round. This time we tried to make problems easier than usual. May be div1-hard should be more challenging. What do you think?

Here's short hints:

div2 easy, SquareMaking

hint

div2 medium, StringTransform:

hint

div2 hard, TreeMovingDiv2:

hint

div1 easy, ConsecutiveOnes:

hint

div1 medium, OrderedProduct:

hint

div1 hard, TreeMoving:

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

    Does random generator ensure that we get correct trees in div2 hard?

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

      Yup, this can be proven. Look at i-th tree as rooted tree with root at roots[i].

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

        Will there be a full fledged editorial or do you think that hints are enough? :)

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

    Arterm whats difference bw div1 and div2 hard 1000 pts.

    you gave same soln

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

      In div2 hard n and m up to 50, which allows O(mn^3) solutions.
      In div1 hard n and m up to 500, intended solutions works in O(mn^2) and O(mn^2 \log n). Unfortunately, some O(mn^3) managed to pass too.

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

    Can you please explain the solution a bit more of div1 medium?

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

      contains_one(int n): number of sequences of length n with at least one one with product X,
      greater_one(int n): number of sequences of length n with each element greater than one with product X.

      To calculate contains_one go over amount of ones (we should take at least one):
      contains_one(n) = sum(i = 1..n-1) choose(i, n) * greater_one(n-i)
      greater_one(n) = total(n) — contains_one(n)

      total(n): number of sequences of length n with product X (no restrictions on elements).
      To calculate total(n) we iterate exponents and assign primes[i] independently, hence:
      total(n) = product(i) choose(a[i], a[i]+n-1)

      Result is sum of greater_one(i)

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

Come on guys, I don't remember when was the last time I solved any TC problem faster than today's Div1 500. It deserves to be 250 pts at most xd.

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

I take some time to investigate where is wrong in my input parser of Div.1 Hard. And Finally find the wrong thing is the explaining of example...

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

    I managed to make different samples in div2 hard and div1 hard, but copy-pasted the explanation. Sorry for that.

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

In Div2 Hard if try removing every edge that is not a bridge in the resulting graph after adding removed edge from previous tree to calculate dp. Is this method correct ?

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

For Div 2 hard, I used the recurrence F(i, j, k) =number of valid ways using the first i trees,selecting edge number j from last tree ,and edge k picked from tree m - 1 (to maintain cyclic property).

I start this recurrence by calling solve() trying and removing each edge related to tree m - 1 one at a time, and going to tree 0. This procedure is followed for each tree thereon recursively. However, on sample 3 I get WA. Am I doing something wrong ?

Code

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

If we code bruteforce for Div1Hard it will perform n^3 operations "add constant on a path in tree", however random path in a random tree is very short. Were there tests to cause such solutions to get TLE? I think it may be impossible to create them, but it is also sad if such solutions passed (I didn't investigate that)

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

    You can interchange flowers (graphs of diameter 2) and bamboos. This should cause TL for such solutions. I though about that only after the contest, that's sad.

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

FML

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

Please provide Div2 hard, TreeMovingDiv2 editorial with proper explaination. I am unable to understand after looking others solutions.

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

When will full editorial be published ?

→ Reply