topcoder srm 690 div2 medium

이문제를 O(N^2) 이 아닌 방법으로 찾아보려고 하다가 결국에는
O(N^2)방법으로 풀었다.
부등호 하나 잘못 작성해서
system run 에서는 fail ㅠ.ㅠ
다음부터는 조금 더 꼼꼼히 해봐야겠다.,

Topcoder SRM 689 NonDeterministicSubstring

this problem is about

Problem Statement
	You are given two Strings: A and B. Each character in A is either '0' or '1'. Each character in B is '0', '1', or '?'. A string C matches B if we can change B into C by changing each '?' in B either to '0' or to '1'. Different occurrences of '?' may be changed to different digits. For example, C = "0101" matches B = "01??". Note that each character in C must be either '0' or '1', there cannot be any '?' remaining. Consider all possible strings that match B. How many of these strings occur as a (contiguous) substring in A? Compute and return their number. Note that we only count each good string once, even if it has multiple occurrences in A.
Definition
	Class: NonDeterministicSubstring Method: ways Parameters: String, String Returns: long Method signature: long ways(String A, String B) (be sure your method is public)
Limits
	Time limit (s): 2.000 Memory limit (MB): 256 Stack limit (MB): 256
Constraints
-	A will contain between 1 and 50 characters, inclusive.
-	B will contain between 1 and 50 characters, inclusive.
-	Each character in A will be '0' or '1'.
-	Each character in B will be '0', '1' or '?'.
Examples
0)
	"00010001" "??" Returns: 3 There are four strings that match B: the strings "00", "01", "10", and "11". Out of these, the string "11" does not occur in A as a substring. The other three do occur, hence the answer is 3.
1)
	"00000000" "??0??0" Returns: 1 There are 16 different strings that match B, but out of those only the string "000000" is a substring of A.
2)
	"001010101100010111010" "???" Returns: 8 Each of the 8 strings that match B occurs somewhere in A.
3)
	"00101" "??????" Returns: 0 Here, the length of B is greater than the length of A. Clearly, a string that matches this B cannot be a substring of this A.
4)
	"1101010101111010101011111111110001010101" "???????????????????????????????????" Returns: 6

=========================================================
My approach


1. A>B and
2. Find B length
3. Make all possible String with length of B and push HashSet
4. HashSet will filter duplication.
5. and finally only unique strings remain in hashset
6. compare all string with B if index of character is not ?
7. count all if it is match


my code is below

public long ways(String A, String B){
  HashSet<String> set = new HashSet<String>();
  
  int blen = B.length();
  for (int i = 0; i <= A.length()-blen; i++) {
   set.add(A.substring(i, i+blen));
  }
  
  Iterator<String> iter =  set.iterator();
  int count =0;
  while (iter.hasNext()) {
   String str = iter.next();
   boolean found = true;   
   for (int i = 0; i < blen; i++) {
    if(B.charAt(i)!= '?'){
     if(A.charAt(i) != B.charAt(i)){
      found =false;
      break;
     }
    }
   }
   if(found){
    count++;
   }
  }
  return count;
 }

Topcoder Srm 626 div2 500 problem

When I tried to solve this problem, I didn't exactly know about expected value.
know I can liite understand it

problem is get expected value if A value is larger than B


A. 2 sided
B. 2 sided

case is (2,1)
so expected value is 2

A. 4-sided
B. 2-sided

(4,1) (4,2) (3,1) (3,2) (2,1)
4+4+3+3+2 / 5 = 3.2

this is what i learn from this problem.

Topcoder SRM 647 div2 500problem

I solve this problem in two way

one way is two for 

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 27 28 29 30 31 32 33 34

public static int getMaxProfit(int M, int[] profit, int[] city, int[] visit){ int len = visit.length; int sum = 0; int maxPossible=0; int maxCitiIndex=0; for (int i = 0; i < len; i++) { // find visitable array. boolean find = false; for(int j=0; j<city.length; j++){ if(visit[i] == city[j]){ if(maxPossible < profit[j]){ maxPossible = profit[j]; maxCitiIndex =j; find = true; } } } if(find){ profit[maxCitiIndex] = 0; sum+= maxPossible; } maxPossible=0; maxCitiIndex=0; } return sum; }

and  the other is

make List array and reversOrder

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

public static int getMaxProfit(int M, int[] profit, int[] city, int[] visit){ ArrayList<Integer>[] list = new ArrayList[M+1]; int max = 0; for (int i = 0; i < list.length; i++) { list[i] = new ArrayList<Integer>(); } for (int i = 0; i < city.length; i++) { list[city[i]].add(profit[i]); } for (int i = 0; i < list.length; i++) { Collections.sort(list[i], Collections.reverseOrder()); } for (int i = 0; i < visit.length; i++) { if(list[visit[i]].size() > 0){ Integer x = list[visit[i]].remove(0); max += x; } } return max; }

Topcoder SRM 639 div 2 500 problem.

If I solve this problem I sholud know find N

ex) 1+2+3+5... +N = 5050

n*(n+1)/2 = 5050

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 27 28 29

package srm639; /** * n(n+1)/2 = x 1+2+3+4+5+N * @author ddavid * */ public class AliceGameEasy { public static void main(String args[]){ AliceGameEasy age= new AliceGameEasy(); System.out.println(age.findMinimumValue(10, 0)); System.out.println(age.findMinimumValue(932599670050l, 67400241741l)); } public long findMinimumValue(long x, long y){ long sqrt = (long)Math.sqrt((x+y) *2); if(sqrt *(sqrt +1) != (x+y) *2){ return -1l; } long sum =0l; int cnt =0; while(sum < x){ sum += sqrt; sqrt--; cnt++; } return cnt; } }

Topcoder SRM 636 250 problem.

One of my hobbies is solving algorithm problem in topcoder.

I'm very interested in learning.

Today I solve this problem.

http://community.topcoder.com/stat?c=problem_statement&pm=13543&rd=16082

My access was make two subsets and there are intersection between A and B

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 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58

package srm639; import java.util.HashSet; /** * 14분 걸림 * @author ddavid * */ public class ElectronicPetEasy { public static void main(String[] args) { // TODO Auto-generated method stub ElectronicPetEasy ep= new ElectronicPetEasy(); // System.out.println(ep.isDifficult(3, 3, 3, 5, 2, 3)); // System.out.println(ep.isDifficult(1, 1000, 1000, 2, 1000, 1000)); System.out.println(ep.isDifficult(1, 1, 1, 2, 2, 2)); } public String isDifficult(int st1, int p1, int t1, int st2, int p2, int t2){ HashSet<Integer> set = new HashSet<Integer>(); HashSet<Integer> set2= new HashSet<Integer>(); set.add(st1); for(int i=1; i<t1; i++){ int val = st1+(p1*i); set.add(val); } set2.add(st2); for(int i=1; i<t2; i++){ int val = st2+(p2*i); set2.add(val); } System.out.println(set); System.out.println(set2); int totalSize =set.size() + set2.size(); //merge size set.addAll(set2); if(totalSize == set.size()){ return "Easy"; }else{ return "Difficult"; } } }

Topcoder SRM 640 div2 500problem

It took about 1hour to solve this problem

In contest I failed to solve this one.

After days later I retried to solve this one

Finally I was able to solve this one.

My code is below

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 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67

package srm640; import java.util.Arrays; public class NumberGameAgain { public static void main(String[] args) { NumberGameAgain num = new NumberGameAgain(); // int k=40; // long table[] = {2l,4l,8l,16l,32141531l,2324577l,1099511627775l,2222222222l,33333333333l,4444444444l,2135l}; int k=3; long table[] = {2,4,6}; // int k=5; // long table[] = {2,3}; num.solve(k, table); } public long solve(int k, long[]table){ // 1차 필터링 Arrays.sort(table); for(int i=table.length -1; i>0; i--){ long val = table[i]; hello: while((val = val /2) > 1){ for(int p = i-1; p>= 0; p--){ if(table[p] == val){ table[i] = -1; break hello; } } } } long total = (long) Math.pow(2, k) -2; for(int i=0; i<table.length; i++){ long val = table[i]; for(int j=1; j<k+1; j++){ if(table[i] == -1) continue; //System.out.println("j : " + j + " Math.pow(2, j) : " + Math.pow(2, j)); if(Math.pow(2, j) > table[i]){ //System.out.println("minus : " +(Math.pow(2, k-(j-1)) -1)); total -= Math.pow(2, k-(j-1)) -1; break; } } } //System.out.println(total); // System.out.println(Arrays.toString(table)); return total; } }

Topcoder SRM 646 Div2 500 problem

I was not ablet to solve this promblem when participated in the contest.

and I see other people's source and finally i rewrite and sovle this problem using Queue

my code is

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 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92

package srm646; import java.util.LinkedList; import java.util.Queue; public class TheGridDivTwo { public static void main(String[] args) { int [] x = {5, 1, -1, 4, 1, 3, 5, 2, 1, -1, 4, 2, -1, -1, 0, -2, 3, 3, 1, 2, 4, 4, 1, 2, 3, 2, 3, 5, -1, 0, 1, 5, 4, -2, 5, 0, 0, 4, -2, 0, 3}; int [] y = {3, 4, 2, 1, -2, 4, -2, 0, 1, -1, 0, 2, 5, 1, 3, 4, -2, 1, 2, 5, 2, -2, 5, -2, 3, 3, 5, 5, 0, 4, 0, 1, 4, 0, 4, -2, 2, -1, -2, 1, 0}; int k = 11; TheGridDivTwo two = new TheGridDivTwo(); System.out.println(two.find(x, y, k)); } public int find(int[] x, int[] y, int k){ Queue<Point> queue= new LinkedList<Point>(); int[][] visited = new int[2001][2001]; for(int i=0;i<x.length; i++){ visited[x[i]+1000][y[i]+1000] = 1; } if(x.length == 0){ return k; } Point start = new Point(0, 0, k); visited[1000][1000] = 1; queue.add(start); int maxX = 0; while(!queue.isEmpty()){ Point point = queue.poll(); if(point.sec <= 0){ continue; } Point right = new Point(point.x + 1, point.y, point.sec-1); Point top = new Point(point.x , point.y + 1, point.sec-1); Point bottm = new Point(point.x , point.y - 1, point.sec-1); Point left = new Point(point.x - 1, point.y, point.sec-1); // right if(!isVisited(right, visited) ){ queue.add(right); maxX = Math.max(maxX, point.x +1); } // top if(!isVisited(top, visited) ) queue.add(top); // bottom if(!isVisited(bottm, visited)) queue.add(bottm); // left if(!isVisited(left ,visited)) queue.add(left); } return maxX; } public boolean isVisited(Point point, int[][] visited){ int x = point.x; int y = point.y; int sec = point.sec; if((sec + x < 0) || visited[x+ 1000][y+1000] == 1){ return true; } visited[x+ 1000][y+1000] = 1; return false; } class Point{ private int x; private int sec; private int y; public Point(int x, int y, int sec) { this.x = x; this.y = y; this.sec = sec; } } }

Topcoder SRM645 div2 500 Editorial ~!!

The problem site is : problem link

below is thinking of the steps of the problem.

and My code is here

If you have any question comment plz~

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 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85

package srm645; import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; public class ConnectingCarsMycode { private long minimizeCost(int[] position, int[] lengths) { int len = position.length; ArrayList<Car> cars = new ArrayList<Car>(len); for(int i=0; i<len; i++){ Car car= new Car(position[i], lengths[i]); cars.add(car); } Collections.sort(cars, new CustomComparator()); int centerPosition = position.length/2; long totalMove = 0l; // left car to right for(int i=centerPosition; i>0; i-- ){ Car right= cars.get(i); Car left = cars.get(i-1); int move = right.position - (left.position + left.length); left.position = left.position + move; totalMove += move; } // right car to left for(int i=centerPosition; i<len-1; i++){ Car left= cars.get(i); Car right = cars.get(i+1); int move = right.position - (left.position + left.length); right.position = right.position -move; totalMove += move; } return totalMove; } public class CustomComparator implements Comparator<Car>{ @Override public int compare(Car o1, Car o2) { return o1.position - o2.position; } } public class Car { int position ; int length; Car (int position, int length){ this.position = position; this.length = length; } @Override public String toString() { return "Car [position=" + position + ", length=" + length + "]"; } } public static void main(String args[]){ int [] position = null; int [] lengths = null; position = new int[] {1, 3, 10, 20}; lengths = new int[] {2, 2, 5, 3}; ConnectingCarsMycode car = new ConnectingCarsMycode(); System.out.println(car.minimizeCost(position, lengths)); position = new int[] {100, 50, 1}; lengths = new int[] {10, 2, 1}; System.out.println(car.minimizeCost(position, lengths)); position = new int[] {4, 10, 100, 13, 80}; lengths = new int[] {5, 3, 42, 40, 9}; System.out.println(car.minimizeCost(position, lengths)); position = new int[] {5606451, 63581020, 81615191, 190991272, 352848147, 413795385, 468408016, 615921162, 760622952, 791438427}; lengths = new int[] {42643329, 9909484, 58137134, 99547272, 39849232, 15146704, 144630245, 604149, 15591965, 107856540}; System.out.println(car.minimizeCost(position, lengths)); } }