### aryanc403's blog

By aryanc403, history, 6 months ago, ,

hmehta didnt made an announcement on CF :/
SRM 756 will be held today.(in less than 30 mins) Atleast topcoder site says so.

Lets discuss problems after the contest.

• +44

 » 6 months ago, # |   +23 The round was written by IH19980412. A draft of the editorial can be found here.
 » 6 months ago, # |   +18 Thanks for the nice problemset! I liked Div1 Hard that inclusion-exclusion principle works elegantly. Using De Bruijn Sequence, we can improve the solution to $O(2^N + HW)$, which is faster than naive $O(2^N \times N + HW)$.
•  » » 6 months ago, # ^ |   +36 Unless I'm mistaken, you mean Gray code and not a De Bruijn sequence. At least that's what the technique I have in mind uses: you order all subsets in such a way that each two consecutive subsets only differ by adding or removing one item, which allows you to compute the value for the new subset faster by just updating the value of the old subset.
 » 6 months ago, # |   +15 Alternative solution for Hard: go through the table from top to bottom and maintain dp with state being a vector of degrees of all special cells. It works in $nm4^k$, but we can optimise it: if we are now in row $i$, we only need to know about cells in rows $i-1, i, i + 1$. It still works slow if there are a lot of special cells in three adjacent rows, but in that case there will not be a lot of special cells in any three adjacent columns, so let's just transpose the table.
 » 6 months ago, # | ← Rev. 2 →   +10 My solution for Div1 Hard: Consider the neighbors of the undetermined cells. Intuitively it appears that there can't be many undetermined cells with more than one special neighbors (can't provide the maximum number, but the worst test case I came up with had 25 such cells). Thus, we can iterate over all of the combinations for choosing a state for those cells, and calculate the number of ways with respect to the other undetermined cells in $O(2^K*S)$, where $K$ is the number of undetermined cells with more than one special neighbors, and $S$ is the number of special cells. The complexity may be worse than the intended solution, but it avoids using the inclusion-exclusion principle.
•  » » 6 months ago, # ^ | ← Rev. 4 →   0 I've had the same idea but I seem to have a mistake in counting the number valid ways after picking a state for the undetermined cells with more than one special neighbor. Could you provide a code for your solution? What I do is that for each special cell, count the number of active cells let that be activeCnt and number of undetermined cells let that be undetCnt. if activeCnt > 3 then the whole field is invalid. Otherwise I do summation of C(undetCnt, i) such that i is in [0, min(undetCnt, 3 — activeCnt)] and multiply the output of the summation to the final result which is initialized by 1.
•  » » » 6 months ago, # ^ |   0 Here's my codeimport java.util.*; import java.math.*; import static java.lang.Math.*; public class Newgenerations { final long mod = 1000000007L; class Point { int x, y; public Point(int x, int y) { this.x = x; this.y = y; } } public int count(String[] field) { int n = field.length, m = field[0].length(); List adj[][] = new List[n][m]; int alwaysActive[][] = new int[n][m]; int oneDegree[][] = new int[n][m]; int indexOf[][] = new int[n][m]; for(int i = 0;i < n;++i) { for(int j = 0;j < m;++j) { adj[i][j] = new ArrayList<>(); alwaysActive[i][j] = 0; } } for(int x = 0;x < n;++x) { for(int y = 0;y < m;++y) { if(field[x].charAt(y) == '*') { int dx[] = new int[]{1,-1,0,0}; int dy[] = new int[]{0,0,1,-1}; for(int k = 0;k < dx.length;++k) { int nx = x + dx[k]; int ny = y + dy[k]; if(nx >= 0 && nx < n && ny >= 0 && ny < m && field[nx].charAt(ny) == 'x') { adj[x][y].add(new Point(nx, ny)); } } } } } for(int x = 0;x < n;++x) { for(int y = 0;y < m;++y) { if(field[x].charAt(y) == 'x') { int dx[] = new int[]{1,-1,0,0}; int dy[] = new int[]{0,0,1,-1}; for(int k = 0;k < dx.length;++k) { int nx = x + dx[k]; int ny = y + dy[k]; if(nx >= 0 && nx < n && ny >= 0 && ny < m) { if(field[nx].charAt(ny) == '#' || field[nx].charAt(ny) == 'x') { alwaysActive[x][y]++; } if(field[nx].charAt(ny) == '*' && adj[nx][ny].size() == 1) { oneDegree[x][y]++; } } } } } } List moreDegree = new ArrayList<>(); List special = new ArrayList<>(); int zeroDegree = 0; for(int x = 0;x < n;++x) { for(int y = 0;y < m;++y) { if(field[x].charAt(y) == '*') { if (adj[x][y].size() > 1) { moreDegree.add(new Point(x, y)); } else if(adj[x][y].size() == 0) { zeroDegree++; } } if(field[x].charAt(y) == 'x') { indexOf[x][y] = special.size(); special.add(new Point(x, y)); } } } long zeroDegWays = 1; for(int i = 0;i < zeroDegree;++i) { zeroDegWays = (zeroDegWays * 2) % mod; } int specCnt[] = new int[special.size()]; Arrays.fill(specCnt, 0); int lim = 1<
•  » » 6 months ago, # ^ | ← Rev. 2 →   +39 Consider a test where 20 special cells are arranged diagonally. Then there would be 38 such cells.
•  » » » 6 months ago, # ^ | ← Rev. 2 →   +8 Thanks for pointing out that test case, I haven't thought of it.
 » 6 months ago, # |   0 Hi Everyone, I am certainly missing something very obvious for problem NewBanknote. My idea is, add the new currency to given denomination and sort them. For any given value, I try all the currencies recursively and take minimum out of it. My solution is failing for some values with off by one which I believe tailored for this problem. I am not looking for solution, but a hint that what is wrong with my thinking. A small test case would be great.  int recurVal(map &mp, vector &curr, int val) { if (mp.find(val) != mp.end()) return mp[val]; if (val == 0) return 0; vector ret; for(int i = 0; i < curr.size(); i++) { if (curr[i] > val) continue; div_t divresult = div(val, curr[i]); ret.push_back(divresult.quot + recurVal(mp, curr, divresult.rem)); } mp[val] = *min_element(ret.begin(), ret.end()); return mp[val]; } vector fewestPieces(int newBanknote, vector amountsToPay) { vector curr{1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000, 20000, 50000}; curr.push_back(newBanknote); sort(curr.begin(), curr.end()); int n = curr.size(); map mp; mp.insert(make_pair(0, 0)); for (int i = 0 ; i < n; i++) mp.insert(make_pair(curr[i], 1)); //for(map::iterator it = mp.begin(); it != mp.end(); it++) //cout << it->first << " " <second < ret; for(int i = 0; i < amountsToPay.size(); i++) { ret.push_back(recurVal(mp, curr, amountsToPay[i])); } return ret; } 
•  » » 6 months ago, # ^ |   0 Try newBanknote = 50001, amuontsToPay = 200002.
•  » » » 6 months ago, # ^ |   +5 Thank you very much. Now, I see my mistake. I have another noob question. I assume this problem is related to coin change which is universally assumed to be dynamic programming, but it can be solved greedily if there are some special cases of denomination. I am wondering what kind of relation/structure/constraints/pattern on coin denomination makes it greedy ?
•  » » » » 6 months ago, # ^ |   +5 The set of coins is termed as "canonical" if the greedy algorithm produces optimal solution. There is a paper on verifying if the set of coins is canonical. Link
 » 6 months ago, # |   +27 For a while already, I've wondered about the problem which appeared as Div1 Medium in this round: We are given a sequence. Can it be split into two equal subsequences? In the round, the size was only up to 40, which allowed for multiple exponential solutions. The question is, is it solvable in polynomial time? It certainly is when we know the subsequence to search for. So far, I don't see a polynomial solution, I don't see a reduction of some classic hard problem to this one, and I can't find any sources online which discuss the problem. The problem statement is so short that one would think it had been studied decades ago, with some definite result. I'll be grateful if someone sheds some light on the matter.
•  » » 5 months ago, # ^ | ← Rev. 2 →   +11 Here is a link that I found https://cstheory.stackexchange.com/questions/34/how-hard-is-unshuffling-a-string that says it is NP-hard
•  » » » 5 months ago, # ^ |   +10 Yay, many thanks for the find!Amazing that the answer was found only recently.