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...
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..
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.
Is there anyone who can write the announcement (as codeforces blog) of TCO Round 3B?
Yes, you
You see, you haven't created it and now people have no place to discuss it even though it is over :(
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?
To make fun ;p
What does "Fun" SRM mean? Is it not a rated match?
I think regional rounds/fun SRMs should not be rated for Div1 users :P
So, is it rated?...
I had this concern and talked with t-mac on the topcoder slack channel. You can try asking him about his thoughts on this.
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.
"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?
How to solve 1000?
Hint: calculate dynamic for every vertex d[v] minimal negative cost you need to pay to get into 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)
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.
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
I don't get you. Mind giving an example on which I would get a WA?
Three ones
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.
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)