### Rudro25's blog

By Rudro25, 5 weeks ago,

Finally, The round is over smoothly :) We hope everyone had fun and enjoyed the contest!

A. Directional Move

Tutorial
Solution
Tester Solution

B. Make All Odd

Tutorial
Solution

C. Team

Tutorial
Solution
Tester Solution

D. XOR Game

Tutorial
Solution
Tester Solution

Tutorial
Solution
Tester Solution
Tester Solution 2

F. Offer

Tutorial
Solution
Tester Solution

-If have any more query, then please comment.

• +129

 » 5 weeks ago, # |   0 thanks for this contest and hope for more contest like this.
•  » » 5 weeks ago, # ^ |   0 Rudro25 what can be the difficulty of problems E and F?
•  » » » 5 weeks ago, # ^ |   0 My guess: E(1400-1500) and F(1500-1600)
 » 5 weeks ago, # | ← Rev. 2 →   0 Great round. For D, if x and y have no common bits then answer is NO else YES. So this will also work if(x & y) cout << "Yes"; else cout << "No"; 
•  » » 5 weeks ago, # ^ |   +2 this will also work! cout << ((a | b) == (a + b) ? "No" : "Yes") << "\n"; 
•  » » » 5 weeks ago, # ^ |   +6 Both are same!a + b = (a | b) + (a & b)
•  » » 5 weeks ago, # ^ |   +1 thank you for this . I came up with the same logic , but didn't know how to proceed with bit manipulations.So used the basic method to calculate every bit by n%2 and check whether both of them are 1 or not if(a%2 && b&2) { cout<<"Yes" return; else a=>>1; b=>>1; } 
•  » » » 5 weeks ago, # ^ |   0 My method is quite different then the others.First I mapped the position of each set bits in $a$ and $b$.If both $a$ and $b$ has a common position set bit then the bit is off(basic xor).Then I traverse the map and if any second value is $0$ then ans is $YES$.Otherwise $NO$. Spoiler...  cin>>n>>m; M mp; for(ll i=0;(1<
 » 5 weeks ago, # |   0 Thanks for the round and quick editorial
•  » » 5 weeks ago, # ^ |   0 welcome sir!
 » 5 weeks ago, # |   0 Thanks for the round waiting for the next one
•  » » 5 weeks ago, # ^ |   0 welcome sir! i will try (:
 » 5 weeks ago, # |   0 Hoping to solve upto D in div2 contest also some day. btw thanks for this contest and hope for more contest like this.
•  » » 5 weeks ago, # ^ |   0 welcome sir :D i will try soon for the next one.
•  » » 5 weeks ago, # ^ |   0 Welcome, Sir! Hope to see you next time also
 » 5 weeks ago, # |   +15 Nicely done, thanks for the contest!
•  » » 5 weeks ago, # ^ |   +13 Thank you sir, for the support. orz
 » 5 weeks ago, # |   +4 E was really a good problem for learning dp, thanks for the round.
•  » » 5 weeks ago, # ^ |   0 welcome sir!
 » 5 weeks ago, # |   +3 We can also solve E with combinatorics. Combination with repetition to be exact. Suppose the string is like, 1----5. We can place any digit from this, {1,2,3,4,5} set in increasing order in 4 place between 1 and 5.Let, n = number of place to fill. m = size of the set. Possible ways will be (n+m-1) Choose n.For practice: https://codeforces.com/contest/1288/problem/C
•  » » 5 weeks ago, # ^ |   0 I thought on similar lines but wasn't able to get my code working as intended. I'd appreciate it if anyone out here could look into the following submission.
•  » » » 5 weeks ago, # ^ |   0 Try checking the validity of the result explicitly.
•  » » » 5 weeks ago, # ^ |   +1 The problem is with the size of your fac array which is 100005 but according to the problem n<=10^6 which makes n+k-1<=100009(and it is less than 100005).I changed 100005 to 100020 and it got Accepted
•  » » » » 5 weeks ago, # ^ |   0 Silly me! Thank you so much!
•  » » » » 5 weeks ago, # ^ |   0 are you sure about this? I submitted the same code after changing it to int fac[100020]; and still got WA at test 4. Did you change anything else?
•  » » » » » 5 weeks ago, # ^ |   0 You are running the first for loop (inside int main function) only upto 100005, change it to 100020 too.
•  » » » » » » 5 weeks ago, # ^ |   0 Of course, should have known that. Thank you very much.
•  » » 5 weeks ago, # ^ |   0 Thanks for the formula, I got stuck at this and couldn't find this formula. Can you please provide me an explanation or a link where this formula can be find? Thanks for the given problem too.
•  » » » 5 weeks ago, # ^ |   +3 Stars and barsImagine you need to fill a sequence of integers of size $10$ using only $1$, $2$, or $3$ so that the sequence is non-decreasing. As they are non-decreasing, all $1$'s have to appear in front of all $2$'s and so on, so we don't need to care about the order of these integers and we need only the number of occurences of each $1$, $2$, and $3$. Thus, we need to find number of solution of: $count_1 + count_2 + count_3 = 10$, with $count_0, count_1, count_2 \geq 0$.
•  » » » » 5 weeks ago, # ^ |   0 Thank you for the explanation and the link. I got it.
•  » » » 5 weeks ago, # ^ |   +2 Check this out: https://www.youtube.com/watch?v=4_je4mXUCGA Hope it will be helpful. I learned it from Coursera. Someone uploaded the video in YouTube too.
•  » » » » 5 weeks ago, # ^ |   0 Thanks for the help.
•  » » » 5 weeks ago, # ^ |   0 Consider this example:1 — — — 6In this we have to fill 3 places and to fill those 3 places we have 6 elements. Now observe that we only need to choose the elements with which we want to fill the gaps. We don't need to decide the order as that is fixed.
•  » » » » 5 weeks ago, # ^ |   0 I got the idea in the contest but was unable to find the formula for that. which hijibijee provided.
•  » » 5 weeks ago, # ^ |   0 Thancs for the formula :)...was thinking of this approach but couldn't remember the formula
•  » » 5 weeks ago, # ^ |   0 I also tried to solve it with combinatorics. 105596767 This is the code it's failing test case 4. So can you help? if you find something. Thanks in advance.
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   +1 Your solution will fail for (n+m-1) > 10e5 cases. Calculate factorials up to 10e6.check this comment: https://codeforces.com/blog/entry/87253?#comment-754156
•  » » » » 5 weeks ago, # ^ |   0 Ok Done :)
•  » » » » 5 weeks ago, # ^ |   0 can you please explain the formula.how m+n-1
 » 5 weeks ago, # | ← Rev. 2 →   +6 Thanks for the contest, had fun doing it!
•  » » 5 weeks ago, # ^ |   0 Welcome sir!
 » 5 weeks ago, # |   +14 Please make the submissions public, or atleast the testcases. It helps a lot in debugging silly mistakes.
•  » » 5 weeks ago, # ^ |   0 I already told this secondthread sir. May be he will open soon , if possible sir.
 » 5 weeks ago, # |   0 Could anyone explain F in a more detailed way? It would be much appreciated.
•  » » 5 weeks ago, # ^ |   +3 It's just 2 pointer approach, we can keep on increasing our right pointer while maintaining frequency and cost, until the cost becomes greater than k. At this point we can start incrementing our left pointer and decreasing the cost. The number of elements will right-left+1. Now we keep on repeating the prcoess. Code#include using namespace std; template string to_string(pair p); string to_string(const char& ch) { return "'" + string(1, ch) + "'"; } string to_string(const string& s) { return '"' + s + '"'; } string to_string(const char* s) { return to_string((string) s); } string to_string(bool b) { return (b ? "true" : "false"); } string to_string(vector v) { bool first = true; string res = "{"; for (int i = 0; i < static_cast(v.size()); i++) { if (!first) { res += ", "; } first = false; res += to_string(v[i]); } res += "}"; return res; } template string to_string(A v) { bool first = true; string res = "{"; for (const auto &x : v) { if (!first) { res += ", "; } first = false; res += to_string(x); } res += "}"; return res; } template string to_string(pair p) { return "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; } #define output cout void debug_out() { output << endl; } template void debug_out(Head H, Tail... T) { output << " " << to_string(H); debug_out(T...); } #ifndef ONLINE_JUDGE #define dbg(...) output << "[" << #__VA_ARGS__ << "] :", debug_out(__VA_ARGS__) #else #define dbg(...) 42 #endif #define ll int64_t #define ull uint64_t #define lld long double #define FIO ios_base::sync_with_stdio(false);cin.tie(NULL); #define pb push_back #define eb emplace_back #define ff first #define ss second #define vt vector #define vll vt #define pll pair #define vpll vt #define vvll vt #define all(v) v.begin(),v.end() #define rall(v) v.rbegin(), v.rend() #define FOR(i,n) for(ll i=0;i=b;i--) #define space cout<<"\n\n"; #define endl '\n' // comment this line in interactive prob template using mxpq = priority_queue; template using mnpq = priority_queue, greater>; #define fps(x,y) fixed< istream& operator>>(istream& in, pair &a) {in >> a.ff >> a.ss; return in;} template ostream& operator<<(ostream& out, pair a) {out << a.ff << " " << a.ss; return out;} template T amax(T &a, T1 b) {if (b > a) a = b; return a;} template T amin(T &a, T1 b) {if (b < a) a = b; return a;} int dx[4] = { -1, 0, 1, 0}; int dy[4] = {0, 1, 0, -1}; // up, right, down, left const double PI = 3.14159265359; const ll INF = 0x3f3f3f3f3f3f3f3fll; const ll N = 1e6 + 6; const ll MAX_SIZE = 2e6 + 6; const ll mod = 1e9 + 7; ll powerM(ll x, ll y, ll M = mod) { // default argument ll v = 1; x = x % M; while (y > 0) {if (y & 1)v = (v * x) % M; y = y >> 1; x = (x * x) % M;} return v; } ll power(ll x, ll y) { ll v = 1; while (y > 0) {if (y & 1)v = v * x; y = y >> 1; x = x * x;} return v; } int largest_bit(long long x) { // based on 0-indexing return x == 0 ? -1 : 63 - __builtin_clzll(x); } const ll maxN = 1e6 + 9; void preSolve() { } void solve() { ll n, k; cin >> n >> k; vll a(n); FOR(i, n) { cin >> a[i]; } ll i = -1, j = 0, cost = 0; vll hash(maxN, 0); ll ans = 0; while (i < n) { if (i + 1 < n) { ++i; if (hash[a[i]] == 0) { cost += a[i]; hash[a[i]]++; // } else { hash[a[i]]++; } } // while (cost > k && j <= i) { if (hash[a[j]] > 1) { hash[a[j]]--; ++j; } else { hash[a[j]]--; cost -= a[j]; ++j; } } ans = max(ans, i - j + 1); if (i + 1 == n) break; } cout << ans << endl; } int main() { #ifdef LOCAL freopen("in1.txt", "r", stdin); freopen("out1.txt", "w", stdout); #endif FIO; preSolve(); int testcases = 1; cin >> testcases; for (int caseno = 1; caseno <= testcases; ++caseno) { // cout << "Case #" << caseno << ": "; solve(); } return 0; } 
 » 5 weeks ago, # |   0 If in problem D, we were asked to maximize the score of Bob, how will we solve it ?
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +3 I think You can iterate from the highest to lowest bit, and try to set it, if possible.
 » 5 weeks ago, # |   0 The contest was great! Although I had come up with a similar idea as editorial, I had a hard time proving D during contest. I still can't wrap around why case 2 always is true. Could anyone please explain?
•  » » 5 weeks ago, # ^ |   0 Hope This comment helps you.
•  » » » 5 weeks ago, # ^ |   0 Indeed, thank you so much!
 » 5 weeks ago, # |   0 Nice Contest..problem set was really good.
•  » » 5 weeks ago, # ^ |   0 Thank you bhai :D
 » 5 weeks ago, # |   0 Very nice contest! Want more! Especially thanks for the good E task.
•  » » 5 weeks ago, # ^ |   0 Thank you sir!
 » 5 weeks ago, # |   0 The F can also be solved using the bit + binary lifting technique.
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +1 But isn't it overkill?
 » 5 weeks ago, # | ← Rev. 2 →   0 can you please add more test cases? bacause it is just checking with one test case and getting accepted?so now i don't even know whether my solution is correct or not?
•  » » 5 weeks ago, # ^ |   0 You have the permission to see only 1 test case, sir. May be it's the 'gym' contest rule.
 » 5 weeks ago, # | ← Rev. 2 →   0 For C, why is the following approach incorrect? Answer is at least equal to elements >=k. Now put other elements in a list and sort it. Now iterate over every element, for every a[i], use lower_bound() on k-a[i] in range [i, list.size()] to find if such element exists. If it does, mark it used and increment answer. Why does this give a WA? Code#include using namespace std; //#pragma GCC optimize "trapv" #define ll long long int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int t; cin>>t; while (t--) { int n,k; cin>>n>>k; int ans = 0; vector v; v.reserve(n/2); for (int i=0;i>r; if (r>=k) ans++; else v.push_back(r); } sort(v.begin(), v.end()); int len = v.size(); vector used(len); for (int i=0;i
•  » » 5 weeks ago, # ^ |   0 can you please provide the code by spoiler! no permission to see other submission :(
•  » » » 5 weeks ago, # ^ |   0 Sure! My bad
•  » » » » 5 weeks ago, # ^ |   0 Failed test case: 1 10 5 1 3 2 1 4 3 4 2 3 1Expected: 4 but found 6.May be the problem is — When you find a pos by lower_bound it can be also used before but you not checked that. may be you can use set and remove every used element then you can use lower_bound easily.
•  » » » » » 5 weeks ago, # ^ |   +1 Ah right, I think the problem exactly is what you pointed out, I should definitely be removing those used values from my list. Thanks! Orz
 » 5 weeks ago, # |   0 Let's consider a variation of problem F. Now in the subsegment [l,r] instead of making the cost of all repeating elements in that subsegment zero if we were allowed to take only one of the repeating elements in that subsegment and make its cost equal to zero. Rest all the conditions remain same as mentioned in the problem F. Then can someone please provide an insight on how we could have solved it.
 » 5 weeks ago, # |   0 Hello , Thanks for this Contest . Can you Please Update the Settings so that we can we view all the test case , My Code for F gave wrong answer on test case 3 but I cannot access that test case . Thanks .
•  » » 5 weeks ago, # ^ |   0 secondthread sir told that's may be impossible sir. but you can provide your code, i can check that by using polygon which on failed (:
•  » » » 5 weeks ago, # ^ |   0 Can you tell why my top down dp giving the memory limit exceed ??for problem E
 » 5 weeks ago, # |   +1 We need more contests like this. Contests like today's destroy us and you pick us up. Thanks for organizing this man!
•  » » 5 weeks ago, # ^ |   0 True
 » 5 weeks ago, # | ← Rev. 3 →   +1 So, my understanding of the solution of $D$ is as follows:If $a$ and $b$ are given such that there are no common bits between them, the answer is $NO$, because there are no 2 integers $1 \leq c \leq a,$ $1 \leq d \leq b$ s.t. their xor will be strictly greater than the xor between $a$ and $b$.If $a$ and $b$ are given such that there are common bits between them, the answer is $YES$, because we can always find 2 integers $1 \leq c \leq a,$ $1 \leq d \leq b$ s.t. their xor will be strictly greater than the xor between $a$ and $b$.But I don't understand why this should always be true (i.e. for 2 integers $a$ and $b$ s.t. there are common bits between them, why is it that we can always find 2 integers $1 \leq c \leq a,$ $1 \leq d \leq b$ which don't have common bits between them, s.t. their xor will always be strictly greater than the xor of $a$ and $b$), can anyone please provide a more detailed explanation of this or a proof?Edit: deleted some erroneous stuff I thought was correct..; also, thanks a lot @doubleux, that last paragraph (especially) really made it very clear and obvious that the "strategy" for the solution of $D$ would always work.
•  » » 5 weeks ago, # ^ |   +1 Notice, that the maximum Xor between any two numbers is always less than their sum, the maximum arising when no two bits are common.Thus, if no bits are common, Xor of a and b is a+b, which is maximum that you can get using numbers less than them. Therefore no pair possible in this case.If the do have common bits, a Xor b will be 0 at that position. Now choose c same as a, while for d, change the bit at common position as 0. This will make that bit 1 in their bitwise Xor, thus making it larger.
 » 5 weeks ago, # |   +2 I used the same logic and approach in F but got TLE, why Python why :'-)Problem F submissionGreat tasks tho!
 » 5 weeks ago, # | ← Rev. 2 →   0 Rudro25 Can you please explain the tutorial for problem-A more clearly? It is not making any sense. [forgot to add that the problems were interesting!! ;) ]
 » 5 weeks ago, # | ← Rev. 3 →   0 Thanks
 » 4 weeks ago, # |   0 Why I am getting WA in problem E: 106721306
 » 2 weeks ago, # | ← Rev. 3 →   0 I used the chorus property. a^b=c -> a^c=b so (c^d = (a^b)+somenum) -> (c^((a^b)+somenum)=d) And did 1<=somenum<=10. But why +10 was enough I don't understand. can open my eyes?
•  » » 2 weeks ago, # ^ | ← Rev. 2 →   0 this is my submission.107902945
 » 2 weeks ago, # | ← Rev. 5 →   0 IGNORE