Get Time
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat  | Threaded  | Tree
Previous Thread  |  Next Thread
Editorial | Reply
The editorial for this round written by espr1t is now available in the Wiki.

As it's in the Wiki, there's a possibility to improve it. It can be language correction, wording improvement or additional explanation in some parts, your additional comments, description of alternative solutions, etc. If you want to improve the wording of editorial writer or correct some language error, please feel free to put your change over the original text. And if you wish to add a comment or describe another approach, there's a section for this at the bottom of each problem.

Before editing, please be sure to check the following guidelines.

After approximately 1 month passes, we'll review the editorial once again, clean it a bit if necessary and make that version final (i.e. its editing will no longer be possible).
Re: Editorial (response to post by [[rng_58]]) | Reply
Please + this post if you like the editorial (want this writer to do more editorials) and - this post if you don't like it (don't want this writer to do more editorials).

We will use your feedback when selecting editorial writers for the next SRMs.
Re: Editorial (response to post by [[rng_58]]) | Reply
espr1t, would you please provide working code for each problem in the editorial? Thanks.
Re: Editorial (response to post by hacker007) | Reply
Yes, sure! This should be done already :)
Re: Editorial (response to post by espr1t) | Reply
This part from div1 medium:
"we use a really well-known trick: we do an iterative version of the DP, in which only the last and current level are stored." is really short. More details could be better. It took me while to understand.

Also I came up with a solution that uses only one array for dp. The code is this:
dp[0] = 1;
for(int i = 0; i < possible.size(); i++) {
	int v = possible.get(i);
	for(int j = 0; j < dp.length; j++) {
		if((j & v) == 0) {
			dp[j | v] += dp[j];

So basically we keep in dp[bits] the number of sums by which we can reach bits combination. It works because (j | v) > j.

Nice problems by the way:)
Re: Editorial (response to post by covganet) | Reply
Oops, sorry about that. I assumed everyone knows it by now (it is really common in TC), but that's definitely not a good assumption to do in an editorial :)
About the second part you are also right, since with each new number we add a bit, i.e. the state, if represented as a graph, is a DAG, we don't need two levels. But since the required memory in both cases is really small (and time complexity is the same), I thought the other option will be more understandable and straight-forward.

Sorry again for not clarifying well what I meant. I will edit it and explain it further soon.
Re: Editorial (response to post by espr1t) | Reply
Also, I think it would be a good idea not to write numbers like 11881376, but instead 26^5 (or at least explain them). Same goes to 8192, 4096 etc.
Re: Editorial (response to post by PlayLikeNeverB4) | Reply
Since I've used that only in the code, I assume that's the place you are referring to. If I wrote 26^5 there I would have an array with 31 elements, quite insufficient for the purposes of the problem.
Re: Editorial (response to post by espr1t) | Reply
I guess you took things too literally. 26^5 was meant to be 26*26*26*26*26, not the xor operation.
Re: Editorial (response to post by espr1t) | Reply
Well, I think division 1 level 2 have another solution, and the complex can reduce to O(S*2^K):

In your DP solution, you use a bitmask DP to represent the status. But I think maybe it is not necessary.

At first, I check every "special number" x, if n mod x != 0 or gcd(x, n/x) != 1 then we erase x from the special number list, because they will never show up in the result. Then I just run brute force algorithm. The complex will be O(S*2^K). And the implement can be as simple as brute force algorithm.

my code:
HASH <long long, long long> hash;
for_each x in special number
    if n mod x == 0 and gcd(x, n / x) == 1
        for_each element i in hash
             if (n mod (i->first * x) == 0) {
                  hash[i->first * x] += i->second;
        hash[x] ++;
return hash[n];

It is not difficult to proof that at every moment the size of hash will always not larger than 2^K.

for example, let's assume N = 2^1 * 3^3 * 5^2 * 7^4
and your bit status may be: 0 1 1 0
but I directly use their product: 3^3 * 5^2 as an status in my hashmap.