Ankur's Blog

let's start Code

1116 - Ekka Dokka

, No comments

1116 - Ekka Dokka

  1. #include<bits/stdc++.h>

  2. using namespace std;

  4. int main()

  5. {

  6.    int t;

  7.     cin >> t;

  8.     for(int cs = 1; cs <= t; cs++){

  9.         long long w;

  10.         cin >> w;

  11.         if(w&1){

  12.             cout << "Case "<< cs<<": Impossible\n";

  13.         }

  14.         else{

  15.             for(long long i = 2; i <= w; i+=2){

  16.                 long long x = w/i;

  17.                 if(x&1 && (x*i) == w){

  18.                     cout << "Case "<<cs<< ": "<<x<<" "<<i<<endl;

  19.                     break;

  20.                 }

  21.             }

  22.         }

  23.     }

  24.     return 0;

  25. }


Share:
Read More

1113 - Discover the Web

, 1 comment

1113 - Discover the Web

Solution:

#include<bits/stdc++.h>

using namespace std;

int main()

{

    int t;

    cin >> t;

    for(int cs = 1; cs <= t; cs++)

    {

        stack<string>f,b,st;

        string s;

        cout << "Case "<<cs<< ":\n";

        st.push("http://www.lightoj.com/");

        while(cin >> s)

        {

            if(s == "VISIT")

            {

                string str;

                cin >> str;

                cout <<str<<endl;

                st.push(str);

                while(!f.empty())f.pop();

            }

            else if(s == "BACK")

            {

               // cout << st.size()<<endl;

                if(st.size() <= 1)

                {

                    cout << "Ignored\n";

                }

                else

                {

                    f.push(st.top());

                    st.pop();

                     cout << st.top()<<endl;

                }

            }

            else if(s == "FORWARD")

            {

                if(f.size() == 0) cout << "Ignored\n";

                else

                {

                    cout << f.top()<<endl;

                    st.push(f.top() );

                    f.pop();

                }

            }

            else break;

        }

    }

    return 0;

}


Share:
Read More

1109 - False Ordering

, No comments

1109 - False Ordering


Solution 01:

#include<bits/stdc++.h>

using namespace std;

void Sieve(int n, bool prime[], bool primesqure[], int a[])

{

    for(int i = 2; i <= n; i++)

        prime[i] = true;

    for(int i = 0; i <= (n*n + 1); i++)

        primesqure[i] = false;

    prime[1] = false;

    for(int p = 2; p*p <= n; p++){

        if(prime[p] == true){

            for(int i = p*2; i <= n; i += p)

                prime[i] = false;

        }

    }

    int j = 0;

    for(int p = 2; p <= n; p++){

        if(prime[p])

        {

            a[j] = p;

            primesqure[p*p] = true;

            j++;

        }

    }

}

int countDivisor(int n)

{

    if(n == 1)return 1;

    bool prime[n+1], primesqure[n*n +1];

    int a[n];

    Sieve(n,prime, primesqure, a);

    int ans = 1;

    for(int i = 0; ; i++){

        if(a[i]*a[i]*a[i] > n)break;

        int cnt = 1;

        while(n % a[i] == 0){

            n = n/a[i];

            cnt = cnt + 1;

        }

        ans = ans * cnt;

    }

    if(prime[n])ans = ans * 2;

    else if(primesqure[n])ans = ans*3;

    else if(n != 1)ans = ans*4;

    return ans;

}

bool cmp (const pair<int, int> &aa, const pair<int, int> &bb)

{

  if(aa.first != bb.first )

    {

        return aa.first < bb.first;

        }

            else     {

        return(aa.second > bb.second);

    }

}

int main()

{

    vector<pair<int, int> >Vp;

    for(int i = 1; i <= 1000; i++){

        int x = countDivisor(i);

        //cout << i << " -------> "<<x<<endl;

        Vp.push_back({x,i});

    }

    sort(Vp.begin(), Vp.end(),cmp);

   // for(auto x: Vp){

       // cout << x.first << " "<< x.second<<endl;

   // }

   int t;

   cin >> t;

   for(int cs = 1; cs <= t; cs++){

        int x;

   cin >> x;

   cout << "Case "<<cs<< ": "<<Vp[x-1].second<<endl;

   }

   return 0;

}


Solution 02:

#include<bits/stdc++.h>

using namespace std;


int countDivisors (int n)

{

    int cnt = 0;

    for(int i = 1; i <= sqrt(n); i++){

        if(n % i == 0){

            if(n/i == i)cnt++;

            else cnt += 2;

        }

    }

    return cnt;

}


bool cmp (const pair<int, int> &aa, const pair<int, int> &bb)

{

  if(aa.first != bb.first )

    {

        return aa.first < bb.first;

        }

            else     {

        return(aa.second > bb.second);

    }

}



int main()

{

    vector<pair<int, int> >Vp;

    for(int i = 1; i <= 1000; i++){

        int x = countDivisors(i);

        //cout << i << " -------> "<<x<<endl;

        Vp.push_back({x,i});

    }

    sort(Vp.begin(), Vp.end(),cmp);

   // for(auto x: Vp){

       // cout << x.first << " "<< x.second<<endl;

   // }

   int t;

   cin >> t;

   for(int cs = 1; cs <= t; cs++){

        int x;

   cin >> x;

   cout << "Case "<<cs<< ": "<<Vp[x-1].second<<endl;

   }

   return 0;

}



Share:
Read More

Compare Function for sorting

, No comments

Compare Function for sorting:

bool cmp (const pair<int, int> &aa, const pair<int, int> &bb)

{

  if(aa.first != bb.first )

    {

        return aa.first < bb.first;

        }

            else     {

        return(aa.second > bb.second);

    }

}

Share:
Read More

Count Divisors

, No comments

Count Divisors

Solution 1:

Complexity: sqrt(n)

#include<bits/stdc++.h>

using namespace std;


int countDivisors (int n)

{

    int cnt = 0;

    for(int i = 1; i <= sqrt(n); i++){

        if(n % i == 0){

            if(n/i == i)cnt++;

            else cnt += 2;

        }

    }

    return cnt;

}


int main()

{

    int n;

    while(cin >> n && n){

        cout << countDivisors(n)<<endl;

    }

    return 0;

}

Solution 2:

Complexity: O(n^1/3)

#include<bits/stdc++.h>
using namespace std;

void Sieve(int n, bool prime[], bool primesqure[], int a[])
{
    for(int i = 2; i <= n; i++)
        prime[i] = true;

    for(int i = 0; i <= (n*n + 1); i++)
        primesqure[i] = false;

    prime[1] = false;
    for(int p = 2; p*p <= n; p++){
        if(prime[p] == true){
            for(int i = p*2; i <= n; i += p)
                prime[i] = false;
        }
    }
    int j = 0;
    for(int p = 2; p <= n; p++){
        if(prime[p])
        {
            a[j] = p;
            primesqure[p*p] = true;
            j++;
        }
    }
}

int countDivisors(int n)
{
    if(n == 1)return 1;

    bool prime[n+1], primesqure[n*n +1];
    int a[n];

    Sieve(n,prime, primesqure, a);

    int ans = 1;
    for(int i = 0; ; i++){
        if(a[i]*a[i]*a[i] > n)break;

        int cnt = 1;
        while(n % a[i] == 0){
            n = n/a[i];
            cnt = cnt + 1;
        }
        ans = ans * cnt;
    }

    if(prime[n])ans = ans * 2;
    else if(primesqure[n])ans = ans*3;
    else if(n != 1)ans = ans*4;
    return ans;
}
int main()
{
    int n;
    while(cin >> n && n){
        cout << countDivisors(n)<<endl;
    }
    return 0;
}

Share:
Read More

778. Swim in Rising Water

, No comments

778. Swim in Rising Water

 

Complexity: O(n^2)

Topic: Flood Fill

Solution:

class Solution {
public:
    using vi = vector<int>;
struct pos
{
  pos(int a, int b, int c) : val(a), x (b), y(c) {}
  bool operator< (const pos &d) const {return val > d.val;}
  int val, x,y;
};

vi nx = {1,-1,0,0};
vi ny = {0, 0, 1, -1};

bool is_valid(int x, int y, int n)
{
  return (x >= 0 && x < n && y >= 0 &&  y < n);
}

int swimInWater (vector<vector<int>>& grid)
{
  int n = grid.size();

  priority_queue<pos>PQ;

  PQ.push(pos(grid[0][0], 0, 0));

  vector<vector<int>> done(n, vi (n, -1));
  done[0][0] = grid[0][0];

  while(done[n-1][n-1] == -1){
    auto p = PQ.top();
    PQ.pop();

    for(int i = 0; i < 4; i++){
      int a = p.x + nx[i];
      int b = p.y + ny[i];

      if(is_valid(a,b,n) && done[a][b] == -1){
        int c = max(grid[a][b], p.val);
        PQ.push(pos(c,a,b));
        done[a][b] = c;
      }
    }
  }
  return done[n-1][n-1];
}
};


Share:
Read More

786. K-th Smallest Prime Fraction

, No comments


786. K-th Smallest Prime Fraction

 Complexity: O(n*log(k))

Solution 1:

 

class Solution {
public:
 struct fraction
{
  double val;
  int i,j;
  fraction(double d, int x, int y) : val(d), i(x), j(y){}
  bool operator< (const fraction& f)const{ return val > f.val;}
};

vector<int> kthSmallestPrimeFraction(vector<int>& A, int k)
{
  priority_queue<fraction>PQ;

  for(int i =0; i < A.size(); i++){
    PQ.push(fraction(static_cast<double> (A[i])/A.back(), i, A.size()-1 ));
  }
  while(k > 1){
    auto top = PQ.top();
    PQ.pop();
    top.j--;
    PQ.push(fraction(static_cast<double> (A[top.i])/A[top.j], top.i, top.j));
      k--;
  }

  return {A[PQ.top().i], A[PQ.top().j]};
}



};

Solution 2:

Compexity: N*C (c <= 31)

class Solution{
public:
  vector<int> kthSmallestPrimeFraction(vector<int>& A, int K)
  {
    const int n = A.size();
    double l = 0;
    double r = 1.0;
    while(l < r) {
      double m = (l + r)/2;
      double max_f = 0.0;
      int total = 0;
      int p, q = 0;
      for (int i = 0, j = 1; i < n - 1; ++i) {
       while (j < n && A[i] > m * A[j]) ++j;
        if(n == j)break;
        total += (n- j);
        const double f = static_cast<double> (A[i]) / A[j];
        if(f > max_f){
          p = i;
          q = j;
          max_f = f;
        }
      }
      if(total == K)return {A[p], A[q]};
      else if(total > K)r = m;
      else l = m;
    }
    return {};
  }
};


Share:
Read More

790. Domino and Tromino Tiling

, No comments


790. Domino and Tromino Tiling

 

Topic: DP

complexity: O(n)

Solution:


 

Code:

class Solution {
public:
    int numTilings(int N) {
        const int MOD = 1e9 + 7;
vector<long> dp = {0, 1, 2, 5};
dp.resize (N+1);

for(int i = 4; i <= N; i++){
  dp[i] = 2*dp[i - 1] + dp[i - 3];
  dp[i] %= MOD;
}
return dp[N];
    }
};

Share:
Read More

795. Number of Subarrays with Bounded Maximum

, No comments


795. Number of Subarrays with Bounded Maximum

 

Complexity: O(n)

Solution 1:

 int numSubarrayBoundedMax(const vector<int>& A, int l, int r)
{
  int result = 0, start = -1, end = -1;

  for(int i = 0; i < A.size(); i++){
    if(A[i] >r)start = i;
    if(A[i] >= l)end = i;
    result += end - start;
  }
  return result;
}


Solution 2:

class Solution {
public:
 enum Valutype{
  RESET,
  NEEDED,
  OK
};

int numSubarrayBoundedMax (const vector<int>& A, int L, int R) {
  int result = 0, start = -1, end = -1;

  for(int i = 0; i < A.size(); i++){
    auto val_type = A[i] > R ? RESET : A[i] >= L ? NEEDED : OK;

    switch(val_type){
      case RESET: start = i;
      case NEEDED: end = i;
      case OK: ///do nothing
      default: result += end - start;
    }
  }
  return result;
}
};


Share:
Read More

802. Find Eventual Safe States

, , , No comments


802. Find Eventual Safe States

 

Solution: DFS

concept:

যেই নোডগুলোতে সাইকেল নাই ওই গুলা প্রিন্ট করতে হবে।

Code:

class Solution {
public:
   
    unordered_set<int> cycle_nodes, safe_nodes;
   
    bool dfs(vector<vector<int>>& g, int i, unordered_set<int>visited_nodes)
    {
        if(safe_nodes.find(i) != safe_nodes.end())return true;
        if(cycle_nodes.find(i) != cycle_nodes.end())return false;
       
        if(visited_nodes.find(i) != visited_nodes.end()){
            cycle_nodes.insert(i);
            return false;
        }
       
        visited_nodes.insert(i);
        for(int node : g[i]){
            if(!dfs(g, node, visited_nodes)){
                cycle_nodes.insert(i);
                return false;
            }
        }
        safe_nodes.insert(i);
        return true;
    }
   
    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        unordered_set<int>visited_nodes;
        vector<int>ans;
       
        for(int i = 0; i < graph.size(); i++){
            if(dfs(graph, i,visited_nodes))ans.push_back(i);
        }
        return ans;
    }
};


Share:
Read More

About

let's start CODE

Popular Posts

  • E-maxx training part - 01
                             Binary Exponentiation 1230 - MODEX              Solution 11029 - Leading and Trailing      Solution I...
  • 11029 - Leading and Trailing
    11029 - Leading and Trailing  Topic: Binary Exponentiation  
  • A - Frog 1
    A - Frog 1 Solution 01: IH19980412 //copy 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 2...