### om1429888's blog

By om1429888, history, 5 weeks ago,

Given a polynomial p(x) If degree is A.P(1)=P(2)=P(3).....=P(A)=1. Also P(A+1)=B Tell P(A+C).

• 0

By om1429888, history, 5 weeks ago,

You are given an array A and integer B.divide array into B subarray such that each element belon to 1 subarray.goodness is defined as sum of the goodness of all its subarray where the g99dness of subarray is defined as bitwize or of all elemnts in each subarray.u have to maximize the goodness.

• 0

By om1429888, history, 5 weeks ago,

https://codeforces.com/contest/456/problem/B

so i fugured out that i have to do mod 4 in the power,(having studies number theory alot) but sadly could not figure out how to deal with strings,i have to take input as string obviously right? then how to do mod?

• 0

By om1429888, history, 6 weeks ago,

((3 * ‘N’ ) ! / ( 3! ^ ‘N’ ) )% ‘P

I HAVE TO SOLVE THIS. THE PROBLEM IS IF N=4; AND P=7 MY NUMERATOR BECOMES 0 AND THIS WILL GIVE ME WRONG ANSWER. THE ANSWER IS 6 BUT MY CODE IS GIVING 1.

THIS IS HOW IM DOING IT. IM ITERATING FROM 1 TO 3*N CALCULATING (3*N)FACTORIAL. CALCULATE THE DENOMINATOR, DO MOD INVERSE AND MULTIPLY. ANY SUGGESTIONS HOW CAN I DEAL WITH THIS.

#include <bits/stdc++.h>
#define ll long long
ll factorial(ll n,ll p){
ll res=1;
for(ll i=1;i<=n;i++){
res=((res%p)*(i%p))%p;
}
return res;
}
ll power(ll num,ll d,ll p){
ll res=1;
while(d){
if(d&1){
res=((res%p)*(num%p))%p;
d--;
}
d/=2;
num=((num%p)*(num%p))%p;
}
return res;
}
ll mul(ll a,ll b,ll p){
ll res=0;
a%=p;
while(b){
if(b&1){
res=((res%p)+(a%p))%p;
b--;
}
b/=2;
a=(2*(a%p))%p;
}
return res;
}
long long int factorialAgain(long long int n,long long int p)
{
if(p==1)return 0;
ll temp=3*n;
ll numerator=factorial(temp,p);
n%=(p-1);
ll den=power(6,n,p);
ll inverse=power(den,p-2,p);
ll ans=mul(inverse,numerator,p);
return ans;
}


• -25

By om1429888, history, 6 weeks ago,

Hi guys. We all know that matrix exponentiation can be used to find Nth term of a recurrent relation in logN time, this is generally used to find Nth fibonacci in logN time where N can be as large as 1e18(obviously it is modulo something), now fibonacci is represented as f(n-1)+f(n-2),but what is relation isnt linear, it can be for example, f(n-1)+f(n-2)+f(n-1)*f(fn-2). i tried and could'nt find a solution, so any suggestions>

• +16

By om1429888, history, 7 weeks ago,

for the first test case im getting 7/16 but it should be 7/8 basically im doing summation of 1/n*1/k*1/n*fre(y)/n. https://codeforces.com/contest/1279/problem/D

• 0

By om1429888, history, 2 months ago,

• 0

By om1429888, history, 2 months ago,

https://codeforces.com/gym/102644/problem/A

for this problem i thought of the recurrence relation and then applied matrix exponentitation, my relation was (1-p)*f(n-1)+p*p*f(n-2);

why is this relation wrong?

• 0

By om1429888, history, 2 months ago,

Vova again tries to play some computer card game. The rules of deck creation in this game are simple. Vova is given an existing deck of n cards and a magic number k. The order of the cards in the deck is fixed. Each card has a number written on it; number ai is written on the i-th card in the deck. After receiving the deck and the magic number, Vova removes x (possibly x = 0) cards from the top of the deck, y (possibly y = 0) cards from the bottom of the deck, and the rest of the deck is his new deck (Vova has to leave at least one card in the deck after removing cards). So Vova's new deck actually contains cards x + 1, x + 2, ... n - y - 1, n - y from the original deck. Vova's new deck is considered valid iff the product of all numbers written on the cards in his new deck is divisible by k. So Vova received a deck (possibly not a valid one) and a number k, and now he wonders, how many ways are there to choose x and y so the deck he will get after removing x cards from the top and y cards from the bottom is valid?

The first line contains two integers n and k (1 ≤ n ≤ 100 000, 1 ≤ k ≤ 10^9).

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 10^9) — the numbers written on the cards. input 3 4 6 2 8 output 4

• 0

By om1429888, history, 2 months ago,

• 0

By om1429888, history, 2 months ago,

i have been trying alot but cant comeup with a solution,i thought using segmented sieve but it gives tle. https://www.spoj.com/problems/BSPRIME/

BSPRIME — Binary Sequence of Prime Number no tags Binary Sequence of Prime Number is a binary sequence that created by converting prime number to base-2 (Without leading zeros):

(2)10=(10)2 (3)10=(11)2 (5)10=(101)2 (7)10=(111)2 ...

If all base-2 of prime number joined, then we get the binary sequence like this: 10111011111011110110...

Now your task is to count how many digit '1' appear in the first N terms of the sequence, example:

-->If N=3, digit '1' appear 2 times: 101110... -->If N=10, digit '1' appear 8 times: 1011101111101...

Input The first line is an integer T(1 ≤ T ≤ 50,000), denoting the number of test cases. Then, T test cases follow.

For each test case, there is an integer N(0 ≤ N ≤ 150,000,000) written in one line.

Output For each test case, output the number of digit '1' appear in the first N terms of the sequence

Example Input: 3 3 10 50

Output: 2 8 36

• +5

By om1429888, history, 2 months ago,

https://www.spoj.com/problems/BTCK/

#include<iostream>
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define pb push_back
#define fast_io ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fr(i,a,b) for(int i=a;i<b;i++)
#define loop(x,n) for(int x=0;x<n;x++)
#define mod 1e7
#define inf (1LL<<60)
#define all(x) (x).begin(),(x).end()
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
void precal(){
}
vector<int>perm={0,1,2,3,4,5,6,7,8,9};
vector<ll>input(10);
bool helper(ll k,ll index,ll sum){
if(sum>k)return false;
if(index==10){
fr(i,0,10){
cout<<perm[i]<<" ";
}
cout<<endl;
return true;
}
for(int i=index;i<10;i++){
swap(perm[index],perm[i]);
bool check=helper(k,index+1,sum+input[index]*perm[index]);
if(check){
swap(perm[index],perm[i]);
return true;
}
swap(perm[index],perm[i]);
}
return false;
}
void solve(){
fr(i,0,10)cin>>input[i];
ll k;
cin>>k;
bool check=helper(k,0,0);
if(!check){
cout<<-1<<endl;
}
}
int main()
{
fast_io;
cout<<fixed;
cout<<setprecision(10);
precal();
int t=1;cin>>t;
for(int i=1;i<=t;i++)
{
//cout<<Case #<<i<<: ;
solve();
}
return 0;
}


• +1

By om1429888, history, 3 months ago,
#include<iostream>
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define pb push_back
#define fast_io ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fr(i,a,b) for(int i=a;i<b;i++)
#define loop(x,n) for(int x=0;x<n;x++)
#define mod 1e7
#define inf (1LL<<60)
#define all(x) (x).begin(),(x).end()
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
void precal(){
}
ll helper(vector<ll>v1,vector<ll>v2,vector<pair<ll,ll>>&output){
for(int i=0;i<v1.size();i++){
int cur=i;
for(int j=i+1;j<v1.size();j++){
if(v1[j]<v1[cur])cur=j;
}
if(cur!=i){
swap(v1[cur],v1[i]);
swap(v2[cur],v2[i]);
output.push_back({i,cur});
}
}
for(int i=1;i<v1.size();i++){
if(v2[i-1]>v2[i]){
return -1;
}
}
return  output.size();
}
void solve(){
ll n;cin>>n;
vector<ll>v1(n);
vector<ll>v2(n);
fr(i,0,n)cin>>v1[i];
fr(i,0,n)cin>>v2[i];

vector<pair<ll,ll>>output1;
vector<pair<ll,ll>>output2;
ll x=helper(v1,v2,output1);
ll y=helper(v2,v1,output2);

if(x==-1&&y==-1){
cout<<-1<<endl;
return;
}
if(x!=-1){
cout<<x<<endl;
for(int i=0;i<output1.size();i++){
cout<<output1[i].first+1<<" "<<output1[i].second+1;
cout<<endl;
}
}
else{
cout<<y<<endl;
for(int i=0;i<output2.size();i++){
cout<<output2[i].first+1<<" "<<output2[i].second+1;
cout<<endl;
}
}
}
int main()
{
fast_io;
cout<<fixed;
cout<<setprecision(10);
precal();
int t=1;cin>>t;
for(int i=1;i<=t;i++)
{
//cout<<Case #<<i<<: ;
solve();
}
return 0;
}


• -24

By om1429888, history, 3 months ago,

https://leetcode.com/problems/ways-to-split-array-into-three-subarrays/

THIS IS THE QUESTION.

THIS IS MY SOLUTION.

class Solution {
public:
long long mod=1000000000+7;
int waysToSplit(vector<int>& nums) {
vector<long long>v(nums.size(),0);
v[0]=nums[0];
for(int i=1;i<nums.size();i++){
v[i]=v[i-1]+nums[i];
}
int j=0;
long long count=0;
for(int i=0;i<nums.size()-2;i++){
if(j==i)j++;
while(j<nums.size()-1&&v[i]>v[j]-v[i])j++;
if(j==nums.size()-1||v[nums.size()-1]-v[j]<v[j]-v[i])break;
int start=j+1;
int end=nums.size()-1;
while(start<=end){
int mid=start+(end-start)/2;
if(v[mid]-v[i]>v[nums.size()-1]-v[mid])end=mid-1;
else start=mid+1;
}
count+=end-j+1;
count%=mod;
}
return count%mod;
}
};


for the left part im iterating using 'i'and 'j' signfies the middle part, for the last right part im using binary search to find the last index j can go and calculating it in count.it is giving one less than answer for the following test case: [8892,2631,7212,1188,6580,1690,5950,7425,8787,4361,9849,4063,9496,9140,9986,1058,2734,6961,8855,2567,7683,4770,40,850,72,2285,9328,6794,8632,9163,3928,6962,6545,6920,926,8885,1570,4454,6876,7447,8264,3123,2980,7276,470,8736,3153,3924,3129,7136,1739,1354,661,1309,6231,9890,58,4623,3555,3100,3437] It should be 227,my code is returning 226. Please Help,Thanks.

• 0

By om1429888, history, 3 months ago,

• -18

By om1429888, history, 5 months ago,

DecenTile Games have launched a new First Person Shooter soldier game, called the Call of War, that young gamers can play on their website. Our protagonist, Ninja (played by you) is a soldier whose mission is to kill all the enemies plotting against you. Your enemies are standing in a circle, numbered clockwise from 1 to n. Initially, the i-th enemy has ai health. You have only one pistol, and infinite bullet magazines. You have to shoot the enemies in order to kill them. Each bullet fired at the enemy decreases their health by 1 (deals 1 damage to it). When the health of some enemy i becomes 0 or less than 0, he dies and his grenade drops down and explodes, dealing bi damage to the next enemy (enemy i+1, if i<n, or enemy 1, if i=n). If the next enemy is already dead, then nothing happens. If the frag from the grenade kills the next enemy, even he drops a grenade, damaging the enemy after him and possibly triggering another explosion, and so on. You have to calculate the minimum number of bullets you need in order to kill all the enemies and win the game.

constraints 1 <= T <= 100 1 <= N <= 10^4 1 <= a, b <= 10^12

sampleinput 1 3 7 15 2 14 5 3 sample output 6 sample input 2 3 11 5 18 18 12 8 5 7 13 5 15 17 8 2 7 18 17 sample output 21 15