iamskp's blog

By iamskp, history, 5 weeks ago, In English

I was solving this problem from SPOJ : https://www.spoj.com/problems/HAYBALE/

I was able to solve this problem with arrays but there exists a solution with bitmasks.

My solution (Python): https://ideone.com/0exgTg

Can someone please tell me how can I solve this problem with the help of bitmasks.

Read more »

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

By iamskp, history, 7 months ago, In English

I was doing a problem in which we have to find kth smallest element using constant space and the array is read only. The array can be unsorted.

Link to the problem : https://www.interviewbit.com/problems/kth-smallest-element-in-the-array/

I want to know how the binary search solution works here.

Here is a working code I found:

int Solution::kthsmallest(const vector<int> &A, int B)
{
    int maximum = 0;
    for(int a : A) maximum = max(maximum, a);
    int low = 0, high = maximum;
    while(low != high)
    {
        int mid = (low + high + 1)/2;
        int count = 0;
        for(int a : A)
        {
            if(a < mid) count++;
        }
        if(count < B) low = mid;
        else high = mid - 1;
    }
    return low;
}

Read more »

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

By iamskp, history, 8 months ago, In English

Given an array, find out the longest increasing subsequence which is lexicographically smallest.

For example:

Given array : [9,2,10,3,11,4]

Possible LIS: [2,10,11],[2,3,4],[9,10,11],[2,3,11]

Lexicographically smallest LIS [2,3,4].

Read more »

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

By iamskp, history, 10 months ago, In English

I was doing this problem from Atcoder : https://atcoder.jp/contests/abc128/tasks/abc128_c

Can someone please explain the solution?

I have seen the editorial but couldn’t understand it.

Solution link: https://atcoder.jp/contests/abc128/submissions/15518338 (Python)

Solution link: https://atcoder.jp/contests/abc128/submissions/5640467 (C++)

Read more »

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

By iamskp, history, 10 months ago, In English

I am doing this problem. Can someone please tell me why i am getting tle verdict. My submission is in python. My submission : https://codeforces.com/contest/1283/submission/88064624

Read more »

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