siddhi's blog

By siddhi, history, 2 months ago, In English,

Can some explain how to go about this question.

https://www.codechef.com/OCT19A/problems/JIIT

I tried something like this :

Rather than applying Q operations row-column, I considered performing Q operations on rows and columns independently. What I needed to calculate was Dp[Q] vector ith index would denote the number of permutations of Q length with exactly i elements with odd frequencies.

I came up with this recurrence:

DP( n, i) = i*DP( n-1, i-1) + (N-i)*DP( n-1, i+1)

But failed in this approach because I could not do that within Time Limit with Matrix Exponentation.

Read more »

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

By siddhi, history, 3 months ago, In English,

Link https://www.codechef.com/ALCM2019/problems/ALC006 Best I was able to do was Mo's algorithm + heap of frequency of elements. I wasn' t able to optimize better than this.

Read more »

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

By siddhi, history, 4 months ago, In English,

You are given a graph with some of its edges are directed and some are un-directed. You have to return true/false depending upon if you can convert all the undirected edges in directed ones such that there is no cycle in graph return true else return false..

Can some please some help on how to approach this problem?

Thanks in advance :)

Read more »

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

By siddhi, history, 8 months ago, In English,

A sequence is interesting if the greatest common divisor of all the elements from the sequence is greater than 1. Each query can be of two types: 1. Change the value at position X in the sequence to V. 2. Determine the number of interesting contiguous subarrays contained in the interval [L, R] sequence. The first line of input contains the numbers N and Q (1 <= N, Q <= 100000), representing the number of elements in the sequence and number of queries, respectively. The following line contains N natural numbers, A[i] (1 <= A[i] <= 1000000000) that represent the numbers in the initial sequence. Each of the following Q queries contains a query in the following form: 1. The first number in line can be 1 or 2 denoting the type of query. 2. If the query is of type 1, two numbers follow, X (1 <= X <= N) and V (1 <= V <= 1000000000). 3. If the query is of type 2, two numbers follow, L and R (1 <= L, R <= N), that represents the left and right interval boundary.

Read more »

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