Thursday, March 31, 2011

Member SRM 501 - FoxProgression

FoxProgression problem statement.
This division 2 problem was kindly donated by wrong. Make no mistake, thinking of good problems is not easy, so giving them for free to Topcoder just so that we still get to get three SRMs a month instead of only two, is a good thing.

This problem asks us to count the number of ways we could add a new element to a sequence so that the final sequence is an arithmetic progression or a geometric progression. Perhaps the first thing to notice is that the element added is always going to be the last element. We cannot insert this element in the middle of the sequence, this means that we cannot really modify the nature of the first elements of the sequence. If the original sequence is not an arithmetic progression, then we cannot make it an arithmetic progression by adding a new element to the last position. The same happens with geometric progressions.

For now, we will focus on the arithmetic progression aspect of it. If the original sequence seq is an arithmetic progression, then for every i seq[i]-seq[i-1] = a constant. We will call this constant dif as seq[i]-seq[i-1] is a difference. How can we find dif? Simply pick any pair of consecutive elements, and subtract them. We will pick the first two elements: (dif = seq[1] - seq[0]). Now, note that we should not make assumptions, the original sequence will not necessarily have at least two elements. How can we calculate dif if the sequence only has one element?

If the sequence only has one element, it does not really matter, we could add any number to it and the result will be an arithmetic sequence. Because all sequences of two elements have a single difference between its only two elements, which are consecutive. This means that if the original sequence only had one element, there would be infinitely many numbers we could add. The problem statement specifies that this situation is possible, and it tells us to return -1 in that case. Therefore, if the sequence has one element, return -1.

Back to cases with more than one element in the sequence. We have calculated (dif = seq[1]-seq[0]) for the original sequence to be an arithmetic progression, we should verify that for every i, (seq[i]-seq[i-1] = dif). This will imply that the difference is always constant. In case we find that the difference is constant, we can claim that seq is an arithmetic progression, we can also claim that dif is the constant difference. Do not forget that we are going to add a number X to the end of this sequence, and that the new sequence must stay an arithmetic progression, because of this: (X - seq[n-1] = dif) Where seq[n-1] is the last element in the original sequence. We can conclude that if (X = seq[n-1] + dif), then we can have an arithmetic progression after adding X and only after adding X.

In the case of geometric progressions, the situation is very similar, except that we will have a constant q such that: (q * seq[i-1] = seq[i]). The value of q can be calculated by (q = seq[i] / seq[i-1] ). Note that we are doing a division so we would not want seq[i-1] to be 0, but that is not a problem because all elements of seq are going to be greater than 0 per the constraints definition. Then we can use the newly found value of q, and make sure that the sequence is geometric, that is : (q*seq[i-1] = seq[i] ) . Note that it is not convenient to use division in this case because of rounding causing issues. If the sequence is a geometric progression and the constant factor is q, then we can say that a new number Y to be added to the end of the sequence must be such that: (Y = seq[n-1]*q ).

Adding both logics together includes some challenges. There are four cases to consider:

  • The sequence is both an arithmetic and a geometric progression.- This can actually happen with for example seq={4,8} (From the examples) 4+4 = 8 and also 4*2 = 8. If we follow the logics from the previous paragraphs, we will find that (X = 8+4 = 12) and (Y = 8*2 = 16) . In other words, we can add both 12 and 16 to the sequence and the new sequence will be arithmetic or geometric. In this case the result is 2, there are two different number (12 and 16) that do the job.

    It is actually possible that both X and Y are equal. In example 2) seq = {1,1} and (X = 1+0 = 1) and (Y = 1*1 = 1). Since both are equal, there is only one number (1) that we need to count. The result is 1.

    The trick is to simply say: If (X=Y) then the result is 1, else it is 2. Some coders made the mistake of assuming that only {1,1} was special like this and only handled that specific sequence. But for example, {500,500,500} and any sequence of equal numbers will have equal values of X and Y.

  • The sequence is only an arithmetic progression.- Then the only number that can do the job is X, the result is 1.

  • The sequence is only a geometric progression.- Then the only number that can do the job is Y, the result is 1. We can add these two cases together and just say that if the sequence is only arithmetic or only geometric, the result is 1.

  • The sequence is neither arithmetic nor geometric.- Then we cannot do anything, we can add any number, the new sequence will not become arithmetic or geometric because we cannot change the first part of it. The result is 0.



Hey, this problem was definitely easier to solve than to explain, but it may be clearer with just some sample source code:

int theCount(vector <int> seq)
{
int n = seq.size();
// If there is only one element,
// then there are infinitely many ways
// to have this.
if (n==1) {
return -1;
}
// Arithmetic difference
int dif = seq[1] - seq[0];
// Geometric factor
int q = seq[1] / seq[0];

// Verify that the sequence is arithmetic/gemetric or both
bool cangeo = true;
bool canari = true;
for (int i=1; i<n; i++) {
canari &= ( seq[i]-seq[i-1] == dif );
cangeo &= ( seq[i-1]*q == seq[i] );
}
// Possible values for the next element in the
// arithmetic progression and the geometric progression
int x = seq[n-1]*q;
int y = seq[n-1]+dif;

// If both are possible, verify that the numbers are
// actually different, For example with {1,1} it is
// possible to have {1,1,1} no matter if we use an
// arithmetic progression or a geometric one. (example 2)
if ( cangeo && canari ) {
return ( x!=y ) ? 2 : 1;
} else if (cangeo || canari) {
return 1;
} else {
return 0;
}

}

Some late SRM reports

I have not been logging things correctly into my blog, so I will try to do some recap.


SRM 498: A most horrendous rating drop. This SRM made me notice that the Hard-medium-easy strategy was not working. Case in point, due to it being justifiable for me to do badly when using this strategy, I was not taking SRMs seriously. I failed the easy problem because of not doing a O(n^5) even though everything indicated it would work fine. For some reason I thought that this time, doing ad hoc checks was going to be simpler to code than a n*n*n*n loop. Although in a way it was, it was very easy to miss a single mistake which was not caught by the example tests. Blunder: Trying clever code instead of one you know is going to work is not a good idea. It is going to take a while to recover the 145 rating points that were lost that day.

SRM 499: I decided to move to a new strategy which is similar to the one I was using until 2010. I start with the medium-difficulty problem first. However, instead of switching to the easy when there are 30 minutes left, I wait until there are only 15 minutes left. This way, I will force myself to take the medium more seriously than before, and also to be fast at solving the 250. I was tired of taking whole half hours to solve the "Easy" problem, I'd rather get 0 points...

This match's results were nice, they gave me hope about the new strategy. After trying the 500 problem for a while, I got very close to the dp solution, but I was having trouble with some of the example cases. I had to switch to the easy problem when there were only 15 minutes left. But it turned out to be a very easy problem that only took me 4 minutes to solve. When I returned to the 500, my mind was refreshed and it finally struck-me : I had cycles in the recurrence. Before doing memoization, always make sure your recurrence is cyclic, it is the basic thing to do. I managed to fix the cycle, and submit. Everything went well.

I was assigned to write the editorial for this match. I think the 1000 points problem was very nice, but that's probably because I don't usually get the chance to see Strongly-Connected-Components used in problems that are not easily simplified to them.

SRM 500: Did not like this match. I think that a harder than usual 250 was not suitable for a celebration kind of match. It became a downer. Actually there were some other old timers in my room and we were all saying basically the same during intermission. The 500-pointer was nice. I actually had something that resembled a correct solution to it but had problems debugging it. I made the mistake to switch to the other problem at a very bad time. I should have switched much earlier or not switch at all.

Member SRM 501
I open the 500 first. I was able to think of a dynamic programming solution very quickly. So much that I initially thought that the challenge in this problem was that O(n5) was not going to work and O(n4) was required. But I noticed that with memoization you can do plenty of cropping if your recurrence includes the current sum and also that the constraint for the length was 40 and not 50. Those things gave me enough of a reason to try and code the O(n4) solution and try it in the worst case. It turns out it solved the worst case - an array full of -1 - in less than 0.8 seconds.

The easy was a different story. At first, I noticed that it is probably never necessary not to do all the additions consecutively. So operations are always in the form BB...BAA...ABB..B , the first B operations do nothing because they are multiplied with 0. Then the other ones multiply nA * a (The result of all the additions). I unfortunately make the mistake to, after reading the examples, assume that the number of times to multiply b is either 0 (When it is not convenient to multiply at all), nB (When it is convenient to multiply as much as possible) or nB-1 (when the factor b is negative, it pays to do multiply only an even number of times). This passed the example tests, and I submitted the solution. But I had many doubts.

Blunder: nB was actually constrained to be less than or equal to 50. I could have actually just picked all possible values of t=0,1,...nB to raise b to before multiplying it to nA*a. Instead, I only picked 0, nB and nB-1, this was an unnecessary assumption.

I had my suspicions after noticing the low constraints for nA and nB. Tried to make a dynamic programming solution, but I was unfortunately having issues implementing it correctly. Blunder: I switched to the 1000 points problem before making sure the 250 was correct. Some time after, I noticed I really had no clue how to solve the 1000-pointer. So, I kept opening 500 and 250 trying to find typing errors. I eventually figured I could just code a bruteforce solution for 250, that would only work when nA+nB<=10, so I could call both of my solutions with random cases and see if they always agree. After finishing the bruteforce solution and making a program that would generate random cases for the solutions, it didn't took the random number generator much time before finding a case my original solution failed: {1, 8, -2.097, -0.883} After some inspection, I noticed that in that case we need to multiply b exactly once. This is the moment where I finally noticed that I can pick any number of times to multiply b between 0 and nB. After changing the solution to do that, I ran the random number generator again, and it was not finding any mistake. I submitted the new solution, but a long time had passed since the first submission, I ended up getting only 79 points for it.

During the challenge phase, I knew that the test case I found during the coding phase was going to make plenty of solutions to fail, but I just couldn't find the wrong solutions, and parse them well enough to notice they didn't resist that case before they were challenged. After the match I noticed that if I just used that challenge blindly on all the lower rated coders in the room I would have been able to recover all that I lost because of the resubmission. But I am not really an aggressive challenger, and I am not sure how well this sort of blind challenging strategy would work in general. What I can tell is that aggressive challenges are not my style, so I am probably not going to try it soon.

I am not sure if the 500 was too easy or if I am just too used to dynamic programming problems. I could tell many of the submissions had very long, complicated codes for some reason.