kofhearts's blog

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

In the following problem,

http://codeforces.com/contest/186/problem/C

I think for the input 0 the output should be 0 but i think the test case expects 1 or maybe this test is missing.

Read more »

 
 
 
 

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

I am very confused by this problem, especially with the third test case.

http://codeforces.com/contest/127/problem/C

It says the answer is

76 54

I am wondering why isn't the answer

114 81

Both gives the same final temperature

(143*114 + 81 * 456)/(114 + 81)

273.015384615

(143 * 76 + 456 * 54) / (76 + 54)

273.015384615

Since the temperature is same i thought that the higher values for y1 and y2 should be chosen since that will fill up faster. So, i thought 114 and 81 should be the optimal answer. Please help with this dilemma. I appreciate it!!

Read more »

 
 
 
 

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

I am confused by a case for the following problem

http://codeforces.com/contest/108/problem/B

the answer to the following test case is YES

7 1 2 3 4 8 16 32

I thought it was NO since the value that can fit in 16 bits, the square of that value will fit in 32 bits so therefore Tuftuf will not stop using Gava.

Thanks for the help!

Read more »

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

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

The question is here:

http://codeforces.com/contest/94/problem/C

In this problem how come the answer to the following input is 1?

Input: 21 5 1 21

Correct Answer: 1

My understanding is that if there are 21 files with row size 5 then the layout of the files is as follows:

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

Here, we need two selections 1st from 1 to 20 and 2nd for 21. Please correct me if i am wrong. Thanks for help!

Read more »

 
 
 
 

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

hello codeforces,

I am trying to understand the reason why only up to sqrt of n numbers are checked for factors. There is a maths theorem that if a number is not prime then it should have at least 1 factor which is less than sqrt(n). Is the following routine using that fact. My understanding is that in each iteration it is trying to find at least 1 such factor less than sqrt of n and once it finds it then the new n is updated to n / factor. This will give a new n and the same procedure is applied i.e another small factor is tried to be found in the range till sqrt of n. Please give me a better explanation if there is an easier way to understand why we just need to search till sqrt(n) for the factors. I appreciate it! Thanks!


def primes(n): primfac = [] d = 2 while d*d <= n: while (n % d) == 0: primfac.append(d) # supposing you want multiple factors repeated n //= d d += 1 if n > 1: primfac.append(n) return primfac

Read more »

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

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

hello codeforces,

I am trying to understand the reason why only up to sqrt of n numbers are checked for factors. There is a maths theorem that if a number is not prime then it should have at least 1 factor which is less than sqrt(n). Is the following routine using that fact. My understanding is that in each iteration it is trying to find at least 1 such factor less than sqrt of n and once it finds it then the new n is updated to n / factor. This will give a new n and the same procedure is applied i.e another small factor is tried to be found in the range till sqrt of n. Please give me a better explanation if there is an easier way to understand why we just need to search till sqrt(n) for the factors. I appreciate it! Thanks!

def primes(n):
    primfac = []
    d = 2
    while d*d <= n:
        while (n % d) == 0:
            primfac.append(d)  # supposing you want multiple factors repeated
            n //= d
        d += 1
    if n > 1:
       primfac.append(n)
    return primfac

Read more »

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

By kofhearts, 5 years ago, In English,

hello everyone,

I am having trouble understanding 3 dimensional dp. I can understand 2 dimensional dp but i am having trouble coming up with the objective function for this dp. Can someone please explain me what the state function will be like? I know the i, j position of the matrix will be two variables and the third variable will be remainder but i don't get how these three variables can be used to obtain the transition equation. I am especially having problem understanding dp with mod operation like this. I appreciate any help!

http://codeforces.com/contest/41/problem/D

I will summarize the problem.

Suppose there is a grid with number of coins in each cell.

1 2 3

4 5 6

7 8 9

There is a pawn in the bottom most row. Now the pawn can move either top right (eg.suppose if the pawn is at 8 he can move to 6(top right)) or top left(eg.suppose if the pawn is at 8 he can move to 4(top left)). The goal is to reach the top most row. Here is one way to do so. 8, 4, 2. Now we add all the coins that we received while landing to a cell.

The goal is to maximize this sum. The pawn has to start from the bottom most row and we can start from any cell from that row.

If this was the only question then i think it is straight forward 2 dimensional dp but the twist is that the maximum sum also has to be divisible by k. So, if s is the sum then s % k has to be 0.

I'd appreciate if anyone can explain to me the 3d dp solution. I don't seem to understand dp with mods. Thanks!

Read more »

Tags dp
 
 
 
 

By kofhearts, 5 years ago, In English,

hello codeforces community,

The problem is "any entry P is eliminated if the list has any entries strictly bigger than P below the position of P."

2 9

1 6

5 3

9 6

2 5

1 5

4 8

1 1

6 5

For example: 1 1 is eliminated since there is an entry below it 6 5, which is strictly bigger than 1 1. The problem is to find the entries that are left or are not eliminated? This is a simplified version of a problem already present in codeforces so i am not creating a new problem.

The polynomial O(n^2) algorithm is obvious since we can go from bottom to top and for each entry check if there is any item bigger than it below it. My question is if this can be done in linear time or better than polynomial O(n^2) time. I hope i can get some expert eyes on this problem i am facing. Thanks!

Read more »