TOPCORDER SRM598 DIV2 BinPackingEasy

Problem is

Problem Statement
	Fox Ciel has some items. The weight of the i-th (0-based) item is item[i]. She wants to put all items into bins. The capacity of each bin is 300. She can put an arbitrary number of items into a single bin, but the total weight of items in a bin must be less than or equal to 300. You are given the int[] item. It is known that the weight of each item is between 101 and 300, inclusive. Return the minimal number of bins required to store all items.
Definition
	Class: BinPackingEasy Method: minBins Parameters: int[] Returns: int Method signature: int minBins(int[] item) (be sure your method is public)
Limits
	Time limit (s): 2.000 Memory limit (MB): 64
Constraints
-	item will contain between 1 and 50 elements, inclusive.
-	Each element of item will be between 101 and 300, inclusive.
Examples
0)
	{150, 150, 150, 150, 150} Returns: 3 You have five items and each bin can hold at most two of them. You need at least three bins.
1)
	{130, 140, 150, 160} Returns: 2 For example, you can distribute the items in the following way: Bin 1: 130, 150 Bin 2: 140, 160
2)
	{101, 101, 101, 101, 101, 101, 101, 101, 101} Returns: 5
3)
	{101, 200, 101, 101, 101, 101, 200, 101, 200} Returns: 6
4)
	{123, 145, 167, 213, 245, 267, 289, 132, 154, 176, 198} Returns: 8

and My Code is blow

public static int minBins2(int[] items){
  Arrays.sort(items);
 
  int sp = 0;
  int ep = Math.max(items.length -1, 0);
 
  int totalNum =0; 
  while(true){
   if(items[ep] > 199){
    totalNum ++;
    ep--;
   }else{
    break;
   }
  }
 
  while(ep >= sp){
   if(items[ep] + items[sp] <= 300){
    sp++;
   }
   ep--;
   totalNum++;
  }
 
  return totalNum;
 }


## Access Step ##

1. Sort Items
2. if items are bigger than 199 add totalNum
3. sum of first item and last item are bigger than 300
   last index -- and totalnum ++
.......

i think this is very easy

TOPCORDER SRM598 DIV1

The Question is

Problem Statement
	Fox Ciel received a string as a birthday present. However, the string was too long for her, so she decided to make it shorter by erasing some characters. The erasing process will look as follows: Find the smallest i such that the i-th character and the (i+1)-th character of the string are same. If there is no such i, end the process. Remove the i-th and the (i+1)-th character of the string, and repeat from 1. For example, if she receives "cieeilll", she will change the string as follows: "cieeilll" -> "ciilll" -> "clll" -> "cl". You are given a String s. Return the string she will get after she erases characters as described above.
Definition
	Class: ErasingCharacters Method: simulate Parameters: String Returns: String Method signature: String simulate(String s) (be sure your method is public)
Limits
	Time limit (s): 2.000 Memory limit (MB): 64
Constraints
-	s will contain between 1 and 50 characters, inclusive.
-	Each character in s will be a lowercase letter ('a'-'z').
Examples
0)
	"cieeilll" Returns: "cl" This is the example from the statement.
1)
	"topcoder" Returns: "topcoder" She won't erase any characters at all.
2)
	"abcdefghijklmnopqrstuvwxyyxwvutsrqponmlkjihgfedcba" Returns: ""
3)
	"bacaabaccbaaccabbcabbacabcbba" Returns: "bacbaca"
4)
	"eel" Returns: "l"

My Solution is Below

public static String simulate(String str){
  int start =0;
 
  while(str.length()-1 >start){
   char firstChar = str.charAt(start);
//   System.out.println(firstChar + " : fisrt");
   char nextChar = str.charAt(start+1);
//   System.out.println(nextChar +" : next");
   if(firstChar == nextChar){
    str = str.substring(0, start) + str.substring(start+2, str.length());
//    System.out.println("complete:" + str);
    if(start !=0){
     start--;
    }
   }else{
    start++;
   }
  }
 
//  System.out.println(str);
  return str;
 }


## Access Logic ##


my access is below but i don't think this is a good sample

because i just got 144point / 250 point

so other soultions are better than my solution

i attached other solution after my solution

cieeilll

first point is c
first+1 point is i

c and i is differenct so first point will be 2

first point is i
first+1 point is e

c and i is differenct so first point will be 3

firtst point e
first+1 point is e

e and e is the same so cut before first point "ci" and cut after firstPoint +1 to end "ill"
and concat before string and after string

this will be ciill

first point changed first-1



Otheres are Below

public static String simulate(String s){
  for(int i=0; i<s.length()-1 i++){
    if(s.charAT(i) == s.charAT(i+1)){
     s= s.substring(0, i) + s.substring(i+2, s.length);
     i=-1;
     }
  }
}



sombody use StringBuffer.delete

and sombody use Stack

many different way i learend from topcoder --V

Make small cafe DIY(Do it yourself)~

 

My name English Name is David Jung linving in korea.

 

2013/11/29 was just one year passed from meeting my girlFriend.

 

so I wanted make her surprized and mad samll cafe for her

 

i made it for about more than 20 hours.

 

 

 

 

complete

~

 

wow ~

Bubble Sort

Sort	Average	Best	Worst	Space	Stability	Remarks
Bubble sort	O(n^2)	O(n^2)	O(n^2)	Constant	Stable	Always use a modified bubble sort
Modified Bubble sort	O(n^2)	O(n)	O(n^2)	Constant	Stable	Stops after reaching a sorted array
Selection Sort	O(n^2)	O(n^2)	O(n^2)	Constant	Stable	Even a perfectly sorted input requires scanning the entire array
Insertion Sort	O(n^2)	O(n)	O(n^2)	Constant	Stable	In the best case (already sorted), every insert requires constant time
Heap Sort	O(n*log(n))	O(n*log(n))	O(n*log(n))	Constant	Instable	By using input array as storage for the heap, it is possible to achieve constant space
Merge Sort	O(n*log(n))	O(n*log(n))	O(n*log(n))	Depends	Stable	On arrays, merge sort requires O(n) space; on linked lists, merge sort requires constant space
Quicksort	O(n*log(n))	O(n*log(n))	O(n^2)	Constant	Stable	Randomly picking a pivot value (or shuffling the array prior to sorting) can help avoid worst case scenarios such as a perfectly sorted array.

this is bubble sort example



lets make it c language


#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[])
{
 int arr[] = {5, 1, 12, -5, 16, 2, 12, 14};

 int count;
 int i=0, j=0, k=0, temp;
 count = sizeof(arr)/sizeof(arr[0]);
 for(j; j<count -1; j++){
  for(i=0; i<count-1-j; i++){
   if(arr[i]> arr[i+1]){
    temp = arr[i];
    arr[i]= arr[i+1];
    arr[i+1]= temp;
   }
  }
 
  k=0;
  for(k=0; k<count; k++){
   printf("%d ", arr[k]);
  }
  printf("\n");
 }
 return 0;
}


result :

1 5 -5 12 2 12 14 16
1 -5 5 2 12 12 14 16
-5 1 2 5 12 12 14 16
-5 1 2 5 12 12 14 16
-5 1 2 5 12 12 14 16
-5 1 2 5 12 12 14 16
-5 1 2 5 12 12 14 16

Selection sort

 

Example. Sort {5, 1, 12, -5, 16, 2, 12, 14} using selection sort.

lets make it C language


#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[])
{
 int arr[] = {5, 1, 12, -5, 16, 2, 12, 14};
 int i=0;
 int j=0;
 int count=0;
 int min=0;
 int temp;

 count = sizeof(arr)/sizeof(arr[0]);


 for(i;i<count-1; i++){
  min =i;
  for(j=i+1;j<count; j++){
   if(arr[min]>arr[j]){
    min=j;
   }
  }
  temp = arr[i];
  arr[i] = arr[min];
  arr[min] = temp;
 }
 i=0;
 for(i=0; i<count; i++){
  printf("%d ", arr[i]);
 }
 return 0;
}

Html Youtube Link

this would be a good example

This is basic concept of Memoization in Javascript

<!DOCTYPE>
<html>
<body>
<script>
<!--  Basic use -->
function square(num){
return num*num;
}

console.log(square(10));

function squareMemoization(num){
var result= '';
if(!squareMemoization.cache[num]){
console.log("computing value..");
result = num * num;
squareMemoization.cache[num]= result;
}

return squareMemoization.cache[num];

}

squareMemoization.cache = {};

console.log(squareMemoization(10)); //First time when we call this function. It calculates the value &amp; cache it.
console.log(squareMemoization(10)); // Second time onwards it return the result from cache.
console.log(squareMemoization(20)); // square function will calculate again if its a new value.


var a = ["a", "b", "c"];


console.log('a.slice(1,2)');
console.log(a.slice(1,2));
console.log('a.slice(1)');
console.log(a.slice(1));
console.log(a);

console.log('Array.prototype.slice.call(a, 1)');
console.log(Array.prototype.slice.call(a, 1));

</script>
</body>
</html>