White Papier

Lets share and store informations for our next generations.  

[whitepapier]

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

1≤n≤106

Example 1 Input: 7 Output: YES 4 1 2 4 7 3 3 5 6 Example 2 Input: 6 Output: NO

Problem Explanation:

মেইন কথা হলো একটা সংখ্যা n েদওয়া থাকবে এবং আমাদের কাজ হবে 1 থেকে ঔ সংখ্যা(n) পর্যন্ত যত সংখ্যা আছে তাদের 2 ভাগে ভাগ করা যাতে উভয় ভাগের যোগফল সমান হয়। যদি এমন কোনো ভাগ তৈরি করা না যায় তাহলে "NO" প্রিন্ট করতে হবে(example 2)। আর উত্তর থাকলে "YES" প্রিন্ট করে ভাগ দুটি তাদের পরিমান সহ প্রিন্ট করতে হবে(example 1)।

Solution Explanation:

বহু বছরের গবেষণার পর বোঝা গেল যে এখানে একটা পেটার্ন আছে যার মাধ্যমে সহজেই এটা সমাধান করা যায় (আরো সহজ সমাধান থাকতেই পারে, থাকাটাই সাভাবিক। কিন্তু এটার আইডিয়া পাবার পর অন্যকিছু আর ভাবা হয়নি)। প্যাটার্নটাকে আমি 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; }