Shafaet's blog

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

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!

 
 
 
 
  • Vote: I like it  
  • +65
  • Vote: I do not like it  

»
21 month(s) ago, # |
  Vote: I like it +29 Vote: I do not like it

11

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Shafaet (previous revision, new revision, compare).

»
21 month(s) ago, # |
  Vote: I like it +210 Vote: I do not like it

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    LOL :)

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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, # |
  Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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, # |
  Vote: I like it 0 Vote: I do not like it

Can you enable viewing of others solution?

»
21 month(s) ago, # |
  Vote: I like it +6 Vote: I do not like it

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   Vote: I like it 0 Vote: I do not like it

    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:
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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, # ^ |
          Vote: I like it 0 Vote: I do not like it

        None of the hackerrank tests for this problem contain numbers >=2^26, for 2^26 my code would probably fail.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # |
  Vote: I like it +20 Vote: I do not like it

Test case for the last problem is very bad. Bruteforce solution get > 96 points. :(

»
21 month(s) ago, # |
  Vote: I like it +4 Vote: I do not like it

Can some one explain me the solution of the 4th problem? City Construction?

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    You need this observation to solve the problem City Construction:

    Future addition of nodes cannot change the answer for past queries

    That is, the answer remains the same whether you solve a query the moment it is given or you solve the query after considering all the updates. Let's see why this is true. There are two ways to add a node.

    1. The new node has a directed edge towards an old node. In this case, this new node can never be reachable from any old node no matter what the future updates are. Think for yourself why this is true

    2. The new node has a directed edge coming from an old node towards itself. In this case the new node can never reach any old node no matter what the future updates are. Again think for yourself.

    So now we have established that we can take all the updates at first and add the edges for each update and then process the queries. So now the problem becomes, given a directed graph, answer some queries like if it is possible to reach x from y?

    We can solve this problem using dp if the graph was acyclic i.e DAG. So we divide the graph into strongly connected components and build a new graph with those components which will indeed be a DAG. Now our definition for the dp will be:

    dp[i] = nodes which are reachable from node i

    And our recurrence will be:

    dp[i] = union of node i and all possible dp[j] where j is any node which can be reached from node i using one edge

    So the complexity would be O(N*M) This is because for every edge we have to union two sets each of which can have size as large as N. Think of dp array as an array of boolean arrays and you or two boolean arrays of size N for each edge.

    But instead of using a boolean array, you can use bitsets to optimize the solution to have a time complexity of O( ( N * M ) / log( number of bits in an integer ) which is basically ( ( 5*10^4 * 10^5 ) / 32 ) or simply around ( 1.7 * 10^8 ) operations which can easily pass under the time limit.

    Hope this helps.

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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, # ^ |
          Vote: I like it +5 Vote: I do not like it

        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   Vote: I like it 0 Vote: I do not like it

    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   Vote: I like it +10 Vote: I do not like it

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   Vote: I like it 0 Vote: I do not like it

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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, # ^ |
        Vote: I like it 0 Vote: I do not like it

      At least your solution is not wrong :D

      My 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, # ^ |
          Vote: I like it +8 Vote: I do not like it

        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, # ^ |
            Vote: I like it 0 Vote: I do not like it

          It happens, good luck next time:)

        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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, # |
  Vote: I like it +10 Vote: I do not like it

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, # ^ |
      Vote: I like it +5 Vote: I do not like it

    What is the straightforward way?

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I do! It works under 0.6s in all testcases.

    Code

    By the way, I wonder if this method is actually correct. Can anyone prove its correctness or give a counterexample?

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      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, # ^ |
          Vote: I like it 0 Vote: I do not like it

        We could remove duplicates without any regrets;)

        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
          Rev. 2   Vote: I like it +20 Vote: I do not like it

          Ok, try this one:

                  int M = (1 << 18);
          	vector<int> a;
          	for(int i=1;i<M;++i){
          		if(popcnt(i) <= 7 && i % 2 == 1){
          			a.push_back(i);
          			if(a.size() == 99999) break;
          		}
          	}
          	int c = 0;
          	for(int i=18;i<=25;++i){
          		c ^= (1 << i);
          	}
          	a.push_back(c);
          	printf("%d\n",a.size());
          	for(int i=0;i<a.size();++i) printf("%d ",a[i]);
          

          UPD: It could be even worse. I just post this one because it can be launched on codeforces in custom invocation.

          • »
            »
            »
            »
            »
            »
            21 month(s) ago, # ^ |
              Vote: I like it +15 Vote: I do not like it

            Seems it is a good test. In CF his code works 1800 ms.

    • »
      »
      »
      21 month(s) ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Make a[i] odd for 0<=i<n-1, a[n-1] = 1..10..0. Then (1<<(26-k-1)) odd masks will run through all min(10^5-1, choose(k-1, 26-k-1)) numbers.

»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

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, # |
  Vote: I like it +10 Vote: I do not like it

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, # |
  Vote: I like it +13 Vote: I do not like it

Anyone received the prizes? 3 month is quite long to wait..