Thoughts after SRM 508

It was a good match overall but I made a couple of mistakes that really penalized my score.

Div1 500 - YetAnotherORProblem
(Link to problem statement)

The sum must be equal to the binary OR between all the elements of the sequence. That is another way to say that at no moment should there be carry operations when adding the numbers together (in binary). As long as there are no carries, then the sum and the binary OR will be equal.

So, the trick is that for each bit number i, there are never two or more 1 bits in the i-th bit of any of the numbers in the sequence.

At first I thought of an idea for a dp solution: Keep a set of bit numbers that already contain a one, then go through each of the position in the sequence, pick a combination of ones and zeros for that position such that:
- The combination of ones and zeros is <= R.
- If the i-th bit is in the set of bits that already have a 1, then the i-th bit of the combination of ones and zeros must be 0. Else it can be any of them.

Then I noticed that the constraints (1 <= 10¹⁸) allowed very large numbers of at most 60 bits. 60 bits means that there are 2⁶⁰ different ses, and that is a lot.

After some minutes I eventually ended up noticing that all the constraints are rather large. Except the constraint for the number of elements in R, which can be at most 10. Always pay attention to the constraints and consider which one is suspiciously small. This constraint means that although the solution is not supposed to be exponential on the number of bits in the numbers in the input, it should be able to make it exponential on the number of elements in the R array.

So, the dp idea is basically the same, but in reverse. Instead of considering the numbers one by one. Consider the bits one by one. Start with the left-most bit. Keep a set of which of the N numbers are currently less than its respective value of R[i] (Once one of the left most bits is smaller, you can begin using any bit 0 or 1, but until then, in case the corresponding bit in R[i] is 0, you would need to use a 0 in that location. Since we are visiting the number of bits from 60 to 0, in each bit we are assigning something for the numbers of the sequence.

An obvious choice is to pick 0 for the i-th bit of every number in the sequence, this will alter our memory of which numbers in the sequence are already smaller. The other option is that exactly one of the elements in the sequence will have a 1 in the i-th bit. It also modifies the state of the set.

So we can have a recurrence that is not cyclic as it keeps decreasing the bit number. All we need is dp tho finish it. During the match, I initially had issues debugging. Besides of the typical mistakes when typing, I also made the mistake of using 1000000007 as modulo instead of 1000000009. Always pay attention to those small details.

struct YetAnotherORProblem
{
    long long mem[1<<10][63];

    vector<long long> R;
    int n;
    long long rec(int mask, int bits) {
        long long & res = mem[mask][bits];
        if ( res == -1) {
            res = 0;
            
            if (bits==0) {
                // No more bits left, we can assume that
                // the previous bits follow the property though.
                res = 1;
            } else {
                int p = bits-1;
                //Assign bits for the p-th position:
                
                //all zero.
                int zmask = mask;
                
                // When leaving zero bits in all the numbers, it is possible that
                // some of them in which the number in the sequence was still not
                // less than seq[i]. Update the mask accordingly. 
                for (int i=0; i<n; i++) {
                    if ( !(mask&(1<<i)) && (R[i]&(1ll<<p)) ) {
                        zmask += (1<<i);
                    }
                }
                res = rec(zmask, bits-1);
                
                //exactly one is 1:
                for (int o=0; o<n; o++) {
                    int nmask = zmask;
                    if ( !(mask&(1<<o)) ) {
                        if (R[o]&(1ll<<p)) {
                            //We are basing the mask on the all 0 case
                            // but if the o-th number has 1 in this case
                            // then the mask should not change.
                            nmask -= (1<<o);
                        } else {
                            //The number must be <= R[i]
                            continue;
                        }
                    }
                    res += rec(nmask, bits-1);

                }
                res %= 1000000009;
            }
        }
        return res;
    }
    
    int countSequences(vector<long long> R)
    {
        n = R.size();
        this->R = R;
        memset(mem,-1,sizeof(mem));
        return (int)rec(0, 62);
    }
};

Div1 250 - DivideAndShift
Link to problem statement

By the time I finished coding the 500-pointer, I was 15-th in the division and first in my room. It seemed many people were taking long to solve the 250. I knew that as long as I got around 220+ points in it, I would be fine.

I open the 250 and ... it seemed hard. But not for long. The main point I think is to notice that it is never necessary to perform shift operations before the division operations. For example, assume that you would do a shift before issuing a division that will turn a list of 10 numbers into 5 groups of 2 numbers. If M=1, a single shift right, will convert M to 2, and after doing the division, it will be the same as if you first did the division and THEN shifted right.

It is harder to see if M=1 and the shift is to the left. In this case, M would become 10. It seems like it modifies things, but in fact, it just changes the group you will keep, but after dividing and keeping the last group, M will become 2, which is the same as if you did the shift AFTER dividing the groups.

So, just try all possible ways to divide the number and then calculate the number of shifts required. The total cost would be the number of divisions plus the minimum number of shifts required. The minimum number of shifts is easy to get. If the groups contain X elements, then M%X will describe the position relative to the group in which M is placed. Everything becomes easier if you first decrement M and assume that positions are 0-based.

To do the divisions, note that after performing enough divisions of many prime numbers, the number of groups can be any divisor of N. So, you can just iterate through all the divisors d (can be done in O(sqrt(N)). Count the total number of divisions necessary to reach that divisor which is equal to the number of prime factors of (N/d), and then calculate the shift cost.

The minimum among all of those shift costs found is the result.

During the match, I needed plenty of time to find a bug that was causing my last example to fail. It was not after a long wait that I finally noticed - I was only performing left shifts in my solution because I hadn't noticed yet that right shifts were also enabled.

Always read the problem statement paying attention to details. The delay was so low that I dropped many positions from the very hopeful situation I initially had.

Div1 1000
After (and while) triple-checking everything with the 250 and the 500, I opened the 1000 pointer. It is probably one of the most horrifying problems. I sort of figured that the answer is probably much easier than the problem appears, but I guess appearances are important to me. Eventually, many people solved it correctly, so in a strange way, this problem is supposedly easier than most of the recent 1000s. That is strange.

Challenge phase
I was either going to have a great position or to fail 500 and get a very bad position, in either case, a successful challenge is not that helpful, and the penalty of a negative challenge seemed like too much. I decided to be passive and avoid any problem.

System tests
My stuff survived and that is great. I reached 2075 which is an all time maximum. Hopefully I will be able to reach 2100 before the first semester of the year. That would allow me to try 2150 for a year target.