By riadwaw, history, 5 years ago,

Today, at 6 PM MSK (3 PM UTC)

• +11

 » 5 years ago, # |   +56 I'm having problems with registration (It says that registration is by invitation only despite the fact I have automatically advanced to the Round 2). Any ideas how to fix this?
•  » » 5 years ago, # ^ |   +38 I think admins just forgot to add byes to advancers pool
•  » » 5 years ago, # ^ | ← Rev. 2 →   -32 how bad!!!
•  » » 5 years ago, # ^ |   +8 Same here.
 » 5 years ago, # |   +21 Hey where has cgy4ever gone?
 » 5 years ago, # | ← Rev. 2 →   -81 Damn , my classmate wrote that stupidness :D idk wht's going on there so sry .
 » 5 years ago, # |   +10 I'll be correcting the issue with those who have byes. Those compeittors will be automatically registered for this round. — said TopCoder
 » 5 years ago, # |   0 We just fixed it: "All competitors with a bye have been automatically registered, our apologies for the trouble. For everyone else competing today, be sure you register at least fifteen minutes before the match begins, thanks!"
 » 5 years ago, # |   0 WEB ARENA IS DAMN TOO SLOW -_-
 » 5 years ago, # |   +13 I can't login now. I could several hours ago.
 » 5 years ago, # |   0 Sorry, you cannot perform this operation because you are not assigned to this room. The likely cause is that you did not successfuly register for the match during the registration period.But I am registered...
 » 5 years ago, # |   +5 Surprisingly my randomized solution for A passed.I shuffled the array 1000 times and check if if possible to fix the first element and apply GCD or LCM using DP.Unfortunately it was not enough to advance, my browser got frozen while testing sample cases.I would like to know a deterministic solution.
 » 5 years ago, # |   0 Ugh. I failed 500 on slightly exceeding the memory limit (so slightly that changing long long to int in 4 places would've fixed it).
 » 5 years ago, # |   0 How to solve the first question?
 » 5 years ago, # |   +15 Unfortunately most of passing 500's solutions were ugly (including mine).Admins said the intended solution was meed-in-the-middle, but I just googled how to count the number of cliques (http://cs.stackexchange.com/questions/9209/finding-all-cliques-of-a-graph).
•  » » 5 years ago, # ^ |   +5 tourist's solution looks good
 » 5 years ago, # | ← Rev. 2 →   0 Why this code is TL on topcoder? 400pthttp://pastebin.com/1wxnCQhM
 » 5 years ago, # |   0 Would have pulled of successful last second submission. Did not change min->max in two lines during last sec updates. Two things 1. The excitement of a successful last sec submission would have been great. 2. Generally frustrated for missing because of typing miss!
 » 5 years ago, # |   +25 My solution on 500 passes if fix stupid bug in 134ms. Solution is following. We can count sum for each edge independently. For one edge answer is equal to ({Number of cliques with a} + {Number of cliques with b} + 1 — {Number of cliques total}). So the solution is to find number of cliques in graph except each vertex. It's well known, that dp on subsets, works in time 2n / 2 if don't count same mask twice, and choose to get or not to get smallest vertex each time. If use same cache, it's works even faster, than n*2^{n/2} (i think even in 2^{n/2} time, but I can prove, only n/2*2^{n} visited states).
•  » » 5 years ago, # ^ |   +10 Would you mind elaborating that DP which counts cliques a little?
•  » » » 5 years ago, # ^ |   +15 dp[S] = count of cliques, which are subset of SLet's v be vertex in S., where N(v) is set of neighbors.If always get as v vertex with minimal id, there is O(2n / 2) states reachable. If v is less than n / 2, there are less than 2n / 2 branches, if v is more, there are less than 2n / 2 states total. Order of vertices is imortant. For example, choose random vertex each time is bad (but choose random order one time is ok, of course).
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   0 I did it in other way. Divide vertices on two equal parts. For first part precalculate for every subset A is it clique or not, and if it is clique calculate mask of vertices in second part which is connected with all vertices in A (both could be done by & incident masks of vertices in A). For second part calculate for every subset is it clique. Then calculate convolution of this array. For each query S, we look for subsets A of S in first part and if A-clique add number of subsets in second part which is clique and incident to A.
 » 5 years ago, # |   +57
•  » » 5 years ago, # ^ |   -8 the same problem, but i have zero execution time on little test
•  » » » 5 years ago, # ^ |   +10 According to the following, system calls like clock() are not accounted for the reported "Execution time", but are accounted for the timeout, and for some reason the call to clock() is slow on TopCoder: http://apps.topcoder.com/forums/?module=Thread&threadID=507280&start=0&mc=9#511776
•  » » » » 5 years ago, # ^ |   0 thanks for link!
 » 5 years ago, # |   +23 Solve the first problem correctly, fast enough to be in top40. Think that you aren't in top40 because you are ~80-th right now. Blindly challenge a few participants. You are no longer in top40. ??? Profit.
•  » » 5 years ago, # ^ |   +8 Same story here :(
•  » » 5 years ago, # ^ |   +31 Submit a solution for 400 you think is incorrect, just so you submit something. Close topcoder arena after 1 hour of "not solving anything", seeing your rank is too low even if your 400 miraculously passed. Read this comment and see that just 400 was enough. Open arena 10 hours after round end and realize you qualified. WTF, how did this happen
 » 5 years ago, # |   0 I think problem 400 was nice for people who like ifs a lot. I'm not sure I like ifs quite so much :(
•  » » 5 years ago, # ^ |   +5 You can also solve the 400 by checking if any pair or triplet of numbers can reach the target (also handling the case where n=1 correctly).
•  » » 5 years ago, # ^ | ← Rev. 2 →   +6 I solved it by bfs on reachable states. Every number 2i3j is a pair i, j. There 9 different types of pairs (first and second coordinate could be <,=,> then in t). It could be proven that every type of pair could be useful not more than twice. Then I made search on this 39 states.
•  » » » 5 years ago, # ^ |   0 I had the same approach. How to prove it?
•  » » » » 5 years ago, # ^ |   0 Consider about 10 cases =) I haven't done it during round, and for sure submited 4^9 states solution.