gagannagpal68's blog

By gagannagpal68, history, 8 months ago, In English

Problem statement: You are a given a string s , int x and int y; S consists of three characters '0', '1', and '?' You can replace '?' with either '0' or '1'. You need to minimize the following equation:

Equation is a*x + b*y. 

Here a is the number of "01" subsequences and b is number of "10" subsequences after the replacement of all '?'

Constraints

Constraints
Testcase:
Possible approaches

I was thinking in direction of DP and making it run in nlogn and some sort of convex hull emerges in my head but I don't have enough practice to make it work. Any idea folks?

Full text and comments »

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

By gagannagpal68, history, 3 years ago, In English

Given a string s and a number k. You need to tell count of distinct string of length k. s.t. k is a subset of s.

Eg 1. "aaabb" 2 => 4 (aa bb ab ba)

  1. "aabbcc" 2 => 9( aa ab ac ba bb bc ca cb cc)

  2. "abbcc" 2 => 8( same as #2 but aa can't be formed

I can create a dp of state index and mask where mask is of base 26 and rest is straightforward. Please help me in finding some combinatorics approach of solving it.

Full text and comments »

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

By gagannagpal68, history, 5 years ago, In English

My hash has 3 fields

f1 = size of interval

f2 = sum of array elements over interval(a[i] +a[i+1]...a[j])

f2 = sum of squares of array elements over interval(a[i]^2 + a[i+1]^2 .. a[j]^2).

if all 3 matches, then elements are indeed same. Can this be broken?

P.S. While in attempt to solve D from previous contest(https://codeforces.net/contest/1284/problem/D). I was looking for this question.

Full text and comments »

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

By gagannagpal68, history, 5 years ago, In English

I was solving this problem(https://codeforces.net/contest/1197/problem/D) from a recent contest. Eventually, I came up with Dp. But in the process of solving, I proved if I can answer below problem then I can easily use that to solve the original problem.

Problem: Given an array of integers, We need to print an array sz[] of length n. sz[i] should print the value of maximum sum of i-length subarray.

Example n = 3 given array: 4 -2 5

ans: 5 3 7

Can we solve the problem in O(nlogn) ?

Full text and comments »

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