ProveMeRight's blog

By ProveMeRight, 8 months ago, In English

When I am trying to register for the upcoming Div 2 round,

CF Be like:

Message

I wonder if the registration rules have been changed or if It's a bug or If it's only for this round.

Full text and comments »

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

By ProveMeRight, history, 11 months ago, In English

According to the solution, I need to calculate n! — (n!/(k+1).

I tried two ideas to calculate this but still got the wrong answer on Test 2

216215234 for the idea:

val = (fact[n] * inv(cnt+1))%mod

cout << fact[n] - val << endl;

216404434

int val = fact[n]/(cnt+1);

cout << fact[n] - val << endl;

Please help, as I'm stuck on this since yesterday.

void solve() {
  int n;
  cin >> n;
  vi v(n);
  rep(i, 0, n) cin >> v[i];
  sort(all(v));
  if (v[n - 1] == v[n - 2])
  {
    cout << fact[n] << endl;
    return;
  }
  int cnt = count(all(v),v[n-1]-1);
  int val = (fact[n] * inv(cnt+1))%mod
  cout << fact[n] - val << endl;
}

Note: In my template, I defined int as a long long, and pre-computed fact array.

Full text and comments »

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

By ProveMeRight, history, 12 months ago, In English

209248600

...
int a = x;
int b = 0;

for(int i= 29;i>=0;i--)
    {
        if((x & (1 << i)) > 0)
        {
            continue;
        }

        if((2*x - a - b) >= (2 << i))
        {
            // bug(a,b);
            a += (1 << i);
            b += (1 << i);
        }
    }

When I am making the start from i= 30 or more, it makes a negative. Why?

Note: I defined int as long long. Still, It's doing the same.

Can anyone please explain?

Full text and comments »

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

By ProveMeRight, history, 13 months ago, In English

Hey Guys, I don't know why But my Codeforces pages like Home, Submit and sometimes even the contest page is loading very slowly.

I have been facing this issue for the last 4-5 days.

I checked my internet connection but other sites are loading quite fast except codeforces. I tried it on my Android phone too, there also I'm facing the same issue.

Is this happening to me only?

MikeMirzayanov

Full text and comments »

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

By ProveMeRight, history, 14 months ago, In English

let's suppose the case:

k = 1, n = 1000;

arr[] = {1,3,5,7,9,11,..........1999]

For this case, the answer can be 2^N, and according to the question we have to return an integer. Is it possible?

Please help someone.

Thank you.

Full text and comments »

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

By ProveMeRight, history, 15 months ago, In English

I was solving the CSES Dynamic Programming Problem named Coin Combinations I. I don't know what's the matter here.

In my view, Both the commented code, as well as uncommented code, is the same. But The uncommented code is throwing TLE and the Commented Code is passing all the test cases.

This is the code

vi dp(1000001, 0);
vi v(1000001, 0);
void solve() {
  int n, x;
  cin >> n >> x;
  FOR(i, 0, n) cin >> v[i];



  // for(int i =0;i<=x;i++)
  //   {
  //       // base case
  //       if(i==0)
  //       {
  //           dp[i] = 1;
  //       }
  //       else
  //       {   dp[i] = 0;
  //           for(int j = 0;j<n;j++)
  //           {
  //               if(i-v[j]>=0)
  //               dp[i] += dp[i-v[j]];
  //           }
  //           dp[i] %= mod;
  //       }
  //   }

  for(int i =0;i<=x;i++)
  {
    if (i == 0)
    {
      dp[i] = 1;
    }
    else
    {
      dp[i] = 0;
      for(int j = 0;j<n;j++)
      {
        if (i - v[j] >= 0)
        {
          dp[i] += dp[i - v[j]];
        }
        dp[i] %= mod;
      }
    }
  }

  cout << dp[x] << endl;
}

Please Help Me. Thank you.

Full text and comments »

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

By ProveMeRight, history, 15 months ago, In English

196344788

Please check for this.

/*
                    ------ Ackerman ------
     A single soldier might pose a threat to me?
     Yes! Captain Levi is Dangerous.   
*/

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

using namespace std;

#define int            long long int
#define F              first
#define S              second
#define pb             push_back
#define si             set <int>
#define vi             vector <int>
#define pii            pair <int, int>
#define vpi            vector <pii>
#define vpp            vector <pair<int, pii>>
#define mii            map <int, int>
#define mpi            map <pii, int>
#define spi            set <pii>
#define endl           "\n"
#define sz(x)          ((int) x.size())
#define all(p)         p.begin(), p.end()
#define double         long double
#define que_max        priority_queue <int>
#define que_min        priority_queue <int, vi, greater<int>>
#define bug(...)       __f (#__VA_ARGS__, __VA_ARGS__)
#define print(a)       for(auto x : a) cout << x << " "; cout << endl
#define print1(a)      for(auto x : a) cout << x.F << " " << x.S << endl
#define print2(a,x,y)  for(int i = x; i < y; i++) cout<< a[i]<< " "; cout << endl
#define FOR(i,a,b)     for (int i = a; i < b; i++)

//---------- MOD Operations (Unleash the Beast Mode) -----------------------


int mod = 1e9 + 7;

inline void add(int &a, int b) {
  a += b;
  if (a >= mod) a -= mod;
}

inline void sub(int &a, int b) {
  a -= b;
  if (a < 0) a += mod;
}

inline int mul(int a, int b) {
  return (int) ((long long) a * b % mod);
}

inline int powerM(int a, long long b) {
  int res = 1;
  while (b > 0) {
    if (b & 1) {
      res = mul(res, a);
    }
    a = mul(a, a);
    b >>= 1;
  }
  return res;
}

inline int inv(int a) {
  a %= mod;
  if (a < 0) a += mod;
  int b = mod, u = 0, v = 1;
  while (a) {
    int t = b / a;
    b -= t * a; swap(a, b);
    u -= t * v; swap(u, v);
  }
  assert(b == 1);
  if (u < 0) u += mod;
  return u;
}

//-------------------------------------------------------------


inline int power(int a, int b)
{
  int x = 1;
  while (b)
  {
    if (b & 1) x *= a;
    a *= a;
    b >>= 1;
  }
  return x;
}


// O(logN) -> __gcd(a,b);


// int gcd(int a,int b)
// {
//   if(b==0) return a;
//   return gcd(b,a%b);
// }


// negative mod
inline int Nmode(int x,int m)
{
   x = x%m;
    if (x < 0) x += m;
    return x;
}

template <typename Arg1>
void __f (const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << endl; }
template <typename Arg1, typename... Args>
void __f (const char* names, Arg1&& arg1, Args&&... args)
{
  const char* comma = strchr (names + 1, ',');
  cout.write (names, comma - names) << " : " << arg1 << " | "; __f (comma + 1, args...);
}

// const int N = 200005;

/* void sieve()
{
  is_prime[0]=is_prime[1] = true;
  for(int i=2;i<=N;i++)
  {
    if(is_prime[i]==false && i*i<=N)
    {
      for(int j = i*i;j<=N;j+=i)
      {
        is_prime[j]= true;
      }
    }
  }
}
*/

void solve() {
    int n;
    cin >> n;
    vi v(n);
    FOR(i,0,n) cin >> v[i];

    if(n==1)
    {
        cout << "YES" << endl;
        cout << 1 << endl;
        cout << 1 << endl;
        return;
    }

    set<int>s1,s2;

    FOR(i,1,n+1)
    {
        s1.insert(i);
        s2.insert(i);
    }

    vector<int>p(n,0),q(n,0);
    FOR(i,0,n)
    {
        int val = v[i];

        if(s1.find(val)!=s1.end())
        {
            p[i] = val;
            s1.erase(s1.find(val));
        }
        else if(s2.find(val)!=s2.end())
        {
            q[i] = val;
            s2.erase(s2.find(val));
        }
        else
        {
            cout << "NO" << endl;
            return;
        }
    }


    FOR(i,0,n)
    {
        if(p[i]==0)
        {
            auto it = upper_bound(s1.begin(),s1.end(),q[i]);
            if(it==s1.begin())
            {
                cout << "NO" << endl;
                return;
            }
            it--;

            p[i] = *it;
            s1.erase(it);
        }
    }

    FOR(i,0,n)
    {
        if(q[i]==0)
        {
            auto it = upper_bound(s2.begin(),s2.end(),p[i]);
            if(it==s2.begin())
            {
                cout << "NO" << endl;
                return;
            }
            it--;

            q[i] = *it;
            s2.erase(it);
        }
    }

    cout << "YES" << endl;
    print(p);
    print(q);
}

int32_t main()
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

// #ifndef ONLINE_JUDGE
//   freopen("input.txt",  "r",  stdin);
//   freopen("output.txt", "w", stdout);
// #endif

  clock_t z = clock();

  int t = 1;
  cin >> t;
  while (t--) solve();

  cerr << "Run Time : " << ((double)(clock() - z) / CLOCKS_PER_SEC);

  return 0;
}

Full text and comments »

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

By ProveMeRight, history, 16 months ago, In English

It's showing open for registration for Feb 16, 23 — Mar 08, 23

But the date of the contest shown is Feb 22, 23.

What is the catch here?

https://icpc.global/regionals/upcoming!

Also, I am Indian so can I fill out the registrations for Other Asia Regions too? Except for the Asia West. And How many times ICPC occurs in Regions in a year?

Also suggest me some good blog link, which clears all doubts related to ICPC.

Full text and comments »

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