Hi All,

Topcoder Single Round Match 701 will be held 26 October 05:00 PM BDT

Wish you all good luck. Let's discuss the problems after the contest .

**EDIT :** This match is sponsored by booz allen hamilton. winners will get t-shirts from Booz Allen Hamilton .

The match announcement promises t-shirts from Booz Allen Hamilton again (and this should really be included in the blog announcement, not in the comments). Not sure whether this is a copy-paste error, I guess we'll just have to wait and see :-)

I could not find the t-shirt announcement in the web arena. ( It only mentions sponsored by BAH). I guess its there in the applet. To popularise it better, the announcement should also be put in Web arena.

What's the criteria for getting t-shirts?

I would prefer srm announcements from one person and I think that cgy4ever is the best option. Finding an old discussion would be so much easier then, just scrolling through his blogs. Searching the blog in google or in codeforces-search doesn't give instant results sometimes.

then I will cordially request cgy4ever for posting srm announcements from next SRMs

I think a special account made for Topcoder admins is an even better option.

Okay, I will add a blog for each SRM once I know it — so you can view my blog to see the schedule of upcoming SRMs.

And I will update it about 24 hours before the contest so that it will be in the "recent actions" list.

Has anyone used the Web Arena recently? Has it improved? (e.g. stable to use, can challenge normally, etc.)

Also is there any way to generate class definition, test codes... for the web arena?

It is definitely a lot more stable than it was before. Not faced any issue in the past few srms i participated.

I have not yet found any method to generate these.

The competition just finished. Can someone please tell me how to solve Div2. 1000 pointer ? I partially computed the state (win/lose) for numbers upto 1,000,000. For numbers greater than that I used recursion to reach numbers <= 1,000,000. But It didn't work, I was getting seg fault. Anyone who solved the problem, Kindly share the approach and if possible, a link for the code. Much Thanks.

Any hint for Div1.600 ? There seems to be a crucial insight ?

The first character of the string can either be at the first position or the last (since only reversal m affects it).

Then, of the remaining positions of the final string that aren't fixed, the second character of the original string can either be at the first position or the last, and so on...

Now use this observation to make a DP function that counts how many of the resulting strings have a prefix p. My DP state was (how many characters in front, how many characters in back).

How to solve div2 900 problem ?? Any hints

How to solve Div2 900?

I saw only one person who passed all tests.

How to view the global leaderboard ?? I could only find the room summary leaderboard. I am new to topcoder .

Active contests -->>> SRM 701 --->>> Division summary

got it. thanks..

How to solve div1 300 ?

What I did was this, the boolean value DP[0][n] denotes whether it is a winning position for Alice or not, and DP[1][n] denotes the same for Bob. I calculated these values till 1e5. Consider any 5 consecutive values of DP[0] array. There are at most 2^5 = 32 such sequences. So if you precompute till 1e5, one is bound to repeat. Using that I found the length of the cycle (let it be len). Then answer is DP[0][n % len].

`Consider any 5 consecutive values of DP[0] array.`

Why 5 elements is enough, but not 1+2+3+4+5=16?Because you take either 1,2,3,4 and/or 5 elements from the pile. So, DP[0][i] depends on DP[1][i-1], DP[1][i-2], DP[1][i-3], DP[1][i-4] and/or DP[1][i-5]. :)

Hey satyaki3794, I was looking at your code for this problem. I couldn't understand one thing. Why don't you break off the loop once you have the cycle value for the first time.I mean shouldn't the cycle value remain constant?

I tried this but this gives a WA? Can you please explain what is wrong with this idea?

Yes, cycle value should remain constant. Breaking off the loop when you get cycle value for the first time shouldn't change the answer. There must be some other bug in your code.

Hi satyaki3794, even i tried by the same approach but breaking off when i get the cycle for first time fetched WA. Gives AC when submitted without the break statement.

Codeusing namespace std;

int dp[2][200]; int mask[100];

class PartisanGame { public: string getWinner(int n, vector a, vector b) {

};

I'm trying to understand why you picked 1e5. If each group has 5 things and there are 32 possible groups, then after 5*32=160, the next group should be a repeat. So is checking 165 enough, or was 1e5 significant for some other reason? Thanks.

(I just noticed that 165 and 1e5 are similar, with e being upside down 6 :-)

165 is enough. No special reason for 1e5.

Although 6 years passed, I'm willing to leave my comment because I think something may be wrong. The answer may be DP[0][i+(n-i)%len] but not DP[0][n%len], because the repeat part will begin with position i instead of the beginning. So this also answers the Nams and BicameralMind's confusion as above.

Is this correct?

CodeI need some Help :D Here's my solution for 250 Div2

and here's my code for the 500 Div2

~~~~~ import java.io.BufferedReader; import java.io.IOException; import java.io.InputStream; import java.io.InputStreamReader; import java.io.PrintWriter; import java.util.*;

public class SortingSubsets {

}~~~~~

Both failed at System Test , So Any help will be appreciated.

I was a writer this time. That's my 4th Single Round Match at TopCoder) Sorry for inconvinience in PartisanGame, I forget to add constraint that a and b are non-empty, so this case was not present at samples. Hope you liked the tasks anyway) Short editorials:

div2-easy SquareFreeString:

Just check each substring.

codediv2-medium SortingSubsets:

Which elements will remain on its own positions after sorting? Precisely this elements we will not take to our set.

codediv-2 hard ThueMorseGame:

O(n) solution using bitmasks.

codediv1-easy PartisanGame:

One can see that we win/lose on next position for Alice and Bob depends only on last five positions, so period will be not greater than 1024 (in fact, maximal period is around 20).

codediv1-medium KthStringAgain:

One can notice that strings in the collection can be obtained using following pseudocode:

Using this, we can easily calculate number of strings with given prefix.

codediv1-hard FibonacciStringSum:

This hard intended to be easier than usual.

One can notice and prove that for fixed a and b answer f(n, a, b) will be linear combination of f(n-1, a, b) ... f(n-2 * (a + b + 1), a, b).

Coefficients of linear reccurence can be found using gauss elimination or directly (say, using generating functions or other reasoning).

code`One can see that we win/lose on next position for Alice and Bob depends only on last five positions`

How to prove this formally?

Could someone explain the solution for Div2. 900 ? Thanks.

You store the answers for last 50 states (one can use queue, but the writer has done using bit masks). I understood it. It is quite elegant. The idea is to reduce memory while the time complexity stays the same.

I can't understand your code for Div2 900...

Could you please give some hints?Thank you very much for that.

Finally I understand it.

Very nice problem. Thank you~

Why do i get tle with the following O(N) solution for div2-hard ?

Code`__builtin_popcount`

is slow. This takes 0.4 seconds in the worst case (I didn't check to see if it actually passes system test, so it may have some bug):CodeYeah , it passes now :(

i cant understand your(fauzdar65) solution. would you mind explaining?

I move from one losing position to the next losing position. If at the end i stop at n, then its a losing position, otherwise i skip n, that means it is a winning position.

0 is the first losing position. If X is a losing position, then surely X+1,X+2....X+m are winning positions as we can move to X. So, from X we move to X+m+1. If this number has even number of set bits, then this is the next losing position, otherwise this becomes a winning position, and next candidate for losing position is the next number i.e (X+m+1)+1 . So, we keep adding 1 till we find next losing position.

Why

`If this number has even number of set bits, then this is the next losing position`

?How to notice and/or prove this? I'm just trying to understand what's the intuitive way of noticing this fact and believing in it during the contest as for me the only way of thinking was to try to derive

f(n,a,b) fromf(n- 1, * , * ) andf(n- 2, * , * ) (which can be done but it requires raising 702x702 matrix to 10^{9}-th power and is most likely too slow).If you write y=(n-x), then you can expand (n-x)^b, so you can notice you only need the powers x^0, x^1, ..., x^(a+b).

This would be an intuitive reason to change the

a,bparameters, but why does this give a recurrence onn?Hmm, I guess I don't know the answer to that. This was more if you're looking to solve it by exponentiating a matrix, this is the most intuitive way I think.

Is there a way to translate the matrix to a recurrence? I'm not sure if this is even possible in general.

Yes there is.

f(n) =A^{n}_{ij}(that is any coefficient in fixed position in matrix powers) obey recurrence relation, which coefficients are coefficents of χ_{A}(characteristic polynomial). That is follows from Cayley-Hamilton formula χ_{A}(A) = 0.Take

for example.

_{A}(λ) = λ^{2}- λ - 1.So,

obey reccurence

And what is that matrix A you're talking about? It should be of size a + b. I know only the matrix of size (a+1)*(b+1)*2 (number of taken zeros, ones and the last bit).

Upd: Well, I got the solution described above: just understand, that f(n,a,b) = sum {one^a*(n-one)^b}. So you can take the matrix of size (a+b+1)*2 (powers of taken 1s and the last bit) and the answer is weighted sum of coefficients of this vector: (A^n * v0).

But the weights in this sum depend on n, so how do you get a recurrent?

P.s. I solved the problem from the different angle: I need to find sum(x_i) ^ a * sum(!x_i)^b, so need to count number of ways to choose not intersecting multisets of sizes a and b, so I just counted the answer for n,a,b with the first and the last bits fixed. After that I split n in two parts and check that both middle bits are not equal to 1. I got accepted with n -> [n/2], [(n+1)/2], and so I needed map, but actually if you divide n into (2^r) > (n — 2^r), than you don't need any map, and it works in log(10^9) * a^2*b^2.

I have a question about div1 300 ptr. I failed that problem because I did not cover the special case when the vector was empty. Was not mentioning that fact explicitly and not add it to examples done on purpose?

Also the wording in the constraints was confusing for me and I did not think about empty vector at all.

That is kind of accident and totally not on purpose, I'm sorry for that.

There was one more constraints like "a will contain between 1 and 5 elements, inclusive." Then I guess Arterm notice "all number in a will be distinct" + "all number in a will be between 1 and 5" can imply this, so he removed that constraint.

It can be confusing but we think empty set is valid based on this: https://en.wikipedia.org/wiki/Vacuous_truth

Thanks for the answer. I just want to make sure that I do understand correctly:

Yes, your understanding is right.

Yeah, that's my fault. I commented two constraints to remove "redundancy". When cgy4ever noticed that it was too late to do anything.

Can you explain me solution of div 2 hard by bitmask?

I added a quick editorial on the site: https://apps.topcoder.com/wiki/display/tc/SRM+701

Just wondering, do people find these useful? (i.e. on the actual site as opposed to a comment on CF) I just happened to do this one and 700 because I was involved in preparing the rounds. It seems the view counts are relatively low.

Yes, they are valuable. But it's hard to find them.

Thank you for giving an explicit link!

And if it is possible, could you add a few more sentences after the sentence:

`Namely, a number is winning if and only there exists a losing number.`

? :)I don't understand what that means exactly.

Sorry, I missed some words. I added a few more.

In general, all editorials can be found here: https://apps.topcoder.com/wiki/display/tc/Algorithm+Problem+Set+Analysis

They haven't been kept up to date in the past few months, so that's probably why you can't find some.

Best code ever :D

https://community.topcoder.com/stat?c=problem_solution&rm=329368&rd=16822&pm=14413&cr=22263204

Div2 hard is a kind of Bash Game.But when I used TC test,I found that data 499... 1 run 2.4s~2.7s,so I just bruteforce when m==1.When m==2,it runs 1.7s :)