Blog entries - Codeforces

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

art-hack's blog

Generating subsets of size K using bits

By art-hack, 4 years ago, In English

Hi Everyone, I encountered this subproblem in a problem.

Suppose we are given an array of integers of size N and want to generate subsets of size K from it. I used this simple backtracking approach to generate the combinations of size K.

Backtracking Code

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

void generatesubsets(vector<int> choices, int current, int K, vector<int> selected=vector<int>()){

    if(choices.size()-current<K-selected.size())
        return;
    if(selected.size()==K){
        //process subset
        for(auto i:selected)
            cout<<i<<" ";
        cout<<endl;
        return;
    }
    if(current==choices.size())
        return;

    selected.push_back(choices[current]);
    generatesubsets(choices,current+1,K,selected);
    selected.pop_back();
    generatesubsets(choices,current+1,K,selected);

}

int main() {
ios::sync_with_stdio(0);
cin.tie(0);

vector<int> v{1,2,3,4,5,6,7,8,9,10};
generatesubsets(v,0,3);

return 0;
}

I was wondering if there is a possible approach to do this by using bits, a simple approach is generating all subsets and processing only the ones that have size K, but in this, we have to generate all 2^N subsets.

Bits Solution

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

int main() {
ios::sync_with_stdio(0);
cin.tie(0);

vector<int> v{1,2,3,4,5,6,7,8,9,10};
int N = v.size(),K = 3;
for (int b = 0; b < (1<<N); b++) {
    if(__builtin_popcount(b)!=K)
        continue;
    vector<int> subset;
    for (int i = 0; i < N; i++)
        if (b&(1<<i)) subset.push_back(v[i]);
    
    for(auto i:subset)
        cout<<i<<" ";
    cout<<endl;
}


return 0;
}

Is there a way to do this using bits without generating all the possible subsets?.

Full text and comments »

bits, subset

art-hack
4 years ago
15

Range Sum Queries after Updates

By art-hack, history, 4 years ago, In English

Hey Everyone, I am trying to solve a problem and got stuck at this subproblem.

Problem

You are given an initial array a with N elements.

There are a series of update operations, Let's say there are K operation, such that in each operation a_i is replaced with x_i.

Now there are Q range sum queries, and in each query, you're given L, R, and P.

You have to find the sum of range in [L, R] after the p^th update has occurred.

Constraints

N<=2*10⁵
a_i <= 10⁹
K <= 10⁵
Q <= 10⁵
L,R <= N

The solution should preferably be with preprocessing and not be with offline queries.

Example

Initial array [1, 2, 3, 4, 5]
Updates (K=3):
(Index ReplacedValue)
0 5
1 4
2 4
Queries(Q=3)
0 4 1
1 3 2
1 4 0

Answer:
21 (5+4+3+4+5)
11 (4+4+3)
14 (2+3+4+5)

Full text and comments »

#range query

art-hack
4 years ago
10

Codeforces Hacking Assistant

By art-hack, history, 5 years ago, In English

Hello Everyone,

I have created a handy tool for running two codes against an input or stress testing them against random inputs. This can be helpful in hacking some simple problems and get possible faults, and also in finding wrong test cases for your solutions.

Link to Github Repo: Link

Video Showing its working

I know this isn't perfect so if you feel that I can improve something or add some feature then do let me know and feel free to contribute as well.

Full text and comments »

#hack, testing, help

art-hack
5 years ago
11

Matrix Exponentiation Optimization

By art-hack, history, 5 years ago, In English

Hey Everyone, So I saw this problem in one of the contests on Codechef(link)

Problem Statement

You are given two integers N and M. Find the number of sequences A1, A2,…,AN, where each element is an integer between 1 and M (inclusive) and no three consecutive elements are equal. Since this number could be very large, compute it modulo 109+7.

So I used my general code for Matrix Exponentiation but got a TLE.

My submission

/* Code by
               __            __                       __         
              /\ \__        /\ \                     /\ \        
   __     _ __\ \ ,_\       \ \ \___      __      ___\ \ \/'\    
 /'__`\  /\`'__\ \ \/        \ \  _ `\  /'__`\   /'___\ \ , <    
/\ \L\.\_\ \ \/ \ \ \_        \ \ \ \ \/\ \L\.\_/\ \__/\ \ \`\  
\ \__/.\_\ \_\  \ \__\        \ \_\ \_\ \__/.\_\ \____\ \_\ \_\
 \/__/\/_/ \/_/   \/__/  _______\/_/\/_/\/__/\/_/\/____/ \/_/\/_/
                        /\______\                                
                        \/______/                                
*/

#include "bits/stdc++.h"
using namespace std;
#define max(a, b) (a < b? b : a)
#define min(a, b) ((a>b)?b:a)
#define mod 1e9+7
#define FOR(a,c)   for ( int (a)=0; (a)<(c); (a)++)
#define FORL(a,b,c)  for ( int (a)=(b); (a)<=(c); (a)++)
#define FORR(a,b,c)  for (  int (a)=(b); (a)>=(c); (a)--)
#define INF 1000000000000000003
typedef long long int ll;
typedef vector<int> vi;
typedef pair<int,int> pi;
#define F first
#define S second
#define PB push_back
#define POB pop_back
#define MP make_pair

#define MOD 1000000007
ll k=2;
vector<ll> b; // b is base case

vector<vector<ll> > multiply(vector<vector<ll> > A,vector<vector<ll> > B ){

    vector<vector<ll> > C(k,vector<ll>(k,0));
    FOR(i,k)
        FOR(j,k)
            FOR(x,k)
                C[i][j] = ((C[i][j]%MOD) + ((A[i][x]%MOD)*(B[x][j]%MOD))%MOD)%MOD;

    return C;
}

vector<vector<ll> >  pow(vector<vector<ll> > A,ll p){
    if(p==1)
        return A;
    if(p%2==1)
        return multiply(A, pow(A,p-1));
    else{
        vector<vector<ll> > X = pow(A,p/2);
        return multiply(X,X);
    }
}


ll compute(ll n,ll m){
    //Suppose n<=k
    if(n<=k){
        return b[k-n];
    }

    //2. Transformation matrix
    vector<vector<ll> > T{
        {(m-1),(m-1)},
        {1,0}
    };

    // 3. T^n-k
    T = pow(T,n-k);

    // 4. multiply by initial vector
    ll res = 0;
    FOR(i,k)
        res = (res%MOD + ((T[0][i]%MOD)*(b[i]%MOD))%MOD)%MOD;
    return res;  
}


int main() {
ios::sync_with_stdio(0);
cin.tie(0);

int T;
cin>>T;
while(T--){
    ll N,M;
    cin>>N>>M;
    if(M==1 && N>1)
        cout<<0<<endl;
    else if(M==1 && N==1)
        cout<<1<<endl;
    else{
        b.PB((((M%MOD)*(M%MOD))%MOD));
        b.PB((M%MOD));
        cout<<compute(N,M)<<endl;
        b.clear();
    }
}

return 0;
}

People have used matrix exponentiation for the same and got a full score.

Selected submission

#include <iostream>

using namespace std;
using ll = long long;
#define N 1000000007
void mul(ll F[2][2], ll M[2][2]) 
{ 
  ll x =  (F[0][0]*M[0][0] + F[0][1]*M[1][0])%N; 
  ll y =  (F[0][0]*M[0][1] + F[0][1]*M[1][1])%N; 
  ll z =  (F[1][0]*M[0][0] + F[1][1]*M[1][0])%N; 
  ll w =  (F[1][0]*M[0][1] + F[1][1]*M[1][1])%N; 
  
  F[0][0] = x; 
  F[0][1] = y; 
  F[1][0] = z; 
  F[1][1] = w; 
} 
ll matmul(ll mat[2][2], ll n, ll m)
{
    ll ans[2][2];
    ans[0][0] = 1;
    ans[0][1] = 0;
    ans[1][0] = 0;
    ans[1][1] = 1;
    while(n > 0)
    {
        if(n%2 == 1)
            mul(ans, mat);
        n = n/2;
        mul(mat, mat);
    }
    ll x = (m*m)%N;
    return (ans[0][0]*x + ans[0][1]*m)%N;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--)
    {
        ll n, m;
        cin >> n >> m;
        m = m%N;
        ll mat[2][2];
        mat[0][0] = m-1;
        mat[0][1] = m-1;
        mat[1][0] = 1;
        mat[1][1] = 0;
        if(n == 1)
            cout << m << '\n';
        else if(n == 2)
            cout << (m*m)%N << '\n';
        else
            cout << (matmul(mat, n-2, m)+N)%N << '\n';
    }
}

Things that I have tried already are

Switching ll with int
Reserving the size of the vector already.

Please tell me what I can optimize more in my code so that we do not face this problem in any of the Matrix Exponentiation problems?

Full text and comments »

#help, #matrix exponentialtion, complexity optimization

art-hack
5 years ago
11

Modified Knapsack Problem

By art-hack, history, 5 years ago, In English

I created a problem, but I couldn't solve it and need some help.

Problem You have N blocks with an array a in which a[i] represents the weight of ith item. You are also given the maximum weight that the knapsack can handle as W.

You have to find the maximum possible weight that you can achieve by filling these blocks in the knapsack.

Now the different part is that you can either take any block as whole or you can split it into two blocks(only once) such that atleast one of the two block has weight between [80,100%) and you can take either of the blocks into the knapsack.

Sample Input
2
200 100
285

Sample Output
285

Sample Input
2
200 100
230
Sample Output
220

Explaination: In the first sample input we take the first block as whole and the second partially with one piece of 85 and one of 15 and take the one with weight 85 to achieve the total of 285.

In the second sample input we take the first block as whole and the second partially with one piece of 80 and one of 20 and take the one with weight 20 to achieve the total of 220.

I wanted to know if it is solvable or not.

If possible can we extend this question with another given array v representing the values of the blocks and we want to achieve the maximum possible value by putting blocks in the knapsack. Note: when we split a block its value gets split in the same ratio as it's weight.

Full text and comments »

#dynamic programing, #range query, #help

art-hack
5 years ago
7