Member SRM 505: Part 1

So, let me explain a couple of problems from a Topcoder Member SRM that I wrote and never got an editorial.

BTW, it was the last member SRM. I wanted to participate in it as tester simply because I was being selfish. I had an exam that day at that time and the practice of skipping exams in favor of SRMs was not helping my race to graduate, so I noticed it was a member SRM and I offered myself to test it a long time in advance.

At the end, when I remembered I was supposed to test it, it turns out that there were few problems ready so we improvised a couple of things. The div2 500 I will explain in this post inspired a div1 1000 that I have still not solved.

Div2 250: SentenceCapitalizerInator
Actually, since it is a member SRM and I wrote the problem, I can copy paste the statement in here.

You are given a simple paragraph containing a number of sentences, the original person who wrote the paragraph was in a rush and used only lower case letters ('a'-'z') for the words in the paragraph and did not use any punctuation other than a period to separate sentences. Your task is to fix the capitalization in the paragraph, the objective is to make it so every sentence in the paragraph begins with a capital (upper case) letter ('A'-'Z').


The paragraph is formatted as one or more sentences separated by single space (' ') characters. Each sentence consists of one or more words separated by single space (' ') characters. The last word in a sentence is always immediately followed by a single dot ('.') character. Each word is a non-empty string containing only lower case letters ('a'-'z'). As an example, consider the following paragraph (quotes for clarity):

You are given a simple paragraph containing a number of sentences, the original person who wrote the paragraph was in a rush and used only lower case letters ('a'-'z') for the words in the paragraph and did not use any punctuation other than a period to separate sentences. Your task is to fix the capitalization in the paragraph, the objective is to make it so every sentence in the paragraph begins with a capital (upper case) letter ('A'-'Z').



The paragraph is formatted as one or more sentences separated by single space (' ') characters. Each sentence consists of one or more words separated by single space (' ') characters. The last word in a sentence is always immediately followed by a single dot ('.') character. Each word is a non-empty string containing only lower case letters ('a'-'z'). As an example, consider the following paragraph (quotes for clarity):

"this is merely an example. be careful. this is a new sentence."

The result of your program must then be as follows:

"This is merely an example. Be careful. This is a new sentence."

Constraints
- paragraph will contain between 2 and 50 characters, inclusive.
- Each character in paragraph will be a lower case letter ('a'-'z'), a space (' ') or a dot ('.').
- The first character of paragraph will be a lower case letter ('a'-'z').
- The last character of paragraph will be a dot ('.').
- There will be no two consecutive space characters in paragraph.
- Every space (' ') character in paragraph will precede a letter.
- Every '.' character in paragraph except the last one will precede a space character.

It is a simple problem that needs more implementation than thought. Parsing strings in programming contests requires some practice and a mind quick enough to find shortcuts (else you end up doing very long and bug-prone codes.). In this case, I think the best idea is to find the link in common between all letters that we should capitalize. The constraints are very detailed and should make our lives easier.

We need to capitalize all the letters at the beginning of a sentence. By constraints, the first character will always start a sequence. And also every dot '.' (but the last one) will always be followed by a space and then a letter (the one that we have to capitalize). We can then say that the letters that we have to capitalize are those of the kind : ( index == 0 , or character at(index - 2 ) is a '.' ).

The code then gets simple:

string fixCaps(string paragraph) 
{ 
    int n = paragraph.size(); 
    for (int i=0; i<n; i++) { 
        if ( (i==0) || (paragraph[i-2]=='.') ) { 
            // Capitalize paragraph[i]. 
            paragraph[i] -= ('a'-'A'); 
        } 
    } 
    return paragraph; 
} 

Div2 500 - PerfectSequences
I just noticed what a massacre this member match was. It is no wonder it got such low ranking in the votes. This problem was a massacre because it was division 2, division 2 coders are very prone to making overflow mistakes and this problem was the archetypal "avoid overflow!" problem. Here is the statement:

A perfect sequence is a sequence such that all of its elements are non-negative integers and the product of all of them is equal to their sum. For example: {2,2}, {1,3,2} and {0,0,0,0} are perfect sequences and {4,5,6} and {0,2,-2} are not perfect sequences (4*5*6 is not equal to 4+5+6, and negative numbers are not allowed by the definition).

You are given a int[] seq. Return "Yes" if it is possible to change exactly one element of seq so that the resulting sequence is perfect. Otherwise, return "No".

Constraints
- seq will contain between 1 and 50 elements, inclusive.
- Each element of seq will be between 0 and 1000000000 (10^9), inclusive.

Ok, we must change exactly one of the elements of the sequence. We can pick any of those indexes and there are at most 50 of them. We can then try checking each of the possible indexes and see if it is possible to change the element in that position to make the sequence perfect.

Given an index i, is it possible to change the element in that index to make the sequence perfect? That is the same as saying that the new sum of all elements must be equal to the new product of all elements. The new value we will use instead of seq[i] will be called x. Let s = (sum of all elements but seq[i]) and p = (product of all elements but seq[i]). The new sum and product will be: (s + x) and (p * x), respectively. So we should have (s + x) = (p * x). This is a simple equation that becomes: x = s / (p - 1).

So, if we replace seq[i] with s / (p - 1), the sequence will become perfect. Here is where it gets a little complicated. Note that the division (p - 1) will only work if p is not 1 (else we would divide by 0). If p was 1 we have:

s + x = 1 * x.

Which is only true when s = 0. If s = 0, then any value of x would work and if s is not 0 then no value of x would work.

Another thing. The statement wants the elements in the sequence to be a) non-negative and b) integers. This means that x = s / (p - 1) must be a non-negative, integer number. If (s / (p - 1) is negative (can happen when p = 0) or if s is not a multiple of (p-1) then we cannot replace seq[i].

In addition, we have to replace seq[i]. If we found out that x = (s / (p-1) = seq[i] then we would not be replacing seq[i] as it would stay the same number. So, if (seq[i] = x) that is not a case either.

Repeat this logic for each index until we find one that works (or return No if we don't) to solve the problem.

Avoid overflow
As a sub-task we need to calculate s and p for each i. s is at most 49*1000000000 (There may be 49 other elements than i, and the maximum value is 1000000000). That number is too large for 32 bit integers, but not so large for 64-bit ones. That is not a problem. The real issue comes with p, as it can be at most 1000000000⁴⁹. The trick here is to notice that our objective is not to find the value of p, but to solve the equation s/(p-1). That result must be a integer, so as long as we know that it is not integer, we can just skip calculating it as we don't really have to. If p was too large, then s would become less than (p-1), and then s/(p-1) would not be able to become a integer. Unless s was 0, but in that case, s would be a multiple of any value of (p-1), so we do not need the actual value of p either.

If we ever find that the value of p would exceed s, we can just break the loop and stop multiplying. Because for practical purposes, any value of p larger than s would work in our logic the same as if we actually calculated p.

string fixIt(vector <int> seq)
 {
     int n = seq.size();
     
     for (int i=0; i<n; i++) {
         // Can we change seq[i] to make the sequence perfect?
         
         // Let:
         //     p = product of all seq[j] (j!=i)
         //     s = sum of all seq[j] (j!=i).
 
         // Find a x:
         //
         //     p * x = s + x
         //   x*( p-1) = s
         //         x =  s / (p - 1)    : x is a integer >= 0.
         
         long long s = 0;
         for (int j=0; j<n; j++) {
             if ( i!=j) {
                 s += seq[j];
             }
         }
         
         long long p = 1;
         for (int j=0; j<n; j++) {
             // Note that if (s < p-1), then there is no result...
             // if (p * seq[j] - 1 > s)
             //      ->  ( p * seq[j] > s + 1 )
             if (i!=j) {
                 if ( seq[j] == 0) {
                     p = 0;
                 } else if ( p > (s + 1) / seq[j] ) {
                     p = s+2; //any number larger than s+1 will work
                              //All of this is done to avoid 
                              //dealing with ultra large numbers (overflow)
                 } else {
                     p *= seq[j];
                 }
             }
         }
         if (p == 1) {
             if (s==0) {
                 //any value can do.
                 return "Yes";
             }
         } else if ( s % (p - 1) == 0 ) {
             // just change seq[i] to s/(p-1)
             // make sure that 0 <= seq[i] != s/(p-1) 
             long long x = s/(p-1);
             if ( x != seq[i] && x >= 0 ) {
                 return "Yes";
             }
         }
     }
     return "No";
 }