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

Fun SRM / Pittsburgh regional round
Автор Swistakk, история, 7 лет назад, По-английски

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

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

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

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

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

    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.

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

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

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

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

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

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

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

    So, is it rated?...

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

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

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

    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.

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

      "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?

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

How to solve 1000?

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

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

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

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";
}
→ Ответить
  • »
    »
    7 лет назад, # ^ |
    ← Rev. 6   Проголосовать: нравится +1 Проголосовать: не нравится

    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.

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

      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

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

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

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

          Three ones

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

            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.

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

              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)

              → Ответить