### Shafaet's blog

By Shafaet, history, 21 month(s) ago, ,

Hello Codeforces Community, I am glad to share HackerRank World Codesprint 11 starting on 26th May 2017. The contest duration is 24 * 2 =48 hours.

The winners of the contest will win up to 2000USD cash prizes. Also, there are opportunities to win T-shirts and Amazon Gift cards.

The contest will be rated. If two person gets the same score, the person who reached the score first will be ranked higher. There will be 7 algorithmic challenges in the contest including an approximate challenge.

The problems are prepared by svanidz1, tunyash, cmaster, muratt and Shafaet. Thanks to wild_hamster for testing the challenges and finalizing everything.

Update: Contest is starting in 10 minutes.

Update: The contest ended, congrats to the winners.

Happy Coding!

•
• +65
•

 » 21 month(s) ago, # |   +29 11
•  » » 21 month(s) ago, # ^ |   0 Thanks :D.
 » 21 month(s) ago, # |   0 Auto comment: topic has been updated by Shafaet (previous revision, new revision, compare).
 » 21 month(s) ago, # |   +210
•  » » 21 month(s) ago, # ^ |   +10 LOL :)
•  » » 21 month(s) ago, # ^ |   +5 At least in the 100 point problem, We don't need to use a 32 bit number to represent 32 numbers.
 » 21 month(s) ago, # |   0 Approaches for the approximate problem? I used backtrack to solve the smallest tests optimally and greedy for the remaining tests — pick an order of the pieces and try to place them in a shaft of fixed width (either trying all possible widths or at least divisors of the optimum size) in that order either by trying various Tetris-style drops, all possible positions (only smaller tests) or making the leftmost bottom cell of the given piece coincide with the leftmost bottom free cell. It was pretty slow, so it scored about 2/3 points for the largest tests and over 0.8 for the rest.
•  » » 21 month(s) ago, # ^ |   0 I came up with a solution that I wasn't able to finish during the contest that recreates the original rectangle.The idea is to take a figure of cells and produce a list of connected line segments that form the outline of the figure. There may be multiple sets of line segments if the figure has holes.We can convert a path of line segments into a string of L, R, U (left, right, up/straight). A single cell square would be R,R,R,R which means start at a point in the path that forms the outline, go one unit, then make a right, ... repeat 3 more times. A square with twice the side would look like this RURURURU. An opening a figure that could hold the one cell square would look like LLLL and for the four cell square (2x2) it would look like RURURURU or URURURU depending on the point chosen. If there are multiple disconnected paths we append one string after the other with a / inserted in between. For example, a square with 3 units sides and a hole in the middle would look like this RUURUURUURUU/LLLL.We do this for every figure converting their shape into a string. Each string represents the contour of the shape. We will use this to match the contour of each figure against each other to see which ones naturally fit with other. This also allows us to fit holes inside figures perfectly.Then we can perform fast longest common substring matches with a suffix automaton in O(n) time. We create a suffix automaton for each string. Then for every shape we want to match against it, we run that shape's string against the suffix automaton. We actually run the string repeat twice to handle wraparound. Also, we run the string in reverse (twice repeated) to handle paths traversed in the reverse order. The resulting value capped by the length of string passed gives us the length of the longest match.Note when matching we match U's with U's and L's with R's. R's are produced for a turn when the first segment and second segment belong to the same cell. L's are produced otherwise. A segment only belongs to one cell, because a boundary separates a cell inside from the empty space outside.
•  » » » 21 month(s) ago, # ^ |   0 I believe that this approach would have achieved a perfect score in most cases. The main problem would be cases where there are ambiguities. The method of test case generation pretty much guarantees that we would get a lot of odd shapes that provide unique contours for fitting two figures.
 » 21 month(s) ago, # |   0 Can you enable viewing of others solution?
 » 21 month(s) ago, # |   +6 Can someone share his approaches for the problem "The Best Mask" ? I went through the editorial and could not understand it.
•  » » 21 month(s) ago, # ^ | ← Rev. 3 →   0 I went with recursion in index of a bit, starting with the lowest one. That is rather slow in the worst case, but one can cut off some of the recursion branches that are not promising. Every time we try to set a bit to 0, the set of the numbers that need to be matched with the mask stays the same, and if we set a bit to 1, all the numbers that have that bit set are taken care of, so on average, the set is cut in half.This is probably not much worse on average than the intended solution, but I am not so sure about possible hacks. I managed to get it to pass the test cases in barely under 1s. Code:#include using namespace std; int n; vector a; int bestres = 1000000000; int bestbits = 30; int curnum=0; void f(int b, int bits, vector & s){ if(bits>bestbits || b==26)return; if(s[0]>=(1<<(b+1)) ){ // set bit b to 0 if(curnum &(1< s2(0);s2.reserve(s.size()); //s2.clear(); s2.resize(0); for(int i=0; i>n; a.clear(); a.resize(n); for(int i=0; i>a[i]; } sort(a.begin(), a.end()); f(0, 0, a); cout<
•  » » » 21 month(s) ago, # ^ |   0 try this one: 1 67108864 Just curious will this line gets RE at some test or not: assert(a[i] < (1 << 26)); 
•  » » » » 21 month(s) ago, # ^ |   0 None of the hackerrank tests for this problem contain numbers >=2^26, for 2^26 my code would probably fail.
•  » » 21 month(s) ago, # ^ |   0 My solution looked for the element in the set with the lowest bit count... If there are more than one, choose the smallest integer.If the bitcount is one, then we know that the bit needs to be set in the resulting integer.We are guaranteed that one of those bits will be used, so we dfs with the lowest bit first. After dfs, we get integer candidate, we save it as our current best. Also, we pass an exclude mask to eliminate the bit from being considered in future searches. Because we started with the lowest bit first, our integer is likely to be smaller than any future candidate and we can curb searches that will try a bit higher that our candidate.This approach eliminates redundancy and prunes quickly by considering likely bits and tends to produce small initial candidates that can curtail future searches that will generate higher candidates.
 » 21 month(s) ago, # |   +20 Test case for the last problem is very bad. Bruteforce solution get > 96 points. :(
 » 21 month(s) ago, # |   +4 Can some one explain me the solution of the 4th problem? City Construction?
 » 21 month(s) ago, # |   0 I had used DFS for the problem city construction. None of the test cases passed. Then after optimizing my dfs so that it won't check for other nodes once its found this particular one stupid me thought that i'll pass some/possibly all cases. Still none passes :/.Anyone with a similar logic who's passed the cases? I'd love some hints. Or has everyone thought of the way it's coded in the editorial?
•  » » 21 month(s) ago, # ^ |   0 Did you run dfs on each query? This is O(n*q) and I don't think it can be optimized with bitsets in any way. The solution in editorial works fast only because of bitsets. It's something like O(n^2 / (bitset_constant)).
•  » » » 21 month(s) ago, # ^ |   0 Nah, mate:)We're using bitsets ONLY because of constraints of memory. Bitset is obviously slower than vector/array.The solution in editorial is fast enough because of SCC (and non-complete tests).
•  » » » » 21 month(s) ago, # ^ |   0 I was talking more of the idea of bitsets than of the c++/java structure implementation. I believe that compressing bits using ints can be faster with vectors.Isn't there still up to 5·104 SCCs? Like are there any tests where author solution may perform for too long?
•  » » » » 21 month(s) ago, # ^ |   +5 No, bitset OR is fast, so you can use dag topsort order to compute reachability by performing OR on children's reachable vertices. It is not only to save memory but also time.
•  » » 21 month(s) ago, # ^ | ← Rev. 2 →   0 I didn't use bitsets and I passed. First, I created the whole graph including late additions. Second, I did union find to identify disconnected subgraphs in the undirected graph sense. If 2 cities are in disconnected subgraphs, immediately fail. Third, I did Tarjan SCC to identify strongly connected components. If 2 cities are in same SCC, immediately succeed.All cities are replaced by a representative from their SCC to reduce the graph. Then I created a new DAG from the rep. I did dfs against the two reps for each query.I didn't use bitsets.
 » 21 month(s) ago, # | ← Rev. 5 →   +10 Really weak testcases which makes me sad:(In problem 'The Best Mask' (75 pts) I have AC with optimized N·226.In problem 'Road Trip' (100 pts) I have 97 out of 100 with sorting queries and stupid n2 approach (I handle all queries with equal xi for linear time).
•  » » 21 month(s) ago, # ^ | ← Rev. 10 →   0 I did the same as you. Additionally, I got a full score D 'City Construction' just by doing the following: Group each node based on its SCC For each SCC, run a DFS. If i-th component can visit j-th component, store that information in Map/Set. This solution is supposed to be quadratic in time and memory, yet passed all cases.
•  » » » 21 month(s) ago, # ^ |   0 Now the funniest part of this. Quadratic approach in D is exactly what's in editorial (ofc with SCC but still quadratic).
•  » » » 21 month(s) ago, # ^ |   0 At least your solution is not wrong :DMy friend (or maybe, I don't know the word for this, let's call him my senpai :v) did it like this: Group every node based on its SCC. Run a DFS, number all component like in Euler tour for tree. Use that numbering to check reachability (like in a tree). This, is completely wrong if the original graph doesn't form a SCC. Yet he got AC.
•  » » » » 21 month(s) ago, # ^ |   +8 My apologies. I tried my best to generate good tests, but it wasn't enough according to this comment. I am sorry, if this made you sad.BTW, it was my first problem in hackerrank
•  » » » » » 21 month(s) ago, # ^ |   0 It happens, good luck next time:)
•  » » » » » 21 month(s) ago, # ^ |   0 I'm not sad though :v Don't worry about that.It is a really nice problem. Good luck next time :)BTW, it'd be nice if you would add some more explanation in the editorial, like why the queries order doesn't affect the answer and how to speed up the solution using bitset.
•  » » 21 month(s) ago, # ^ |   +5 I am really sorry for that. I tried to hack "Best Mask" with brute force and some greedy, but managed to get at most 75% points with tons of optimizations. I can give a code a bit later, because hackerrank is not available now.As for "Road Trip" I didn't try to submit any solution, because I couldn't find normal solution even assuming, that tests are random. Seems like there are many queries with equal xi in the testset :(
•  » » » 21 month(s) ago, # ^ |   0 That's the reason of my sadness being on the opposite side... I'm relatively at the top of the leaderboard not because of my solving skills but because I assumed there could be weak tests -_-
•  » » 21 month(s) ago, # ^ |   +10 Usually last task on Codesprint (especially on data structures) has binary scoring system. I wonder why didn't they do it this time.
•  » » » 21 month(s) ago, # ^ |   0 Last time they did and I wondered why they did it :'( . I am not against strong cases, but I do not like binary scoring, so many equal scores last time.
•  » » 21 month(s) ago, # ^ |   +10 In city construction , I did meet in middle bfs. Started bfs from one node amd another bfs from other node but in reverse direction(maintaining reverse graph). If both bfs meet in middle then path exist else not. PAssed all test in jAVA
 » 21 month(s) ago, # |   +10 Let me share solution on problem E.Let's sort all possible 226 masks and all ai by its popcnt(num of ones). After that we gonna use binary search of popcnt.For fixed p = popcnt we check every mask in the straightforward way (remember we have sorted ai?).Also we even could optimize and check only those ai with popcnt(ai) < 27 - p (because of Dirichlet principle).Any similar solutions?:)
•  » » 21 month(s) ago, # ^ |   +5 What is the straightforward way?
•  » » » 21 month(s) ago, # ^ |   +5 just check if current mask suits every ai. We stop checking current mask if we meet such ai that ai&mask = 0. Because of sorting order (by popcnt) we wouldn't perform too much operations.
•  » » 21 month(s) ago, # ^ |   0 I do! It works under 0.6s in all testcases. Code#include using namespace std; bool cmp(int a, int b) { return __builtin_popcount(a) < __builtin_popcount(b); } int main() { ios::sync_with_stdio(false); int n, a[100005] = {}, z1 = 30, z2 = 100000000; cin >> n; for (int i = 0; i < n; i++) cin >> a[i]; sort(a, a + n, cmp); for (int i = 1; i < 67108864; i++) { bool y = 0; int x = __builtin_popcount(i); if (x >= z1) continue; for (int j = 0; j < n; j++) if (!(a[j] & i)) {y = 1; break;} if (!y) { z1 = x; z2 = i; } } cout << z2; } By the way, I wonder if this method is actually correct. Can anyone prove its correctness or give a counterexample?
•  » » » 21 month(s) ago, # ^ |   0 int n = 100 * 1000; for(int i=1; i<=n - 50; ++i) cout << 3; for(int i=2; i<=26; ++i) cout << (1 << i); try this one
•  » » » » 21 month(s) ago, # ^ |   0 We could remove duplicates without any regrets;)
•  » » » » » 21 month(s) ago, # ^ | ← Rev. 2 →   +20 Ok, try this one:  int M = (1 << 18); vector a; for(int i=1;i
•  » » » » » » 21 month(s) ago, # ^ |   +15 Seems it is a good test. In CF his code works 1800 ms.
•  » » » 21 month(s) ago, # ^ | ← Rev. 2 →   0 I think the worst case might be: all a[i] have the same popcount k; the last a[n-1] is 1..10..0, and the rest of them will have ones in the last 26-k bits. So, all masks under (1<<(26-k)) will fail for the last a[i].Runtime will be at least ((1<<(26-k))-1)*N, where N is the expected number of comparisons before failure for each mask<(1<<(26-k) ). If this will run in time for all k between 5 and 13, I think the solution is good.
•  » » » » 21 month(s) ago, # ^ |   0 Make a[i] odd for 0<=i
 » 21 month(s) ago, # |   +3 In problem "The Best Mask", i was trying an approach similar to a problem (let's call it Rooks in a Chessboad) that ask to put the max number of non-attacking rooks in a chessboard with prohibited cells, that uses bipartite matching between rows and columns (it's a well konw problem in bpm). The things is I could't find such solution in the end, so it's possible to solve this problem using this approach ??? anybody has a similar solution and can explain it. Greetings
 » 21 month(s) ago, # |   +10 Did anyone understand the editorial solution of THE best mask ?? https://www.hackerrank.com/contests/world-codesprint-11/challenges/best-mask/editorial
 » 18 months ago, # |   +13 Anyone received the prizes? 3 month is quite long to wait..