Swistakk's blog

Fun SRM / Pittsburgh regional round
By Swistakk, history, 7 years ago, In English

I see that in 2,5 hours there is a fun SRM, so I thought I would let you know cause I learned that coincidentally and I see no blog about it (but expect it to be probably significantly easier than Div 1 :( ). If I did everything correctly, here is its time: https://www.timeanddate.com/worldclock/fixedtime.html?msg=Fun+SRM+%28Pittsburgh%29&iso=20170908T19&ah=1&am=35 P.S. clist.by shows this: https://www.timeanddate.com/worldclock/fixedtime.html?msg=TCO17%20Pittsburgh%20Event%20/%20Fun%20SRM&iso=20170908T1700&ah=6&am=0 which is 2 hours earlier, but Arena's schedule says what is in first link...

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

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

This is the second time in row I find there is an SRM by complete luck. (Thanks to you this time).

Any idea why isn't topcoder or cgy4ever letting us know about them? Why don't they send emails and why just making it in general so hard to track their rounds..

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

    Actually I learnt this from e-mail reminder called "Two FUN, Rated SRMs & More: Topcoder Data Science Newsletter", but TC sends a lot of spam, so I think that people simply learned to ignore these.

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

    Is there anyone who can write the announcement (as codeforces blog) of TCO Round 3B?

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

      Yes, you

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

      You see, you haven't created it and now people have no place to discuss it even though it is over :(

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

        I didn't notice your reply so I didn't write this. But why didn't you post the blog instead of replying my comment?

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

What does "Fun" SRM mean? Is it not a rated match?

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

I think regional rounds/fun SRMs should not be rated for Div1 users :P

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

    So, is it rated?...

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

    I had this concern and talked with t-mac on the topcoder slack channel. You can try asking him about his thoughts on this.

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

    Just to make it clear for people who will read it later — Swistakk wrote this comment before system testing, not knowing his result yet :)

    Making it unrated for div1 users will decrease number of participants even more :) In previous one we had several red coders who didn't solve last task, so at least that problemset was challenging enough. I agree that today contest was more straightforward though.

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

      "Just to make it clear for people who will read it later — Swistakk wrote this comment before system testing, not knowing his result yet :)" — did you mean something like "this is his true heart opinion, it was not meant to be complaining about failing systests again" or "he pretends to be smarty pants here but systests showed him where his place is" :P?

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

How to solve 1000?

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

    Hint: calculate dynamic for every vertex d[v] minimal negative cost you need to pay to get into it.

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

Can someone give me a small hint on the 600? I see DP solutions but don't get the main idea.
Edit: only if it its difficulty is like Div. 2 600, not if it's like a Div. 1 600 (no point in me practicing that level). Thanks!

The 250 was like Div. 2 level nowadays. So here's a one-statement solution for it.
Just For Fun, since this is the Fun SRM (tm)

string isMatch(string S, string T, int p = 0) {
	return S[p] ? S[p]==T[p] || 1-string("0oo01ll1mnnm").find(S.substr(p,1)+T[p])%2 ? 
               isMatch(S, T, p+1) : "Impossible" : "Possible";
}
→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 6   Vote: I like it +1 Vote: I do not like it

    To me it's a Div1 250 or maybe hard Div2 500 if that answers your question.

    Now for the solution:

    Trivial Solution that will TLE: Just do a regular backtracking with a vector, and keep all numbers you took, to add a number, just iterate on the vector, and make sure no 3 numbers would be divisible by 9.

    How to improve it:

    Notice that since we care about divisibility it's the same as taking every number modulo 9.

    Now for each class from 0 to 8, do you ever want to keep more than two numbers of this type ? The answer is no, since any future number you choose must be the third, it's enough to keep for each modulo from 0 to 8, if you have 0,1 or 2 frequency of that class.

    You can mask the frequencies by using a ternary mask. ( Like you use a normal mask, but instead treat it as in base 3, so you have 0,1,2 for each bit), or you can use two binary masks.

    Then let dp[i][msk] represent the maximum number in the sets you can keep while being at index i, and having mask msk. Solution is max(dp[n][m]) for all valid masks m.

    Complexity is n*(3^9)*9.

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

      Your key idea is not true. We want to keep either 0, 1, 2 or all numbers of fixed type. That gives 4^9 possibilities

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

        I don't get you. Mind giving an example on which I would get a WA?

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

          Three ones

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

            Correct answer is 3, and so does my algorithm/code :).

            I don't think you understood me correctly ( or maybe I wasn't clear enough).

            Whenever you keep a number, you add 1 in the transition, so you don't care about how many numbers are truly in the mask, only min(2,frequency) for each class.

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

              Yeah, it was not clear to me what you're doing. You said that we never want to keep more than two numbers for fixed remainder and it is more natural to think that you meant keeping in final set, not keeping in dp state. But now I see what you're doing and that's first solution better than 4^m that I see (where m is our modulo, here 9)

              → Reply