Light OJ - 1269 - Consecutive Sum Tutorial

Problem Description here

সহজ ভাষায় বলতে গেলে, একটা অ্যারে দেয়া থাকবে। এই অ্যারে থেকে এমন একটা সাবঅ্যারে সিলেক্ট করতে হবে যাতে এই সাবঅ্যারের সব সংখ্যাগুলোর XOR সর্বোচ্চ হয়। একইভাবে, এমন একটা সাবঅ্যারে সিলেক্ট করতে হবে যাতে এই সাবঅ্যারের সংখ্যাগুলোর XOR সর্বনিম্ন হয়। সর্বোচ্চ এবং সর্বনিম্ন সংখ্যাটি প্রিন্ট করতে হবে। 

সলুশ্যন আইডিয়াঃ

সাবঅ্যারের XOR কথাটি আসলেই মূলত PrefixXOR এর আইডিয়া আসে। 

১) অ্যারেটির PrefixXOR বের করে রাখবো। এখন, অ্যারের l to r ইনডেক্সের XOR মানে কী? 

PrefixXOR[r] ^ PrefixXOR[l-1]

২) ক্রমানুসারে প্রতিটি PrefixXOR এর বিট গুলো নিবো MSB থেকে LSB।

আমি যদি এখন PrefixXOR অ্যারের ith পজিশনে থাকি তাহলে ট্রাই তে 0 to (i-1) পজিশন পর্যন্ত PrefixXOR অ্যারের প্রতিটা এলিমেন্ট এর বিট সিকুয়েন্স স্টোর করা আছে। 

এখন, বর্তমান এলিমেন্ট এর জন্য এর পূর্বের অল পসিবল সাবঅ্যারের XOR এর কাজটা আমরা ট্রাই তে স্টোরড ডেটা থেকে করতে পারি। কীভাবে?

বর্তমান বিট সিকুয়েন্স এর একটা পজিশনে যদি ০ থাকে আমি চেষ্টা করবো ট্রাই এর বর্তমান নোড থেকে ১ এর পথে যেতে। বিট সিকুয়েন্সে যদি ১ থাকে আমি চেষ্টা করবো ট্রাই এর বর্তমান নোড থেকে ০ এর পথে যেতে। Desired পথ না থাকলে অন্য পথে যাবো। আর যেতে পারলে এই বিটের জন্য উপযুক্ত ভ্যালু একটা ভ্যারিয়েবলে যোগ করবো এবং সবশেষে তা রিটার্ন করবো। এভাবে, আমরা 1 থেকে বর্তমান ইনডেক্স পর্যন্ত অল-পসিবল সাবঅ্যারের জন্য ম্যাক্সিমাম ভ্যালু পাবো। 

মিনিমাম বের করার জন্য ঠিক তার উল্টোটা হবে। 

খাতা কলমে কিছুটা চিন্তা করলে আশা করি লজিকটি বুজতে সহজ হবে। এরপরেও না হলে সলুশ্যন দেখতে পারো নিজ দায়িত্বে।

বিঃদ্রঃ সলুশ্যন দেখে প্রব্লেম সলভ করা ভালো প্র্যাকটিস না।

	#include<bits/stdc++.h>
	#define scin(x) sc("%d",&(x))
	#define scln(x) sc("%lld",&(x))
	#define RUN_CASE(t,T) for(__typeof(t) t=1;t<=T;t++)
	using namespace std;
	bool Check(int N, int pos) {return (bool)(N & (1<<pos));}
	const int N = 50000+100;
	int tot_node = 1;
	int to[1600009][2];
	int ara[N],prefixxor[N];
	void Add(vector<int> &v)
	{
	int sz = (int)v.size() , curr = 1;
	for(int i=0 ; i<sz ; i++){
	int bit = v[i];
	if(!to[curr][bit]) to[curr][bit] = ++tot_node;
	curr = to[curr][bit];
	}
	}
	int Maximize(vector<int> &v)
	{
	int sz = (int)v.size() , curr = 1 , ret=0;
	for(int i=0 ; i<sz ; i++){
	int bit = v[i];
	if(to[curr][bit^1]){
	ret += (1<<(sz-i-1));
	curr = to[curr][bit^1];
	}
	else
	curr = to[curr][bit];
	}
	return ret;
	}
	int Minimize(vector<int> &v)
	{
	int sz = (int)v.size() , curr = 1 , ret=0;
	for(int i=0 ; i<sz ; i++){
	int bit = v[i];
	if(to[curr][bit])
	curr = to[curr][bit];
	else{
	ret += (1<<(sz-i-1));
	curr = to[curr][bit^1];
	}
	}
	return ret;
	}
	void Solve(int t)
	{
	int i,j,k,n,mx=0,mn=2147483647;
	tot_node = 1;
	ms(to , 0);
	scin(n);
	for(i=1 ; i<=n ; i++){
	scin(ara[i]);
	prefixxor[i] = prefixxor[i-1]^ara[i];
	}
	for(i=0 ; i<=n ; i++){
	vector<int>bit;
	for(j=31 ; j>=0 ; j--)
	bit.pb(Check(prefixxor[i] , j));
	if(i > 0){
	mx = max(mx , Maximize(bit));
	mn = min(mn , Minimize(bit));
	}
	Add(bit);
	}
	pf("Case %d: %d %d\n",t,mx,mn);
	}
	int main()
	{
	int t,T;
	scin(T);
	RUN_CASE(t,T)
	{
	Solve(t);
	}
	return 0;
	}

view raw LOJ - 1269.cpp hosted with ❤ by GitHub