My Blog List

Tuesday, May 17, 2016

problem 287 in project euler

I took 5 hours to solve this problem. thinking time and coding time is 5hours 1.my first approch this problem was math approach D1, D2, D3, D4 and there is nothing related to math. 2. second was finding pattern. with eclipse tool I was able to draw D1, to D7 but nothing found without only one thing that is black circle. 3. thought lots time and look deeply more and more. 4. finally found that It could be possible that whether all blocks are colorerd black or not if I check only four couners. 5. divide and conquer bruteforce check. 6. I got answer after 5min process. I think it it too long. 7. I started customized removing duplicated conditions. 8. 10second. 9. I changed Math.pow to a * a . 10 finally I can solve this one within 1 second

Monday, May 16, 2016

codefights turnsOnRoad


I divide into 4 side
right, top, left, bottom and finally check.



this is problem
https://codefights.com/challenge/7WzF2fGJA6nKaMbNR

Wednesday, May 11, 2016

Cross Bridge in minimum time in codefights

This is veryintersting and I just worte down some testcases and
found algorithm.
someday I will write detail of this problem.


my code is here
 int c, l;
 int Bridge(int[] t) {
  l=t.length;
  Arrays.sort(t);
  
  while(l>3) {
   c+= Math.min( 2*t[1],  t[l - 2] + t[0]) + t[l-1] + t[0];
   l-=2;   
  }
  return c+= l<3?t[l-1]:t[1] + t[0]+t[2];
 }

https://codefights.com/challenge/K4HYozLrbRoLHkt8P

Tuesday, May 10, 2016

MaxCupCake in codefights

this is good problem.

https://codefights.com/challenge/X33imTX2FSqhSLTtJ


My code is

        int c, i,t;
 int MaxCupCakes(int N, int[] P, int K) {
  for (; i < P.length; i++ ) {
   t= (P[i] -c -1);
   if(K<=t) break;
   K=K-t;
   c=P[i];
  }  
  return c+K<= N ?c+K : -1;  
 }


best code is here
 int MaxCupCakes(int n, int[] P, int k) {
     for(int i:P) 
         if(i<=k)k++;
           
  return  k>n ?-1 : k ;
 }




Max and Caroline, two girls in their mid-twenties, work at a Brooklyn restaurant as waitresses. Together, they dream of starting up their cupcake business.
One day Max comes with a box of N cupcakes numbered according to their quality from 1 to N. Caroline has a list of cupcakes P that should be removed from the box.
Your task it to find the quality of the Kth cupcake after the cupcakes from the list P are removed from the box.
If it is not possible to get the Kth cupcake, return -1 instead.
Example
For N = 4P = [1] and K = 2, the output should be MaxCupCakes(N, P, K) = 3.
Initially there were cupcakes of the following quality: 1, 2, 3, 4. According to P, the cupcake with quality 1 should be removed, so only the following cupcakes are left: 2, 3, 4. The 2nd cupcake in this list is 3, thus the output should be 3 as well.
  • [input] integer N
    The number of cupcakes, 4 ≤ N ≤ 109.
  • [input] array.integer P
    A sorted array of positive integers, the cupcakes to be removed. 0 ≤ P.length ≤ 500, 1 ≤ P[i] ≤ N.
  • [input] integer K
    A positive integer, the 1-based number of the cupcake to find.
  • [output] integer
    The quality of the Kth cupcake, or -1 if less than K cupcakes are left.

Sunday, May 8, 2016

problem 243

hint is EulerPhi / n-1

and second focus is how to short running time~!

Wednesday, May 4, 2016

topcoder srm 690 div2 medium

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

Monday, May 2, 2016

Minimum coin numbers

this is somehow easy dynamic problem.

this is my python code
coins = [1, 2, 5, 10, 20, 50, 100, 500, 1000]

def find(coins, target):

    list = [];
    for i in reversed(range(len(coins))):
         print(coins[i])
         while target>= coins[i]:
             target = target - coins[i]
             list.append(coins[i])

    return list

list = find(coins, 93 )
print(list)