john_hopes's blog

By john_hopes, history, 13 months ago, In English,

Suppose, I know m1, m2, m3 and P1, P2, P3 of the following equations. Here P1, P2, P3 are prime numbers.

X mod P1 = m1

X mod P2 = m2

X mod P3 = m3

Now, for another prime number P4,

I need to find, X mod P4 = ?

Using Chinese Remainder Theorem I can calculate this if P4 is not a prime and is equal to (P1xP2xP3).

How can I solve this problem for any prime P4?

Read more »

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

By john_hopes, history, 14 months ago, In English,

Is there anyone can help me to solve this problem?

Problem Link: https://open.kattis.com/problems/foolingaround

Problem Description:

Alice and Bob take turns playing a game, with Alice going first. They begin with a pile of N stones, each turn removing one less than a prime number of stones. The person who removes the last stone wins. Given N, determine who wins the the game.

Constraints: N>0 and N<=10^9

I already read some solutions. They just pre calculated all the N for which Second Player wins and answer each query.

How can I pre calculate all the N(Second Player wins)?

Read more »

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

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

Could you please give me some Problems Link which requires DP+Priority Queue or DP+Monotonous Queue to solve?

Almost like this problem LINK

Thanks in Advance :)

Read more »

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

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

You'll be given an Array of N elements and Q queries.

Here N and Q is a non-negative integer and maximum value of N and Q is 100000.

There are two types of query.

One is : 1 P V , this means that you have to change P-th element of the array to V.

Another is : 2 L R X , this means that you have to output the number of elements less than or equal to X in L to R range of the array.

How can I solve this problem? I know the solution if there is no update operation. But this problem contains update operation.

Thanks in Advance. :)

Read more »

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

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

How can I find the minimum number of edges need to be added to convert a tree graph to binconnected component such that if we remove an edge from that graph, the graph remain connected? Please give me some idea to do that! Thanks in advance :)

Read more »

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

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

In a bitmask DP problem, there 10 digits. And for every digits I need to store three types of data ( Not used, Used and Using ). One way to solve this is using two bitmask. But for some other reasons It is not possible to use two bitmask in my case. Is there any other memory efficient way to do so? Is there any good resources for learning this?

Read more »

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