CSES-Two Sets (solution + explanation)
CSES এর খুবই মজার একটা প্রবলেম হলো Two Sets প্রবলেম. একটু মাথা ঘাটালেই এর সমাধান পাওয়া যায়। তো আসুন white paper নিয়ে বসা যাক...
Problem:
Time limit: 1.00 s | Memory limit: 512 MB
Your task is to divide the numbers 1,2,…,n into two sets of equal sum.
Input
The only input line contains an integer n.
Output
Print "YES", if the division is possible, and "NO" otherwise.
After this, if the division is possible, print an example of how to create the sets. First, print the number of elements in the first set followed by the elements themselves in a separate line, and then, print the second set in a similar way.
Constraints
Example 1
Input:
7
Output:
YES
4
1 2 4 7
3
3 5 6
Example 2
Input:
6
Output:
NO
মেইন কথা হলো একটা সংখ্যা n েদওয়া থাকবে এবং আমাদের কাজ হবে 1 থেকে ঔ সংখ্যা(n) পর্যন্ত যত সংখ্যা আছে তাদের 2 ভাগে ভাগ করা যাতে উভয় ভাগের যোগফল সমান হয়। যদি এমন কোনো ভাগ তৈরি করা না যায় তাহলে "NO" প্রিন্ট করতে হবে(example 2)। আর উত্তর থাকলে "YES" প্রিন্ট করে ভাগ দুটি তাদের পরিমান সহ প্রিন্ট করতে হবে(example 1)।
বহু বছরের গবেষণার পর বোঝা গেল যে এখানে একটা পেটার্ন আছে যার মাধ্যমে সহজেই এটা সমাধান করা যায় (আরো সহজ সমাধান থাকতেই পারে, থাকাটাই সাভাবিক। কিন্তু এটার আইডিয়া পাবার পর অন্যকিছু আর ভাবা হয়নি)। প্যাটার্নটাকে আমি snake pattern বলি কারন এখানে সংখ্যা গুলোকে সাপের মতো করে সাজানো হয়।
যদি n = 8 হয় তবে আমরা একে সাজাবো এভাবে,
8 5 -> 4 1
| | | |
7 -> 6 3 -> 2
এখানে হিসাবের সুবিধর্তে vector 1 = 8, 5, 4, 1 এবং vector 2 = 7, 6, 3, 2 ধরতে পারি। snake pattern এ কিছু মজার বৈশিষ্ট আছে। যেমন, প্রত্যেকবার decrement 3 বা 1 করে হয়েছে, vector 1 সর্বচ্চ সংখ্যা থেকে vector 2 দ্বিতীয় সর্বচ্চ সংখ্যা থেকে শরু হয়েছে। উভয়েরই সর্বনিম্ন সংখ্যা ০ থেকে বড়।
এই বৈশিষ্ট গুলো ব্যবহার করে সহজেই vector 1 এবং vector 2 গঠন করা যাবে।
এরপর দেখব এদের যোগফলের পার্থক্য কত।
পার্থক্য = ০ হলে vector 1 এবং vector 2 সমান। উত্তর "YES"।
পার্থক্য = 1 হলে vector 1 এবং vector 2 কে কখনো সমান করা যাবে না কারন অতিরিক্ত 1 যে vectorরেই দেয়া হোকনা কেন তার মান ওপরটির থেকে বেরে যাবেই। সুতরাং উত্তর "NO"।
পার্থক্য = ২ হলে বড় vector থেকে 1 কেটে ছোট vector a রাখলেই দুটি সমান হয়ে যাবে(এক্ষেত্রে আমি vector 1 এবং vector 2 এর মাঝে element swap করেছি)। উত্তর "YES"।
snake pattern এ এই ৩টি ঘটনাই ঘটতে পারে যার মাধ্যমে কাঙ্খিত সেই দুটি ভাগ পাওয়া যাবে।
code:
click here for -> Code link<-
#include <vector>
#include <iostream>
#include <algorithm>
#include <numeric>
#define ll signed long long int
void print_vec(std::vector <ll> v1, std::vector <ll> v2)
{
// printing result if available
// part 1 (vector v1)
printf("YES\n%lld\n", (ll)v1.size());
for (ll i = 0; i < v1.size();i ++)
{
printf("%lld ", v1[i]);
}
// part 2 (vector v2)
printf("\n%lld\n", (ll)v2.size());
for (ll i = 0; i < v2.size(); i ++)
{
printf("%lld ", v2[i]);
}
}
int main(void)
{
ll n = 0;
scanf("%lld", &n);
// v1 = v2 = store snake pattern values
std::vector <ll> v1, v2;
// process
// creating vectors
int v1s = 1, v2s = 3;
for (ll v1i = n, v2i = n - 1; v1i > 0 || v2i > 0; v1i -= v1s, v2i -= v2s)
{
// decrement 3, decrement 1, decrement 3, decrement 1...........
if (v1i > 0)
{
v1.push_back(v1i);
(v1s == 1)? v1s = 3 : v1s = 1;
}
if (v2i > 0)
{
v2.push_back(v2i);
(v2s == 1)? v2s = 3 : v2s = 1;
}
}
//end creating vectors
//storing sum of 2 vectors
ll v1sum = std::accumulate(v1.begin(), v1.end(), 0);
ll v2sum = std::accumulate(v2.begin(), v2.end(), 0);
// if difference of 2 sum is 1 then print NO
if (abs(v1sum - v2sum) == 1)
{
printf("NO");
}
// if difference of 2 sum is 0 then this 2 vector is already equal. just print them
else if (v1sum - v2sum == 0)
{
// print_vec will print this 2 vectors according output needs
print_vec(v1, v2);
}
// if difference is 2 then we can swap value to resize and make equal
else if (abs(v1sum - v2sum) == 2)
{
// if sum of vector 1 > vector 2 then we can simply swap 1st values of both them
// cause 1st value is greater in vector 1(snake pattern). this way we can make equal
if (v1sum > v2sum)
{
std::swap(v1[0], v2[0]);
}
// 2nd value is greater in vector 2 (snake pattern)
else
{
std::swap(v1[1], v2[1]);
}
// after swap it is now equal. so print it
print_vec(v1, v2);
}
else printf("NO");
return 0;
}
