Problemset 3

Problem Jewels:
there exists two papers that are quite useful to solve this problem:
cs.technion.ac.il/~michalz/lcscsa.pdf20
fano.ics.uci.edu/cites/Document/ ... oblem.html16

The first one can be adapted to be used for the non-reversed part, the other one can be used for the reversed part.
But without heavy optimization (both time and space) it is not possible to get Accepted.
I guess the key optimization was that I allocated a big array at the beginning of my program, and then I used my own memory management on that array.
Here are some code parts with comments that should make clear how the memory management works:

#define null QSIZE
typedef struct {
	int right,next;
}storage;
storage dp[QSIZE];
int st_ptr,head;
/* st_ptr tells the first position in the array that was not used so far
head points either to null or to a element between 0 and st_ptr-1 that can be used again (old value is not necessary any more)
if I follow the next pointers starting at dp[head], I get all such elements
*/
/* get a free storage position */
inline int get() {
/* if head points to null, there is no element that can be replaced,
so I have to increase the stack pointer */
   if (head == null)
       return st_ptr++;
/* otherwise, take the position that head points to and set head to dp[head].next */
   int v = head;
   head = dp[head].next;
   return v;
}
/* free a storage position */
inline void dispose(int ind) {
/* freeing is done by prepending element ind to the head of the list of free storage positions */
   dp[ind].next = head;
   head = ind;
}

The reason why this is such a big optimization:
initialisation is easy:
head = null; st_ptr = 0; is all that is needed.
So, with some pruning that stops the algorithm with a full table, there is no need to clear that table up, just reinitialize it in O(1).

But I would be interested to know if there is a faster algorithm than the one described in the first paper.

BYTELE.

My solution was like a

Sort vertices in SL order
(vertex with smallest degree is last in a sequence).
1: take next vertex:
try to place it minimizing the total length of cable used.
if succeed goto 1:

For each test case I was trying different city dimensions.

What about other ideas?
I'm also very interested in approaches to BURNCITY problem.

My aproach for Burning City is to find current position on the map like: SE SW NW or NE. Next I move diagonally to the opposite corner, and destroy all squares except water. (That can give final result about 13000)
And later to improve results I add some other ideas ...

I haven't much time to study the problemset 3, but I think I've invented some nice algorithm witch should be about n^2 log n in time and about |matchpoints| in memory (that's much...but I've invented algorithm by myself)
I would like to test it, so is it possible to submit the solution for JEWELS (in future?)

[my idea is: try to keep the lists of dominating points of LCS algorithm during increasing suffix and decreasing prefix]

Hello qbolec,

I adepted an algorithm for the LCS Consecutive Suffix Alignment problem to solve the task. This algorithm has space complexity of n^2 = |matchpoints| like your algorithm. But it runs in O(n^2) time and took about 26 sec to solve all the testcases. So I assume that no solution with a factor of log(8000) to the n^2 solution can solve the problem in the given time.
(Btw. my solution is quite well optimised )

You can test your program at
http://spoj.sphere.pl/problems/JEWELS/1

Problem Bytele:
My greedy placed vertices that had most number of already placed neighbours, and in case of a tie that with higher degree. If at least one neighbour was already placed, I randomly selected one of these placed neighbours and used it as "reference point" to reduce number of possible positions to O(side length of grid). I tried the distances from the reference point in increasing order. If for some distance there was at least one possible point, I randomly selected one of them and placed the point there (by creating the list of possible points I ignored points where the length needed differed by more than 10 from the best length for some point in this list).
I reached most solved cases (906) with grid dimensions 100 x 100, but I got a low score. With dimensions 46 x 46 I got the highscore (and still a lot of cases solved).

Problem burncity:
I didn't deserve the highscore there, my best result was due to a "bug" (I implemented something different by mistake than what I wanted first).
I use iterated randomized greedy. Each position gets some score that indicates how good it would be to place dynamit there. Places where water is adjacent diagonally get high score, whereas places with water adjacent from >= 3 directly adjacent fields are ignored (it wouldn't make sense to place dynamit there). There are some other conditions that I evaluate for the score.
Now I wanted to select the position with maximum score (or only slightly less) and among those that with minimum distance from current point. But because I didn't calculate the maximum score first, but at the same time the minimum distance, it happened that some intermediate result for maximum score set the minimum distance to a low value, and I ignored everything with higher distance.
Anyway, I believe it is possible to get a much higher score for that problem.

Can someone tell how to solve problem Crypto4? I only found the obvious optimization to try only key lengths m to (m/2+1), because it makes no sense to try divisors of some key length.

JEWELS, Really nice problem. I've jsut read the paper. (I've been writing thesis for our national training team so haven't come to SPOJ for quite a long time)
I have thought out similar ideas but too difficult to construct the complete algorithm system:( what a pity. You must have had hardwork in it:P
I'll try to write the program tomorrow;)

I hope there could be someone who'd like to share the solution of CRYPTO4

Is it really necesary to read the papers to solve 'JEWELS'.I am asking this because the paper is putting me off from solving the problem as i feel it is too tough.

Thanks,
Kashyap

Now I'm going to give a solution of problem CRYPTO4. Many Thanks to the help of Carlos Eduardo Rodrigues Alves.

Actually, we need to know all possible value of n. We can generate the whole message if and only if the value of n is known. A brute force solution is easy to find: for each n between 1 and m, decide if there's a conflict between the original message and the encoded message. If the answer is no, then generate the whole message. After comparing all the possible messages, you can find all the missing characters that can be determined.

This solution is too tough and actually gets Time Limit Exceeded. My solution is based on that, with these optimizations:

*Keep a list of the positions of the characters (called todo-list) that still have possibility to be fixed(i.e. We know the character on that position in the encoded message but we don't know the one in the original message.)
*Keep a list of the positions of the characters that is already known in both message. The conflict will occur on these characters.
*Obviously, if the messages are valid when n equals to some value x, then it must be valid when n equals to any multiple of x. So we only need to check all the values between m/2+1 and m(inclusive).
*Assume that now we are check if n = x is valid. The conflict will NOT occur before the x-th character.
*Once a character in some position can not be fixed, delete it from the todo-list.

These optimizations make the program terminate within the 17 second time limit.

P.S. After about 10 submissions in contest SPOJPL, I realized that there is only one test case which satisfies that m is about 100000 and the length of the message is about 1000000. So perhaps the solution above is fast only to this test case, but who knows...

Hey what's the problem with my code, that I get TLE ?? I have used sufficient optimization. Can anyone please help me out?

    int main(){
       int no,n,i,j,kbase,kval,top,N,misVal,counter;
       char tmp;
       bool flag;
       cin>>no;
       while(no>0){
          no--;
          string x,y;
          cin>>N;//Max length of cypher
          cin>>x;//Plain text
          cin>>y;//Encrypted text
         int kMap[x.length()][2];
         int mismatch[N+1];//As 0 is left unconsidered
        //Initializing the array containing the values of n that is never possible
         for(i=0;i<=N;i++)
             mismatch[i]=-1;
         top = -1;
         for(i=0;i<x.length();i++){
            //If both the values are known, we can determine the k values
            if((x[i]!='*')&&(y[i]!='*')){
               kval=(y[i]+26-x[i])%26;
               //Chekcing for possible mismatch
               for(j=top;j>=0;j--){
                  //Mismatch occurs
                  if(kMap[j][1]!=kval){
                     misVal=i-kMap[j][0];
                     mismatch[misVal]=1;
                  }
               }
               top++;
               //Insert the k value and the index in the k-map
               kMap[top][0]=i;
               kMap[top][1]=kval;
            }
          }
          //If a n is not possible, so is all its factors also, calculating those values
          for(i=0;i<=N;i++){
             if(mismatch[i]==1)
               storeMisVal(misVal,N,mismatch);
          }
          n=-1;
          char mem[x.length()];
          int k[N];//Array holding cyphers.
          counter=-1;
          //Initialzing array to hold the plaintext
          for(i=0;i<x.length();i++)
            mem[i]=1;
          //Detecting the value of n
          for(i=N;i>0;i--){
             if(mismatch[i]==-1){
                n=i;
             }else
                continue;
            counter++;
            //Initializing the values of k.
            for(j=0;j<N;j++)
              k[j]=-1;
            for(j=0;j<=top;j++){
              kbase=kMap[j][0];
              kbase%=n;
              k[kbase]=kMap[j][1];
            }
            for(j=0;j<x.length();j++){
               //The text is inelligible to compute, meaning for different n, the value is not unique.
               if(mem[j]==0)
                  continue;
              //If encrypted text is inelligible or plaintext is elligible,then print the plaintext as it is.
               if((y[j]=='*')||(x[j]!='*')){
                 if(counter==0)
                    mem[j]=x[j];
                 else if(mem[j]!=x[j]){
                    mem[j]=0;
                 }
                 continue;
               }
               kbase=j%n;
               if(k[kbase]==-1){
                 if(counter==0)
                    mem[j]=x[j];
                 else if(mem[j]!=x[j]){
                    mem[j]=0;
                 }
                 continue;
               }
               tmp=y[j]-k[kbase];
               if(tmp<65){
                 if(counter==0)
                mem[j]=(char)(tmp+26);
             else if(mem[j]!=(char)(tmp+26)){
                mem[j]=0;
             }
           }
           else{
             if(counter==0)
                mem[j]=tmp;
             else if(mem[j]!=tmp){
                mem[j]=0;
             }
           }
        }
      }
      //Print the generated plaintext, for those values with conflicting for different n, original plaintext letter is used.
      for(i=0;i<x.length();i++){
         
         if(mem[i]!=0)
           cout<<mem[i];
         else
           cout<<x[i];
      }
      cout<<endl;
   }
}
//Function to store the value and all their factors as well in the mismatch array.
int storeMisVal(int val,int max,int mismatch[]){
    int i;
    if(val<=max)
       mismatch[val]=1;
    for(i=val-1;i>0;i--){
        if(val%i==0){
           if(mismatch[i]!=1)
              storeMisVal(i,max,mismatch);
        }
    }
}