Problem Statement Given N heroes with power levels a1, a2....an. You have to partition the heroes with the following rules: 1. Each hero should be part of exactly one partition. 2. Each partition should consist of at least one hero. 3. A partition should consist of only consecutive heroes i.e. if a; and a; (where i<j) are part of the same partition then all a (i < k <=j) should be part of that partition. The strength of the partition is defined as the maximum difference between the power of any two heroes in that partition. You have to partition such that the sum of the strength of partitions is maximum. Output the sum of the strength of partitions. Input format: N a1, a2.....an Constraints: N<=1e6

My initital intuition was DP but obviously it is out of contraints. I have seen many such questions but was not able to solve them.

https://codeforces.net/problemset/problem/1738/C

Hi guys,i was upsolving this round and could not figure out how to solve this.I went for the editorials but still could not figure out why they are using mod 4 not some other number.can someone please guide me with the intution behind this problem?

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).

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.

Please help!!!

https://codeforces.net/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?

((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;
	// Write your coder here.
    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;
}

PLEASE HELP ME.

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>

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.net/contest/1279/problem/D

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

https://codeforces.net/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?

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

https://codeforces.net/problemsets/acmsguru/problem/99999/106 can someone please help me solve this?

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

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;
}

#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;
}

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.

https://www.hackerearth.com/practice/algorithms/searching/binary-search/practice-problems/algorithm/partitions-5fd40ffc/

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