GSUB - Editorial

editorial
, , , , ,
1

PROBLEM LINK:

Practice
Contest

Setter: Mohammed Ehab
Tester: Ramazan Rakhmatullin
Editorialist: Ishmeet Singh Saggu

DIFFICULTY:

Easy

PREREQUISITES:

Ad-hoc

PROBLEM:

Given a sequence a_1,a_2,…,a_N. You have to process Q queries. In each query, you are given an index x and changes the x-th element of the sequence to y. After each query, you have to find the longest good sequences.

A sequence good if it does not contain any two adjacent identical elements.

EXPLANATION:

Let us think about what will be the length of the longest good sequence initially. We can imagine the array as a concatenation of segments where each number in a segment is the same and no 2 consecutive segments have the same number. Example - 1,1,1,2,2,1,3,3 (In this array there are 4 segments with index ranges : [1, 3], [4, 5], [6, 6] and [7, 8]), and our longest good sequence will be equal to the count of such segments.

Now let us see how a query can modify the longest good sequence if the query is (x,y). Now if y=a_x then there will be no change in the answer. So let us consider the case where y \neq a_x.

  • Case 1 : (a_x == a_{x-1}) and (a_x == a_{x+1}), then answer will increase by 2 as it will make 1 segment into 3 segments.
  • Case 2 : (a_x \neq a_{x-1}) and (a_x == a_{x+1}), then the answer will increase by 1 as earlier a_x == a_{x+1} and y will introduce an extra segment. If y = a_{x-1} then we will reduce the answer by 1 as earlier we added 1 as changing to y increased the segment count but now it will be merged with previous segment. Example : let a_x = a_{x+1} = 1 and a_{x-1} = 2, so If y = 3 answer will increase by 1, and if y = 2 then there will no change to the answer.
  • Case 3 : (a_x == a_{x-1}) and (a_x \neq a_{x+1}), similar to above case, we will increase the answer by 1. if y=a_{x+1} then we will reduce the answer by 1.
  • Case 4 : (a_x \neq a_{x-1}) and (a_x \neq a_{x+1}), then if y=a_{x-1} we will reduce answer by 1. if y = a_{x+1} we will reduce answer by 1.(Note that you might reduce the answer by 2 when y=a_{x-1}=a_{x+1}).

Also, you have to handle the edge cases(when x=1 or x=N), but you can reduce the casework with clever implementation.

TIME COMPLEXITY:

  • We take O(N) for computing the initial answer and O(1) for computing each query. So total time complexity per test case is O(N+Q).

SOLUTIONS:

Setter's Solution 
#include <bits/stdc++.h>
using namespace std;
int a[100005];
int main()
{
	int t;
	scanf("%d",&t);
	while (t--)
	{
		int n,q,ans=0;
		scanf("%d%d",&n,&q);
		for (int i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
			ans+=(a[i]!=a[i-1]);
		}
		while (q--)
		{
			int x,y;
			scanf("%d%d",&x,&y);
			ans-=(a[x]!=a[x-1]);
			if (x!=n)
			ans-=(a[x+1]!=a[x]);
			a[x]=y;
			ans+=(a[x]!=a[x-1]);
			if (x!=n)
			ans+=(a[x+1]!=a[x]);
			printf("%d\n",ans);
		}
	}
}
Tester's Solution 
#include <bits/stdc++.h>
 
#pragma clang diagnostic push
#pragma clang diagnostic ignored "-Wunused-const-variable"
#define popcnt(x) __builtin_popcount(x)
 
#define fr first
 
#define sc second
 
#define m_p make_pair
 
#define low_bo(a, x) lower_bound(a.begin(), a.end(), x) - a.begin()
 
#define up_bo(a, x) upper_bound(a.begin(), a.end(), x) - a.begin()
 
#define unique(a) a.resize(unique(a.begin(), a.end()) - a.begin())
 
#define popcnt(x) __builtin_popcount(x)
 
//#include <ext/pb_ds/assoc_container.hpp>
 
//using namespace __gnu_pbds;
 
//gp_hash_table<int, int> table;
 
//#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
//#pragma GCC target("avx,tune=native")
//float __attribute__((aligned(32)))
 
/*char memory[(int)1e8];
char memorypos;
 
inline void * operator new(size_t n){
    char * ret = memory + memorypos;
    memorypos += n;
    return (void *)ret;
}
 
inline void operator delete(void *){}
*/
 
using namespace std;
 
typedef long long ll;
 
typedef unsigned long long ull;
 
typedef long double ld;
 
typedef unsigned int uint;
 
template<typename T>
class Modular {
public:
    using Type = typename decay<decltype(T::value)>::type;
 
    constexpr Modular() : value() {}
 
    template<typename U>
    Modular(const U &x) {
        value = normalize(x);
    }
 
    static Type inverse(Type a, Type mod) {
        Type b = mod, x = 0, y = 1;
        while (a != 0) {
            Type t = b / a;
            b -= a * t;
            x -= t * y;
            swap(a, b);
            swap(x, y);
        }
        if (x < 0)
            x += mod;
        return x;
    }
 
    template<typename U>
    static Type normalize(const U &x) {
        Type v;
        if (-mod() <= x && x < mod()) v = static_cast<Type>(x);
        else v = static_cast<Type>(x % mod());
        if (v < 0) v += mod();
        return v;
    }
 
    const Type &operator()() const { return value; }
 
    template<typename U>
    explicit operator U() const { return static_cast<U>(value); }
 
    constexpr static Type mod() { return T::value; }
 
    Modular &operator+=(const Modular &other) {
        if ((value += other.value) >= mod()) value -= mod();
        return *this;
    }
 
    Modular &operator-=(const Modular &other) {
        if ((value -= other.value) < 0) value += mod();
        return *this;
    }
 
    template<typename U>
    Modular &operator+=(const U &other) { return *this += Modular(other); }
 
    template<typename U>
    Modular &operator-=(const U &other) { return *this -= Modular(other); }
 
    Modular &operator++() { return *this += 1; }
 
    Modular &operator--() { return *this -= 1; }
 
    Modular operator++(int) {
        Modular result(*this);
        *this += 1;
        return result;
    }
 
    Modular operator--(int) {
        Modular result(*this);
        *this -= 1;
        return result;
    }
 
    Modular operator-() const { return Modular(-value); }
 
    template<typename U = T>
    typename enable_if<is_same<typename Modular<U>::Type, int>::value, Modular>::type &operator*=(const Modular &rhs) {
#ifdef _WIN32
        uint64_t x = static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value);
        uint32_t xh = static_cast<uint32_t>(x >> 32), xl = static_cast<uint32_t>(x), d, m;
        asm(
        "divl %4; \n\t"
        : "=a" (d), "=d" (m)
        : "d" (xh), "a" (xl), "r" (mod())
        );
        value = m;
#else
        value = normalize(static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value));
#endif
        return *this;
    }
 
    template<typename U = T>
    typename enable_if<is_same<typename Modular<U>::Type, int64_t>::value, Modular>::type &
    operator*=(const Modular &rhs) {
        int64_t q = static_cast<int64_t>(static_cast<long double>(value) * rhs.value / mod());
        value = normalize(value * rhs.value - q * mod());
        return *this;
    }
 
    template<typename U = T>
    typename enable_if<!is_integral<typename Modular<U>::Type>::value, Modular>::type &operator*=(const Modular &rhs) {
        value = normalize(value * rhs.value);
        return *this;
    }
 
    Modular &operator/=(const Modular &other) { return *this *= Modular(inverse(other.value, mod())); }
 
    template<typename U>
    friend const Modular<U> &abs(const Modular<U> &v) { return v; }
 
    template<typename U>
    friend bool operator==(const Modular<U> &lhs, const Modular<U> &rhs);
 
    template<typename U>
    friend bool operator<(const Modular<U> &lhs, const Modular<U> &rhs);
 
    template<typename U>
    friend std::istream &operator>>(std::istream &stream, Modular<U> &number);
 
private:
    Type value;
};
 
template<typename T>
bool operator==(const Modular<T> &lhs, const Modular<T> &rhs) { return lhs.value == rhs.value; }
 
template<typename T, typename U>
bool operator==(const Modular<T> &lhs, U rhs) { return lhs == Modular<T>(rhs); }
 
template<typename T, typename U>
bool operator==(U lhs, const Modular<T> &rhs) { return Modular<T>(lhs) == rhs; }
 
template<typename T>
bool operator!=(const Modular<T> &lhs, const Modular<T> &rhs) { return !(lhs == rhs); }
 
template<typename T, typename U>
bool operator!=(const Modular<T> &lhs, U rhs) { return !(lhs == rhs); }
 
template<typename T, typename U>
bool operator!=(U lhs, const Modular<T> &rhs) { return !(lhs == rhs); }
 
template<typename T>
bool operator<(const Modular<T> &lhs, const Modular<T> &rhs) { return lhs.value < rhs.value; }
 
template<typename T>
Modular<T> operator+(const Modular<T> &lhs, const Modular<T> &rhs) { return Modular<T>(lhs) += rhs; }
 
template<typename T, typename U>
Modular<T> operator+(const Modular<T> &lhs, U rhs) { return Modular<T>(lhs) += rhs; }
 
template<typename T, typename U>
Modular<T> operator+(U lhs, const Modular<T> &rhs) { return Modular<T>(lhs) += rhs; }
 
template<typename T>
Modular<T> operator-(const Modular<T> &lhs, const Modular<T> &rhs) { return Modular<T>(lhs) -= rhs; }
 
template<typename T, typename U>
Modular<T> operator-(const Modular<T> &lhs, U rhs) { return Modular<T>(lhs) -= rhs; }
 
template<typename T, typename U>
Modular<T> operator-(U lhs, const Modular<T> &rhs) { return Modular<T>(lhs) -= rhs; }
 
template<typename T>
Modular<T> operator*(const Modular<T> &lhs, const Modular<T> &rhs) { return Modular<T>(lhs) *= rhs; }
 
template<typename T, typename U>
Modular<T> operator*(const Modular<T> &lhs, U rhs) { return Modular<T>(lhs) *= rhs; }
 
template<typename T, typename U>
Modular<T> operator*(U lhs, const Modular<T> &rhs) { return Modular<T>(lhs) *= rhs; }
 
template<typename T>
Modular<T> operator/(const Modular<T> &lhs, const Modular<T> &rhs) { return Modular<T>(lhs) /= rhs; }
 
template<typename T, typename U>
Modular<T> operator/(const Modular<T> &lhs, U rhs) { return Modular<T>(lhs) /= rhs; }
 
template<typename T, typename U>
Modular<T> operator/(U lhs, const Modular<T> &rhs) { return Modular<T>(lhs) /= rhs; }
 
template<typename T, typename U>
Modular<T> power(const Modular<T> &a, const U &b) {
    assert(b >= 0);
    Modular<T> x = a, res = 1;
    U p = b;
    while (p > 0) {
        if (p & 1) res *= x;
        x *= x;
        p >>= 1;
    }
    return res;
}
 
template<typename T>
bool IsZero(const Modular<T> &number) {
    return number() == 0;
}
 
template<typename T>
string to_string(const Modular<T> &number) {
    return to_string(number());
}
 
template<typename T>
std::ostream &operator<<(std::ostream &stream, const Modular<T> &number) {
    return stream << number();
}
 
template<typename T>
std::istream &operator>>(std::istream &stream, Modular<T> &number) {
    typename common_type<typename Modular<T>::Type, int64_t>::type x;
    stream >> x;
    number.value = Modular<T>::normalize(x);
    return stream;
}
 
const int md = 1e9 + 7;
 
using Mint = Modular<std::integral_constant<decay<decltype(md)>::type, md>>;
 
ll sqr(ll x) {
    return x * x;
}
 
int mysqrt(ll x) {
    int l = 0, r = 1e9 + 1;
    while (r - l > 1) {
        int m = (l + r) / 2;
        if (m * (ll) m <= x)
            l = m;
        else
            r = m;
    }
    return l;
}
 
#ifdef ONPC
mt19937 rnd(513);
mt19937_64 rndll(231);
#else
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
    mt19937_64 rndll(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif
 
template<typename T>
T gcd(T a, T b) {
    return a ? gcd(b % a, a) : b;
}
 
int gcdex(int a, int b, int &x, int &y) {
    if (a == 0) {
        x = 0;
        y = 1;
        return b;
    }
    int x1, y1;
    int ret = gcdex(b % a, a, x1, y1);
    x = y1 - (b / a) * x1;
    y = x1;
    return ret;
}
 
void setmin(int &x, int y) {
    x = min(x, y);
}
 
void setmax(int &x, int y) {
    x = max(x, y);
}
 
void setmin(ll &x, ll y) {
    x = min(x, y);
}
 
void setmax(ll &x, ll y) {
    x = max(x, y);
}
 
const ll llinf = 4e18 + 100;
 
const ld eps = 1e-9, PI = atan2(0, -1);
 
const int maxn = 1e5 + 100, maxw = 2e6 + 1111, inf = 1e9 + 100, sq = 450, LG = 18, mod = 1e9 + 933, mod1 = 1e9 + 993;
 
int n;
 
int a[maxn];
 
int main() {
#ifdef ONPC
    freopen("../a.in", "r", stdin);
    freopen("../a.out", "w", stdout);
#else
    //freopen("a.in", "r", stdin);
    //freopen("a.out", "w", stdout);
#endif // ONPC
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--) {
        int z;
        cin >> n >> z;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            ans += (i == 0 || a[i] != a[i - 1]);
        }
        while (z--) {
            int x, y;
            cin >> x >> y;
            x--;
            if (x == 0 || a[x] != a[x - 1])
                ans--;
            if (x + 1 < n && a[x] != a[x + 1])
                ans--;
            a[x] = y;
            if (x == 0 || a[x] != a[x - 1])
                ans++;
            if (x + 1 < n && a[x] != a[x + 1])
                ans++;
            cout << ans << '\n';
        }
    }
}
Editorialist's Solution 
#include <bits/stdc++.h>
using namespace std;
 
void Solve() {
	int n, q;
	cin >> n >> q;
	vector<int> a(n+2, -1); // I have made the array large so I doesn't have to handle edge cases.
	for(int i = 1; i <= n; i ++) {
		cin >> a[i];
	}
	int ans = 2; // considering the contribution of 0th element and (n+1)th element which is -1. (when I will print the answer I will reduce 2 from it to negate its effect).
				 // just done it to make the implementation easy.
	for(int i = 1; i <= n; i ++) {
		ans += (a[i] != a[i-1]);
	}
	while(q --) {
		int x, y;
		cin >> x >> y;
		if((a[x] == a[x-1]) && (a[x] == a[x+1])) {
			if(y != a[x]) ans += 2;
		}
		else if((a[x] != a[x-1]) && (a[x] == a[x+1])) {
			if(y != a[x]) ans ++;
			if(y == a[x-1]) ans --;
		}
		else if((a[x] == a[x-1]) && (a[x] != a[x+1])) {
			if(y != a[x]) ans ++;
			if(y == a[x+1]) ans --;
		}
		else {
			if(y == a[x-1]) ans --;
			if(y == a[x+1]) ans --;
		}
		a[x] = y;
		cout << ans-2 << "\n";
	}
}
 
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int test_case = 1;
	cin >> test_case;
	for(int i = 1; i <= test_case; i ++) {
		Solve();
	}
	
	return 0;
}

VIDEO EDITORIAL:

Feel free to share your approach. In case of any doubt or anything is unclear please ask it in the comment section. Any suggestions are welcomed. :smile:

10 Likes
2
2 Likes
3

Can someone please help me with what is wrong with solution for subpart A:
https://www.codechef.com/viewsolution/39220242

4

maybe you’re confused b/w sub-array and sub-sequence.

12 Likes
5

Subsequences need not to be continuous
I also made the same mistake :cry:

4 Likes
6

Straight Forward Solution

#include<bits/stdc++.h>
#define ll long long
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--)
    {
        ll n,q,x,y;
        cin>>n>>q;
        vector<ll>arr(n);
        for(int i=0;i<n;i++)
          cin>>arr[i];
        
        ll ans=1,cnt=1;
        for(int i=0;i<n-1;i++)
        {
            if(arr[i]!=arr[i+1])
              cnt++;
        }
        ans=cnt;
        while(q--)
        {
            cin>>x>>y;
            if(arr[x-1]==y)
              cout<<ans<<"\n";
            else
            {
                ll get=0;
                if((x-2)>=0 && arr[x-2]==arr[x-1])  // left
                   get++;
                  
                if(x<n && arr[x]==arr[x-1])        //  right
                   get++;
                   
                arr[x-1]=y;                        // updated value
                
                if((x-2)>=0 && arr[x-2]==arr[x-1])  // left
                   get--;
                  
                if(x<n && arr[x]==arr[x-1])        //  right
                   get--;
                   
                ans+=get;
                cout<<ans<<"\n";
            }
        }
    }
}
9 Likes
7

Yeah I got confused. The constant WA’s just kept annoying me and I kept thinking there is a fault in my code :sleepy:

1 Like
8

I invested wasted more than 2hrs on this

1 Like
9

Yeah same I tried it for over an hour in the contest. I felt the difficulty gap between the first and second(this) question was quite high.

10

I spent around 2 hours for this problems and got so many WA’s still couldn’t find solution.
But I am learning and will definitely solve all problems someday

6 Likes
11

can someone help me understand why I am getting TLE, even subtask 1 feels like it is taking too long to run

Solution

12

bro me too struggle hard for C I was getting Runtime error in 2 test case in python

because of one statement sys.setrecursionlimit(106)****

i forgot to include it in my code

13

Can someone help me where I’m going wrong.
Submission link

14

I did exactly what ma’am said, but still got TLE. I have coded in C++, could anyone please help me find what’s wrong with my solution? Thanks

My solution

15

Is it working?

16

you messed up sub seq with sub array

17

I also did same mistake :unamused:

19

/**************************************************************************

  • Id
  • File:
  • Purpose:
  • Author: Sanchit Gupta (CS19B071)
  • Created:
  • Last modified:
  • Bugs:
  • Change Log:
  • While(!(succeed==try());
    **************************************************************************/
    #include
    #include<bits/stdc++.h>

using namespace std;

int main()
{
int t;
cin>>t;
while(t–)
{
long int n;
long int q;
long int i=0;
cin>>n>>q;
long int arr[n];
map<long int,long int> mp;
long int count=0;
/while(i!=n)
{
cin>>arr[i];
i++;
}/
i=0;
cin>>arr[i];
long int prev=0,next;
i=1;
while(i!=n)
{
cin>>arr[i];
if(arr[i]==arr[i-1])
{
count++;
}
else
{
mp[prev]=i;
prev=i;
count=0;
}
i++;
}
mp[prev]=n;
/auto it3=mp.begin();
while(it3!=mp.end())
{
cout<first<<" "<second<<endl;
it3++;
}/
i=0;
long int x,y;
while(i!=q)
{
cin>>x>>y;
x–;
auto it = mp.lower_bound(x);
if(y==arr[x])
{
cout<<mp.size()<<endl;
i++;
continue;
}
else if(x>0 && x<n-1 && y==arr[x-1] && y==arr[x+1])
{
arr[x]=y;
if(it->first==x)
{
auto it1=it;
auto it2=it;
it–;
it1++;
long int a=it->first,b=it1->second;
mp.erase(it2);
mp.erase(it1);
mp[a]=b;

            }
        }
        else if(x<n-1 && y==arr[x+1])
        {
            arr[x]=y;
            if(it->first==x)
            {
                auto it1=it;
                it1++;
                long int a=it->first,b=it1->second;
                mp.erase(it);
                mp.erase(it1);
                mp[a]=b;
            }
            else
            {
                auto it1=it,it2=it;
                it2--;
                long int  a=it2->first,b=it->second;
                mp.erase(it);
                mp.erase(it2);
                mp[a]=x;
                mp[x]=b;
                
            }
        }
        else if(x>0 && y==arr[x-1])
        {
            //cout<<"yeah";
            arr[x]=y;
            auto it1=it;
            it1--;
            long int a=it1->first,b=it->second;
            mp.erase(it);
            mp.erase(it1);
            mp[a]=x+1;
            if(x+1!=b)
            {
                 mp[x+1]=b;
            }
        }
        else
        {
            arr[x]=y;
            //cout<<"yes";
            if(it==mp.end())
            {
                //cout<<"yes";
                auto it1=it;
                it1--;
                long int a=it1->first,b=it1->second;
                mp.erase(it1);
                mp[a]=x;
                mp[x]=x+1;
                if(b!=x+1)
                {
                    
                mp[x+1]=b;
                }
            }
            else if(it->first==x)
            {
                if(it->second==x+1)
                {
                    
                }
                else
                {
                    //cout<<"yeah";
                    long int s = it->second;
                    mp.erase(it);
                    mp[x]=x+1;
                    mp[x+1]=s;
                }
            }
            else
            {
                long int a=it->first,b=it->second;
                mp.erase(it);
                mp[a]=x;
                mp[x]=x+1;
                mp[x+1]=b;
            }
        }
        /*auto it3=mp.begin();
        while(it3!=mp.end())
        {
            cout<<it3->first<<" "<<it3->second<<endl;
            it3++;
        }*/
        cout<<mp.size()<<endl;
        i++;
    }
    
 }

}

What is the problem with this code ?
Why does it give TLE

21

This question can also be done using Segment Trees. But The time take will be O(QLog(N)+NLog(N))

22

Yes