Topcoder SRM 642 div2



This is my third time in attending topcoder

and I got 815 grad T_T.


I think my skill and score will be higher than now if I continuously attend and study




http://community.topcoder.com/stat?c=problem_statement&pm=13553&rd=16085&rm=324592&cr=23054155


explanation : first I tried to solve this problem Brute-force Search

It mean all posiible I would search

this is may take O(n) if str length is higer time.

but I tried if str.length is cardinal number ,  find only center and one before, one after

and if str.length . even number search 3point, half and before of half, after of half



ex ) cardinal number : 129298481 : 1292 + 98481,  12929 + 8481




 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class ForgetfulAddition {
 
 public int  minNumber(String str){
  int len= str.length() ;
  int start = len / 2;
  int minNumber = Integer.MAX_VALUE;
  
  if(len % 2 == 1){ // 홀수
   int sum = Integer.parseInt(str.substring(0, start)) + Integer.parseInt(str.substring(start, len));
   minNumber = Math.min(sum, minNumber);
   sum = Integer.parseInt(str.substring(0, start+1)) + Integer.parseInt(str.substring(start+1, len));
   minNumber = Math.min(sum, minNumber);
  }else{ // 짝수
   int sum = Integer.parseInt(str.substring(0, start)) + Integer.parseInt(str.substring(start, len));
   minNumber = Math.min(sum, minNumber);
   if(len >2){
    sum = Integer.parseInt(str.substring(0, start+1)) + Integer.parseInt(str.substring(start+1, len));
    minNumber = Math.min(sum, minNumber);
    sum = Integer.parseInt(str.substring(0, start-1)) + Integer.parseInt(str.substring(start-1, len));
    minNumber = Math.min(sum, minNumber); 
   }
  }
  return minNumber;
 }

}


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class LightSwitchingPuzzle {
 public int minFlips(String str){
  char[] array = str.toCharArray();
  int count =0;
  for(int i=0; i<array.length; i++){
   if(array[i] == 'Y'){
    count++;
    for(int j=i+1; j<array.length+1; j = j+ (i +1)){
     array[j-1] = toggle(array[j-1]);
    }
    
   }
  }
  
  return count;
 }
 
 public char toggle(char a){
  if(a =='Y'){
   return 'N';
  }else{
   return 'Y'; 
  }
 }

}

Comments

Popular posts from this blog

Project euler 169 found clue

Floyd-Warshall's algorithm