### decoder123's blog

By decoder123, 6 years ago,

Hi!

Tomorrow at 4:00 MSK will be held Topcoder SRM 696.

Let's discuss problems after contest!

• +64

 » 6 years ago, # |   +26 Are you sure? clist.by says that it will be day later.
•  » » 6 years ago, # ^ | ← Rev. 2 →   +11 EDIT: sorry for the mistake.. I am extremely sorry. I am changing it...Those who actually saw the message I apologize.It is impossible for me to check every timezone and then get a lower bound of time upon crossing which this list is will be true for everyone. This solely serves the purpose of a reminder and also a blog for discussion of the competition problems as the editorial is published quite late over there. As far as I know the time is shown correctly. What else do you guys want?
•  » » » 6 years ago, # ^ |   +12 So I set the alarm for 3:30 AM (the contest starts at 4 AM in my timezone). Turns out I woke up and shut down the alarm and returned to sleep. Then in the morning I was very upset that I missed it. Next thing I find out that the contest is tomorrow. Yay! :D
•  » » » » 6 years ago, # ^ |   +15 hey sorry for that... I will do it more carefully from now on. I have really a lots going on in my life ... well I know that doesn't mean I can put wrong time... I apologize to everyone.
•  » » » » » 6 years ago, # ^ |   +27 Calm down, you're overreacting. Just because people downvote a post you make doesn't mean they hate you. And I'm pretty sure tweety's post was made to cheer you up because things worked out in the end.
•  » » » » » » 6 years ago, # ^ |   -20 ليش صورتك من الذب ؟
•  » » » » » 6 years ago, # ^ |   +13 ^ He's right, of course
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 Yeah it is a day later. See here. Click on 'Click here to see when coding begins in other time zones.'
•  » » 6 years ago, # ^ |   0 قوم نيك
 » 6 years ago, # |   0 1.5 hours before the contest starts. Go register.
•  » » 6 years ago, # ^ |   0 People are too lazy. Looks like one of the lowest participation recently :(
 » 6 years ago, # |   +1 Starts in 10 minutes :)
 » 6 years ago, # |   0 what is the solution logic of div2(c)?
•  » » 6 years ago, # ^ | ← Rev. 3 →   0 Use breadth first search and bit mask. Use a map to index each undecided edge to a number from 0 to k - 1. Consider all possible subsets of nodes [pow(2, 20) of them] and see if each of them forms a clique taking into consideration both the decided and undecided edges. If a certain subset does indeed form a clique push it into a vector of pairs, the pair being the size of the clique and an integer whose ith bit is set to 1 if the ith index corresponds to an undecided edge found in the clique. Sort this vector and then iterate through it from biggest to smallest clique size. Run bfs on each secondary value — the one that contains information about what the undecided edges needed to form it are, if it has not been visited. For each clique you know that forming it could also include other undecided edges unrelated to it. So iterate through i from 0 to k and OR the current integer with (1 << i). Therefore insert these values into the bfs queue if they haven't been visited by a larger clique size previously. Every time you visit a value in the current BFS you would add the size of the current clique to the total. Each subset of undecided edges gets visited once, so time complexity is pow(2, k) * k.
 » 6 years ago, # | ← Rev. 4 →   0 In Div2 500, what will be the answer for3 5 73 5 72 3AC code are giving 1 but according to me it should be 2?EDIT --> Answer is 1 but this code passes system test but fails on above testcase
•  » » 6 years ago, # ^ |   0 1 is the right answer. What happens is 3 is stickied on A[0] i.e on 3. So only 2 causes a conflict . Hence ans = 1 conflict
 » 6 years ago, # |   0 This is a new low for lack of discussion about the contest :( Maybe it is because all the Russians were asleep for the contest?
 » 6 years ago, # |   +53 I hate to complain, but what is the point of samples? I know topcoder is notorious for its weak samples, but the samples on the div1 500 seemed especially weak. For the div1 500, I failed because I compared against 0 rather than '0'. None of the samples had a '0' that wasn't on the diagonal, and any such sample would have caught this mistake. I think this is an example of particularly weak samples because it explicitly doesn't cover one case of the problem (i.e. the case when an edge is not present). I thought samples should just be a quick sanity check on correctness, and should generally catch mistakes like this.This is more of an open question, but what should be the general philosophy behind constructing sample cases?
•  » » » 6 years ago, # ^ |   0 We can find on TC website that in this round: Small one's Success rate is 37.12%, Medium is 24.14%, Large is 0%. Is it truly intended? Personally, I think keep success rate in a reasonable range seems reasonable. Spend lots of effort and have ~ 70% chance to get 0 point just doesn't seem that cool.
•  » » » » 6 years ago, # ^ |   +10 You have to wonder how many of those Easy submissions are actually solutions to the problem, and not just desperately submitting any algorithm that passes samples hoping that it's correct (I'm not blaming anyone; that's what I do when I can't solve a problem, too!). If you coded the correct algorithm it was really hard to get it wrong and all samples right.Medium's success rate is indeed a tad smaller than I would expect, though.
 » 6 years ago, # |   0 div 2 500 solution anyone ?
 » 6 years ago, # |   +11 How to solve Div.1 550? After the contest I googled and submitted 2k bruteforces (it even works for 1.9 s), but I certainly do not think that it was an expected solution.
•  » » 6 years ago, # ^ | ← Rev. 3 →   +28 I completely don't understand the difficulty of this task. It looks like "Hey, bruteforce 2^10 assignments of '?' to '0'/'1' and find maximal clique in graph with 38 vertices as you want". Even if we forget that most difficult part of this problem (finding clique) can be copypasted from... anywhere, coding from scratch clique finding doesn't worth 550 pts.I get AC with simple bruteforce: let's find anticlique. Take vertice with maximal degree, and take it to anticlique (and not take all it's neighbours), or don't take it to anticlique. If there are only vertices with degree <= 2, it is set of paths and cycles and we can calculate answer in linear time. Complexity -- T(n) <= T(n-1) + T(n-4) <= 1.38n (multiplied by 210), which passes easily. Also, there are very weak tests, I had to resubmit because I find stupid bug, but even my first bugged solution get AC.
•  » » 6 years ago, # ^ | ← Rev. 2 →   +52 You can do it in O(2n / 2n) using meet-in-the-middle.- Split vertices in two equal (almost equal) parts in such way that all ?-edges goes in the first part.- For each subset of the second part find largest clique, contained in this subset. This can be done in O(2ss), where s is the size of the part. Probably even O(2ss2) would pass.- For each subset of the first part that contains only ?-edges and 1-edges, we can find largest clique in the second part connected to this.- So, we will have bunch of implications of the form "if subset S of ?-edges is taken, largest clique is at least x"- Using this, we can find in O(2ss) (or O(3s)) for each subset of ?-edges size of larges clique.- Sum up this. code#include using namespace std; const int M = 21; vector g; int n; int da[1 << M], db[1 << M]; int cont[1 << M]; int sub[1 << M]; int in(int mask, int k) { return (mask >> k) & 1; } void calc(vector a, int *d) { int m = a.size(); auto conn = [&](int x, int y) -> bool { return g[a[x]][a[y]] != '0'; }; vector f(m); for (int i = 0; i < m; ++i) for (int j = 0; j < m; ++j) if (conn(i, j)) f[i] |= 1 << j; d[0] = 1; for (int mask = 0; mask < (1 << m); ++mask) { int pos = (1 << m) - 1; for (int k = 0; k < m; ++k) if (in(mask, k)) pos &= f[k]; for (int to = 0; to < m; ++to) if (in(pos, to)) { int nxt = mask | (1 << to); d[nxt] |= d[mask]; } } } void conv(int n, int *d) { for (int i = 0; i < n; ++i) for (int mask = 0; mask < (1 << n); ++mask) if (in(mask, i)) d[mask] = max(d[mask], d[mask ^ (1 << i)]); } class Clicounting { public: int count(vector G) { g = G; n = g.size(); set A, B; for (int i = 0; i < n; ++i) B.insert(i); auto move = [&](int x) -> void { A.insert(x); B.erase(x); }; for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) if (g[i][j] == '?') { move(i); move(j); } for (int i = 0; i < n; ++i) if (A.size() < n / 2) move(i); vector a(A.begin(), A.end()), b(B.begin(), B.end()); int as = a.size(); int bs = b.size(); calc(a, da); calc(b, db); for (int mask = 0; mask < (1 << bs); ++mask) if (db[mask]) db[mask] = __builtin_popcount(mask); conv(bs, db); int q = 0; for (int i = 0; i < as; ++i) for (int j = i + 1; j < as; ++j) if (g[a[i]][a[j]] == '?') { cont[(1 << i) | (1 << j)] |= 1 << q; ++q; } for (int i = 0; i < as; ++i) for (int mask = 0; mask < (1 << as); ++mask) if (in(mask, i)) cont[mask] |= cont[mask ^ (1 << i)]; vector f(as); for (int i = 0; i < as; ++i) for (int j = 0; j < bs; ++j) if (g[a[i]][b[j]] == '1') f[i] |= 1 << j; for (int mask = 0; mask < (1 << as); ++mask) if (da[mask]) { int to = (1 << bs) - 1; for (int k = 0; k < as; ++k) if (in(mask, k)) to &= f[k]; int cur = cont[mask]; int sz = __builtin_popcount(mask) + db[to]; sub[cur] = max(sub[cur], sz); } conv(q, sub); int ans = 0; for (int mask = 0; mask < (1 << q); ++mask) ans += sub[mask]; return ans; } }; P.S. I think it is a nice task. Sad that brute-force solution passed. Probably author didn't want to cause TL problems for intended solutions.
•  » » » 6 years ago, # ^ |   0 I agree it's a nice solution, but it's a questionable task because bruteforce has almost the same complexity, and I'm sure they wouldn't have used it if they had realized this.It's not the first time this happens, for example most problems with n sqrt n log n solutions turn out to be unusable tasks because the n^2 bruteforce is almost always faster.
•  » » » » 6 years ago, # ^ |   0 لاتتفصحن
•  » » » » 6 years ago, # ^ |   0 Really? What's complexity of bruteforce?I think, in this case the problem doesn't fit for topcoder format. Like, huge multitest allow to separate solutions more accurately. Also one can change the statement and give more ?-edges.
•  » » » » » 6 years ago, # ^ |   +10 But number of ?-edges needs to be at most n/4 for that solution to work.
•  » » » » » » 6 years ago, # ^ |   0 Yeah, I know. I mean, came up with something like "all ?-edges will form a tree". Rather awkward, but bettern than brute-force passed.
•  » » » » » 6 years ago, # ^ |   +10 The worst case of Bron-Kerbosch is , but you can optimize it to something like , getting a 20.58n algo, very close to the intended solution.This isn't even the best complexity known for maximum clique, as wikipedia mentions one with 20.25n conplexity, and this is assuming all algorithms perform at the worst case in all runs, which unless a very specific case can be constructed means all versions are faster in practice, even vanilla Bron-Kerbosch.
 » 6 years ago, # | ← Rev. 2 →   +11 How to solve div1 300?
•  » » 6 years ago, # ^ |   +31 Simulate the process backwards int countfee(vector x, vector y) { int m = SZ(x); vector dp(1 << m, 1e9); VI masks(50); REP (i, m) { masks[x[i]] |= (1 << i); masks[y[i]] |= (1 << i); } dp.back() = 0; FORD (mask, (1 << m) - 1, 1) { REP (v, 50) { mini(dp[mask & (~masks[v])], dp[mask] + __builtin_popcount(mask)); } } return dp[0]; } 
•  » » 6 years ago, # ^ |   +21 Here is another simple solution (by the writer subscriber): import java.util.Arrays; public class Gperm { public int countfee(int[] x, int[] y) { int result = Integer.MAX_VALUE; int n = x.length; int v = 50; for (int m = 0; m < (1 << n); ++m) { int[] deg = new int[v]; for (int i = 0; i < n; ++i) if ((m & (1 << i)) > 0) deg[x[i]]++; else deg[y[i]]++; Arrays.sort(deg); int cur = 0; for (int i = 0; i < v; ++i) cur += (v - i) * deg[i]; result = Math.min(result, cur); } return result; } } 
 » 6 years ago, # |   +17 Lol, was there a rejudge of that contest? I submitted easy and hard, but my hard failed systests, so I ended up at 29th position. I searched for a bug in my hard for some time after contest, but couldn't find it. Now I entered that SRM stats and it shows me that my hard passed system tests and I ended up at 2nd position being the only one to solve hard o0 (there were 2 submissions).
•  » » 6 years ago, # ^ |   +17 Yes, we rejudged all solution to Div1-Hard and you passed system test. Congratulation! Somehow the reference output was wrong (it was generated by an old solution).
•  » » 6 years ago, # ^ |   0 Btw, how to solve hard?
•  » » » 6 years ago, # ^ |   0 Bruteforcish dynamic programming. What information do we need from a subtree? Important information for us is whether we can obtain a prefix of our substring of length k if we go form some descendant up to root of subtree and whether we can obtain suffix of length k if we go from root to some descendant. For every mask of 2s bits (where s is length of our string) keep count how many subtrees correspond to that state. And then combine them (note how important here is assumption that our string doesn't have two consecutive equal letters). We should not keep states with count 0, which reduces number of states from 4s to 3s (I used unordered_map). We can combine states in bruteforce way which will result in (3c)s complexity which c is some weird constant with square roots between 2 and 3 resulting from unraveling recurrence, but it can be sped up to 22s if we use fast subset convolution (more precisely we need cover product). To combine substrees I used bruteforce way and was a little afraid of fitting into TL, but it seems it was enough.
 » 6 years ago, # |   0 May anyone tell the idea of the Div.2 500 problem?