myaw's blog

By myaw, history, 11 months ago, In English,

Hello cf community,

I use memoization ( recurssive dp ) to solve dynamic programming, however it's not effecient in some cases, so I'm willing to change to bottom up dp or tabulaire dp, however I find it a bit difficult to understand, so is there anyone who was able to switch from one to another so he can share the steps to follow to switch between the two, something like:

I solved a dp problem using memoization follow these steps to transform it to a tabulaire dp.

Thanks.

Read more »

 
 
 
 
  • Vote: I like it
  • -7
  • Vote: I do not like it

By myaw, history, 3 years ago, In English,

I'm trying to solve this problem 514C, in simple terms you are given n strings and m queries, each query consist of a string s, can you find an equal string in the given n strings by changing only one character in s, (all strings consist only of 'a','b', and 'c')

My solution is brute force based: for each query change each character and try to find if it exist in the given strings using a HashSet, but I got a WA in pretest 6 can any one tell me what I'm doing wrong.

submission

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By myaw, history, 3 years ago, In English,

This solution is O(n) right? is it because java i/o ?

submission

Read more »

Tags tle
 
 
 
 
  • Vote: I like it
  • -10
  • Vote: I do not like it

By myaw, history, 3 years ago, In English,

Hi everyone.

I was trying to solve small input for this problem using recursive dp.

But it gives a strange runtime error when n >= 180000.

this my code

Any helps.

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By myaw, history, 4 years ago, In English,

The problem look like this : we have n object each object have a weight .

We want to create 2 groups of these objects so the number of objects on the two groups must not differ by more than 1 and the total weight of the objects on each group should be as nearly equal as possible.

examples :

n = 4 : 1 2 3 4 => ans : 5 5

n = 4 : 1 2 3 11111 => ans : 5 11112

n = 3 : 100 90 200 => ans :190 200

my code works fine for small input how ever it gives negative values for large input (n >= 25 ) . My code

You should now that n<=100 and the sum of weights is <= 1e6 .

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By myaw, history, 4 years ago, In English,

I just solved this dp problem , i compared my code to an accepted code by trying random test cases , and it gives correct results , how ever it gives MLE in the onligne judge ( only 32M of memory )

So my question is how to prevent this ??

My code

Problem statement :

A tug of war is to be arranged at the local office picnic. For the tug of war, the picnickers must be divided into two teams. Each person must be on one team or the other; the number of people on the two teams must not differ by more than 1; the total weight of the people on each team should be as nearly equal as possible.

Input

Input starts with an integer T (≤ 100), denoting the number of test cases.

The first line of each case is a blank line. The next line of input contains an integer n (2 ≤ n ≤ 100), the number of people at the picnic. n lines follow. The first line gives the weight of person 1; the second the weight of person 2; and so on. Each weight is an integer between 1 and 100000. The summation of all the weights of the people in a case will not exceed 100000.

Output

For each case, print the case number and the total number weights of the people in two teams. If the weights differ, print the smaller weight first.

Sample Input

2

3 100 90 200

4 10 15 17 20

Output for Sample Input

Case 1: 190 200 Case 2: 30 32

Read more »

 
 
 
 
  • Vote: I like it
  • -3
  • Vote: I do not like it

By myaw, history, 4 years ago, In English,

I just solved this problem in uva.onlignejudge 10664 a classical dp problem ( you have n weights and you want to find a way to distribute these weights equally between 2 people ) so you only need a simple dp to find (total sum of weights ) / 2 using given weights .

but what if we decided to shares these weight between k people how to solve that ? do we have to keep track on the chosen weights ??

Read more »

 
 
 
 
  • Vote: I like it
  • +1
  • Vote: I do not like it

By myaw, history, 4 years ago, In English,

I was trying to solve K-Tree 431C But i'am getting WA in protest 5 , the input is 0 , this is my 12482418 any helps ??

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By myaw, 5 years ago, In English,

If any one could explain or give me a good tutorial (c++) to understand the approach of dfs . thanks.

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it