bablu_45's blog

By bablu_45, history, 5 years ago, In English

We are given an array of size 'N' with 'Q' queries. Each query contains 3 integers (A,B and C) which divides the entire array into 4 parts or subarrays, [0,A-1],[A,B],[B+1,C] and [C+1,N-1]. We need to swap first and second subarray and third and fourth subarray.

You need to output the final array after Q queries.

Constraints:

1<=N<=10^5

1<=Q<=10^5

1<=A[i]<=10^9.

Eg:- N=9 with 2 queries

9 2

1 2 3 4 5 6 7 8 9

2 4 6

1 3 5

In first query we are supposed to swap [0,1] and [2,4], [5,6] and [7,8]. So after first query array becomes [3,4,5,1,2,8,9,6,7]

In second query we are supposed to swap [0,0] and [1,3], [4,5] and [6,8] of modified array. So final array is [4,5,1,3,9,6,7,2,8]

How to solve this question?

Full text and comments »

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

By bablu_45, history, 5 years ago, In English

Given a string 's', we can perform the following operation:-

1) Choose an index 'i' greater than the index chosen in previous operation and rotate the suffix(left or right rotate) formed from i, any number of times.

What is the minimum number of operations required to make smallest possible lexicographical string from s?

Size of input:- length of string<=10^3

Example:-

1) s:- acab

Choose suffix from index 1 and right rotate the string "cab" 2 times to the right to obtain "aabc" which is the smallest possible lexicographical string.

So the minimum number of operations required is 1.

2) s:- cdax

First, choose suffix from index 0 and rotate the string "cdax" two times to the right to get "axcd".

Now choose suffix from index 1 and rotate the string "xcd" 1 time to the left to obtain "cdx". Final string is "acdx".

So minimum number of operations required is 2.

Note:- In a single operation you can perform any number of left or right rotations on a suffix.

Full text and comments »

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

By bablu_45, history, 5 years ago, In English

I am just curious about the correlation between chess and CP . It would be great if you could share your chess rating (FIDE or chess.com) rating. Have you guys ever met someone who has high rating in chess (around 2000-2200) and also on CF(around 2400)?

Full text and comments »

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

By bablu_45, history, 5 years ago, In English

Normal palindrome is defined as a string that reads the same backwards as forwards, for example "abccba". Chunked palindrome is defined as a string that you can split into chunks and it will form a palindrome. For example, "volvo". You can split it into (vo)(l)(vo). Let A = "vo", B = "l", so the original string is ABA which is a palindrome.

Given a string str, find the maximum number of chunks we can split that string to get a chuncked palindrome.

For eg

:- "aaaaaa", output is 6 ((a)(a)(a)(a)(a)(a))

:- "volvol" output is 2 ((vol)(vol))

Length of string <=2*(10^4)

I can think of a greedy way to solve this problem but not able to prove if it's optimal.

Full text and comments »

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

By bablu_45, history, 5 years ago, In English

Given an array of roses. roses[i] means rose i will bloom on day roses[i]. Also given an int k, which is the minimum number of adjacent bloom roses required for a bouquet, and an int n, which is the number of bouquets we need. Return the earliest day that we can get n bouquets of roses.

Example: Input: roses = [1, 2, 4, 9, 3, 4, 1], k = 2, n = 2

Output: 4

Explanation:

day 1: [b, n, n, n, n, n, b]. The first and the last rose bloom.

day 2: [b, b, n, n, n, n, b]. The second rose blooms. Here the first two bloom roses make a bouquet.

day 3: [b, b, n, n, b, n, b]

day 4: [b, b, b, n, b, b, b]

Here the last three bloom roses make a bouquet, meeting the required n = 2 bouquets of bloom roses. So return day 4.

I am looking for a efficient D.P solution (if possible).

Full text and comments »

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

By bablu_45, history, 5 years ago, In English

Given a 1-d array candy crush, return the shortest array after removing all the continuous same numbers (the no of occurences of repeating number >= 3)

input: 1-d array [1, 3, 3, 3, 2, 2, 2, 3, 1]

return: [1, 1] (Explanation:- 133322231->133331->11).

133322231->122231->131 gives answer as [131] which is not the shortest.

Time complexity should be better than O(n^2)

Full text and comments »

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

By bablu_45, history, 5 years ago, In English
  • Vote: I like it
  • -19
  • Vote: I do not like it