Overthought non-recursive 3ms C++ solution


  • 0
    C

    The recursive or tail-recursive solutions, building up the pairs, are more elegant than mine.

    I thought about the patter, and built up the orders of the teams in a linked list starting with just 1 team; then wrote it out to a string with a formula for the correct number of parentheses.
    Every time we double the number of teams to a new binary order of magnitude, we leave the teams that were there in place, and match each with one from the upper half in reverse order (1 to the highest, 2 [wherever it is] to the 2nd highest, etc.) so the sum of each pair in the first-round matches is the same, 1 more than the number of teams.
    Starting with 2 teams, 1 plays 2. Double to 4 teams, 1 plays 4 [sum is 5], and 2 plays 3 [sum is 5], then match the winner of the (1,4) to the winner of (2,3).

    For 8, the pairs are (1,8),(2,7),(3,6),(4,5) but in order that's 1,8,4,5,2,7,3,6.

    The number of parentheses is the log-base-2 of the greatest-power-of-2-divisor of the position in the list.

    I don't know if that English is easier to follow than the code.

    I would have liked to find a formula to drop the teams into their slots (and the number of parentheses after them in a parallel array) without a linked list, but I couldn't find it.

    class Solution {
    protected:
        static const int contestmax = 12; // This is a given in the statement of the problem
        // 1-based Array to hold the linked list, as cursors
        // 0 is the sentinel
        int linkedlist [ 1 << contestmax + 1];
    
        int what_pow_of_2(int n)
        {
            int greatest_pow_2_divisor = 1;
            int logg = 0;
            while (1)
            {
                if (n & greatest_pow_2_divisor)
                    return logg;
                logg++;
                greatest_pow_2_divisor <<= 1;
            }
        }
        
        
        void insert(int val, int after)
        {
            linkedlist[val] = linkedlist[after];
            linkedlist[after] = val;
        }
        
    public:
    
        string findContestMatch(int n)
    	{
    		linkedlist[1] = 0;
            
    		int maxavail = n;
    		int nextavail = 2;
    		int seeded = 1;
            
    		while (seeded < n)
    		{
    			// Each time we double the number of teams to a new binary order of magnitude,
    			// add one of the new teams after each of the existing teams, highest after 1,
    			// next highest after 2, etc.
                
    			int pairtotal = seeded * 2 + 1;
    			int curr = 1;
    			while (curr != 0)
    			{
    				insert((pairtotal - curr), curr);
    				curr = linkedlist[linkedlist[curr]]; // Skip over just-inserted
    			}
    			seeded <<= 1;
    		}
            
            // Now the teams are in the right order
            // Write them to the string with the correct number of parentheses,
            // which is the log-base-2 of the greatest power of 2 that divides
            // the 1-based position, which is zero for odd positions, close parentheses,
            // then a comma, then the same number of open parentheses except 
            // no comma and no open parentheses at the end.
            
    		int curr = 1;
    		string out = "";
    		int pos = 1;
    		int maxlog = what_pow_of_2(n);
    		for (int i = 0; i < maxlog; i++)
    			out += "(";
    		while (curr != 0)
    		{
    			out += to_string(curr); // or use string streams, and itoa of your choice
    			int p = what_pow_of_2(pos);
    			for (int i = 0; i < p; i++)
    				out += ")";
    			if (pos < n)
    			{
    				out += ",";
    				for (int i = 0; i < p; i++)
    					out += "(";
    			}
    			curr = linkedlist[curr];
    			pos++;
    		}
    		return out;
    	}
    };
    

    In an attempt to be even faster I used this routine to pre-generate the strings for between 0 and 128 teams, and return those strings for the corresponding input, but it didn't save measurable time, probably because 256, 1024, 2048, and 4096 took most of the time, and I didn't feel like pasting those strings into the code.

    Is there a conventional word for the the highest power of 2 that divides a number, which is the same as the number which is all the zero bits and the first one bit from the least significant? (And is there a better way to find it?)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.