Help in Yet Another Partition Problem

CodeChef-DSA-learners
1

can anyone plz tell me the logic for this question, i am unable to get, even i saw the hint and editorial, still i am not able to get anything for this question

question link- CodeChef: Practical coding for everyone

2

Firstly, It’s easy to see that the number of subarrays is The number of values of i such that A_{i-1} doesn’t divide A_i plus 1. This can be proved by the fact if a subarray started at i, and A_{i-1} divides A_{i}, Then pushing the start of the subarray to i-1 is optimal because there is one less element before it, so it may have fewer subarrays, and the number of subarrays after it will remain constant.

Let’s keep a set that stores all the indexes which are at the beginning of a subarray.

Now for each update query, if our new A_i divides A_{i+1}, Then A_{i+1} will definitely not be starting index, so we can erase it. If it doesn’t, Then A_{i+1} will definitely be a starting index so we insert it. Now consider the other pair A_{i-1} and A_i . if A_{i-1} divides A_i, then A_i is definitely not a starting index, and if it doesn’t, then A_i is definitely a starting index.

So for type 2 queries, we can simply find the largest element less than or equal to i in begin.

My solution : CodeChef: Practical coding for everyone

1 Like
3

the link to your solution says permission denied.

4

Okay

My code 
#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
#include <vector>
#define ll long long int
#define mp make_pair
#define pb push_back
#define vi vector<int>
using namespace std;
void solve(){
    int n,Q;
    cin>>n>>Q;
    vector<int> seq(n);
    set<int> begin;
    begin.insert(0);
    for(int i=0;i<n;i++){
        cin>>seq[i];
        if(i>0 && seq[i]%seq[i-1]!=0){
            begin.insert(i);
        }
    }
    while(Q--){
        int type;
        cin>>type;
        if(type==1){
            int pos, value;
            cin>>pos>>value;
            --pos;
            seq[pos]=value;
            if(pos+1<n && seq[pos+1]%seq[pos]==0){
                begin.erase(pos+1);
            }
            else{
                begin.insert(pos+1);
            }
            if(pos>0 && seq[pos]%seq[pos-1]==0){
                begin.erase(pos);
            }
            else{
                begin.insert(pos);
            }
        }
        if(type==2){
            int pos;
            cin>>pos;
            --pos;
            auto it=begin.upper_bound(pos);
            --it;
            cout<<*it + 1<<'\n';
        }
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}
1 Like
5

Thanks bhai.
finally i got it.

6

My code :
try:
N, Q = map(int, input().split())
N_list = list(map(int, input().split()))
n__ = N_list[::]
N_list.sort()

def make_s_list():
    global N_list
    l = N_list
    S = {}
    m = 1

    for z in range(len(l) - 1):
        appended = False
        jj = 1
        if len(S) == 0:
            S[m] = []
            S[m].append(int(l[z]))
        while jj <= m:
            if int(l[z]) % int(S[jj][-1]) == 0:
                appended = True

                S[m].append(int(l[z]))

            jj += 1
        if appended == False:
            m += 1
            S[m] = []
            S[m].append(int(l[z]))
    return S


last = 0
for _ in range(Q):
    te, *operation = input().split()

    if int(te) == 1:
        N_list[int(operation[0]) - 1] = int(operation[1])
        last = 1

    else:
        if last == 1:
            s = make_s_list()
            last = 2
        smaller_value = n__[0]
        print(s)
        for c in range(len(s)):
            if n__[int(operation[0]) - 1] in s[c + 1]:
                smaller_value = s[c + 1][0]
                break
        print(n__.index(smaller_value) + 1)

Please Tell me whats Wrong with my solution

7

Please Can you tell me the Concept I am Still not getting it as I am Using Python