Stepavly's blog

By Stepavly, 5 weeks ago, translation, In English

1475A - Нечетный делитель

Problem authors: Stepavly, Supermagzzz

Editorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;

void solve() {
  ll n;
  cin >> n;
  if (n & (n - 1)) {
    cout << "YES\n";
  } else {
    cout << "NO\n";
  }
}

int main() {
  int t;
  cin >> t;
  while (t--) {
    solve();
  }
}

1475B - Новогоднее число

Problem author: MikeMirzayanov

Editorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>

#include <utility>
using namespace std;

using pii = pair<int, int>;

int main() {
  int test;
  cin >> test;
  while (test-- > 0) {
    int n;
    cin >> n;
    int cnt2021 = n % 2020;
    int cnt2020 = (n - cnt2021) / 2020 - cnt2021;
    if (cnt2020 >= 0 && 2020 * cnt2020 + 2021 * cnt2021 == n) {
      cout << "YES\n";
    } else {
      cout << "NO\n";
    }
  }
  return 0;
}

1475C - Бал в Берляндии

Problem authors: Stepavly, Supermagzzz

Editorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;

void solve() {
  int A, B, k;
  cin >> A >> B >> k;
  vector<int> a(A), b(B);
  vector<pair<int, int>> edges(k);
  for (auto &[x, y] : edges) {
    cin >> x;
  }
  for (auto &[x, y] : edges) {
    cin >> y;
  }
  for (auto &[x, y] : edges) {
    x--;
    y--;
    a[x]++;
    b[y]++;
  }
  ll ans = 0;
  for (auto &[x, y] : edges) {
    ans += k - a[x] - b[y] + 1;
  }
  cout << ans / 2 << "\n";
}

int main() {
  int t;
  cin >> t;
  while (t--) {
    solve();
  }
}

1475D - Очистка телефона

Problem authors: Stepavly, Supermagzzz

Editorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;

void solve() {
  int n, m;
  cin >> n >> m;
  vector<int> a, b;
  vector<int> v(n);
  for (int &e : v) {
    cin >> e;
  }
  for (int &e : v) {
    int x;
    cin >> x;
    if (x == 1) {
      a.push_back(e);
    } else {
      b.push_back(e);
    }
  }
  sort(a.rbegin(), a.rend());
  sort(b.rbegin(), b.rend());
  ll curSumA = 0;
  int r = (int)b.size();
  ll curSumB = accumulate(b.begin(), b.end(), 0ll);
  int ans = INT_MAX;
  for (int l = 0; l <= a.size(); l++) {
    while (r > 0 && curSumA + curSumB - b[r - 1] >= m) {
      r--;
      curSumB -= b[r];
    }
    if (curSumB + curSumA >= m) {
      ans = min(ans, 2 * r + l);
    }
    if (l != a.size()) {
      curSumA += a[l];
    }
  }
  cout << (ans == INT_MAX ? -1 : ans) << "\n";
}

int main() {
  int t;
  cin >> t;
  while (t--) {
    solve();
  }
}

1475E - Рекламное агентство

Problem authors: Stepavly, Supermagzzz

Editorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;

int mod = 1e9 + 7;

int fast_pow(int a, int p) {
  int res = 1;
  while (p) {
    if (p % 2 == 0) {
      a = a * 1ll * a % mod;
      p /= 2;
    } else {
      res = res * 1ll * a % mod;
      p--;
    }
  }
  return res;
}

int fact(int n) {
  int res = 1;
  for (int i = 1; i <= n; i++) {
    res = res * 1ll * i % mod;
  }
  return res;
}

int C(int n, int k) {
  return fact(n) * 1ll * fast_pow(fact(k), mod - 2) % mod * 1ll * fast_pow(fact(n - k), mod - 2) % mod;
}

void solve() {
  int n, k;
  cin >> n >> k;
  vector<int> cnt(n + 1);
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    cnt[x]++;
  }
  for (int i = n; i >= 0; i--) {
    if (cnt[i] >= k) {
      cout << C(cnt[i], k) << "\n";
      return;
    } else {
      k -= cnt[i];
    }
  }
  cout << 1;
}

int main() {
  int t;
  cin >> t;
  while (t--) {
    solve();
  }
}

1475F - Необычная матрица

Problem authors: Stepavly, Supermagzzz

Editorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;

bool check(vector<vector<int>> a, vector<vector<int>> const &b) {
  int n = (int) a.size();
  for (int j = 0; j < n; j++) {
    if (a[0][j] != b[0][j]) {
      for (int i = 0; i < n; i++) {
        a[i][j] ^= 1;
      }
    }
  }
  for (int i = 0; i < n; i++) {
    int need_xor = (a[i][0] ^ b[i][0]);
    for (int j = 1; j < n; j++) {
      if (need_xor != (a[i][j] ^ b[i][j])) {
        return false;
      }
    }
  }
  return true;
}

void solve() {
  int n;
  cin >> n;
  vector<vector<int>> a(n, vector<int>(n));
  vector<vector<int>> b(n, vector<int>(n));
  for (int i = 0; i < n; i++) {
    string s;
    cin >> s;
    for (int j = 0; j < n; j++) {
      a[i][j] = s[j] - '0';
    }
  }
  for (int i = 0; i < n; i++) {
    string s;
    cin >> s;
    for (int j = 0; j < n; j++) {
      b[i][j] = s[j] - '0';
    }
  }

  for (int times = 0; times < 2; times++) {
    if (check(a, b)) {
      cout << "YES\n";
      return;
    }
    for (int j = 0; j < n; j++) {
      a[0][j] ^= 1;
    }
  }
  cout << "NO\n";
}

int main() {
  int test;
  cin >> test;
  while (test-- > 0) {
    solve();
  }
  return 0;
}

1475G - Странная красота

Problem author: MikeMirzayanov

Editorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;

const int N = (int) 2e5 + 100;

int dp[N];
int cnt[N];

void solve() {
  int n;
  cin >> n;
  fill(dp, dp + N, 0);
  fill(cnt, cnt + N, 0);
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    cnt[x]++;
  }
  for (int i = 1; i < N; i++) {
    dp[i] += cnt[i];
    for (int j = 2 * i; j < N; j += i) {
      dp[j] = max(dp[j], dp[i]);
    }
  }
  cout << (n - *max_element(dp, dp + N)) << endl;
}

int main() {
  int test;
  cin >> test;
  while (test-- > 0) {
    solve();
  }
  return 0;
}
 
 
 
 
  • Vote: I like it
  • +127
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it +15 Vote: I do not like it

F was almost a duplicate of USACO's 'Left Out': http://www.usaco.org/index.php?page=viewproblem2&cpid=942 Really like the idea regardless

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    also it makes no sense to apply the same operation more than once (by the property of the xor operation).

    Can someone explain this line in the F editorial? I understand that applying the operation twice on the same row/column would again switch it back to the previous, but how applying the operation to a row, then to a column, and then again to the same row doesn't make sense?

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      bruh did you reply to my comment just so that it'd appear higher up lol? anyways, that'd be the same as just applying the operation to the column

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        Haha yes, plus this was the only comment regarding problem F. Thanks a lot, got it!.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    in E , i am having trouble while taking mod

    when i submitted without taking mod while calculating factorial then i got overflow. 106346070

    but when i changed and gave mod while calculaating factorial itself then , i got the answer as 0 106343305

    pls someone help me out.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hi! I'm still looking through your code, but maybe you can help me out: is it possible you're dividing factorials? I had the same issue, so if it's your case, too, than I can help.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        In my first attempt 106389327 I explicitly calculated factorials and divided them, and got the exact same error. In my case the mistake is that you can't divide mods. I fixed the problem by calculating pascal's triangle instead of factorials: 106392329. Probably you can still use factorials but you need to use some other things like this. I hope it will help.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hopefully the problems regarding servers get fixed before the next contest.

»
5 weeks ago, # |
Rev. 4   Vote: I like it +28 Vote: I do not like it

Thanks for the contest! I recorded my participation and narrated over it -- https://www.youtube.com/watch?v=0eZsX0BWtyY (video is done processing + I've added chapter timestamps).

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i can not understand your solution to problem c can you make it clear more !!!

»
5 weeks ago, # |
Rev. 2   Vote: I like it +27 Vote: I do not like it

Interesting problemset, not too tough nor too easy. It was definitely more on an easier end, but considering it was a Div3 I enjoyed it.

I especially liked the appearance of many different parts of CP and different topics, not just ad-hoc problems, e. g. binary search, dp, multiplicative inverse/binary exponentation, math, observation...

I think beginners can greatly benefit from this experience regardless of the long queue. Thanks to the problemsetters!

UPD: For those wondering where binary search appeared — apparently I overcomplicated the fourth problem and solved using binary search, Might have not been the best idea, but made it a nice problem for me. :P

»
5 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

i solved D using dp , never realized it could be done using binary search

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you please explain your approach?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    solution please!

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hey,I tried D with priority queues by making different queues more important and less important respectively. But it gave wrong ans with some case.

    This is my code https://codeforces.com/contest/1475/submission/105424077

    Any suggestion in code or logic will be helpful.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      you can see my solution. I have also used the same approach. https://codeforces.com/contest/1475/submission/105382749

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        if (r + r1 <= i)
                    {
                        ans += 2;
                        m -= i;
                        imp.pop();
                        reg.push(r);
                        // trace(i);
                    }
                    else
                    {
                        // trace(r);
                        ans++;
                        m -= r;
                    }

        Thanks brother got the error, I was doing m-=(r+r1) but acc. to your sol. r1 can be used afterwards or it may happen that it is not used. This is what i thought after seeing your solution, if anything else you wanted to add that you think of or proof of this pls share it would be very helpful in future contests.

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          no you got it right. It'a a fairly straight greedy problem. You just have to choose maximum memory you can delete with 2 convienience.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Try thinking about this test case:

      1
      4 8
      4 1 1 4 3
      1 1 1 2 2
      
      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        thanks got the error, i was subtracting two regular apps at a time but it should be one at a time.

        if anything you want to add or can we proof this observation, it would be helpful in future contest.

        Thanks

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    what are the DP states and state transitions used in your solution?

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      initially i calculated the sum of convenience points . divided the memory in two arrays based on the type of application and sorted both the arrays in ascending order . dp states were the convenience points, i calculated what is the maximum application memory that can be removed if i loose k convenience points . dp[i] stored the maximum memory possible , along with how many regular and important applications have been used for it. therefore dp[i] = {max,{index upto which regular have been used,index upto which imp has been used }},here i is the convenience points lost which is (index upto regular + 2*index upto imp) . for transition - dp[i] = max(dp[i-1] + maximum memory from regular array that can be used,dp[i-2] + maximum memory from imp array that can be used) then update the index of regular and important that have been used for that state . After the calculation , i just traversed over the array and found the first index where the memory >= m . here's my solution — https://codeforces.com/contest/1475/submission/105395940

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can you tell me why you choose the dp[i-2] route if both dp[i-1] and dp[i-2] are equal in your solution ?

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          dp[i-1] will store the maximum sum that can be achieved when i loose i-1 convenience points and dp[i-2] will store the maximum sum that can be achieved when i loose i-2 .so since i am loosing more convenience points in (i-1) rather than (i-2) , dp[i-1] > dp[i-2]. for example if i can loose 4 convenience points and the maximum sum achieved is a , and if i can loose 5 convenience points and the maximum sum achived is b , then b > a .

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    the subset DP approach? where you each cell in dp shows sum achieved with min convenience points.?

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      dp[i] stores the maximum sum achieved when we loose i convenience points . along with this it also stores the {index upto which regular applications have been used , ,index upto which important applications have been used} = {a,b} , so we can say that i = (a + 2*b).

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i have also solved it but it is giving me memory limit exceeded... as i am taking a dp of size dp[N][sum_of_all_elements] please reply Bhavyashah12050

    • »
      »
      »
      5 weeks ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      knapsack dp will give tle coz if n^2 and it will not fit in memory because the sum can be >=1e9 , it is not possible to make an array of this size , so instead iterate on the total sum of the convenience points , my approach was that to loose i convenience points we can say (i-2) + 2 or (i-1) + 1 , this is the maximum sum achieved at (i-2) points + add the highest important application which is available or maximum sum achieved at (i-1) points + add the highest regualar application which is available . this is how i made the transitions , along with this i also stored the index upto which regular and important applications were used . it was o(n)

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What will be the time complexity of last question??

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Time complexity of editorial solution for problem G is O(n.log(log(n))). But, you can solve it in O(n.sqrt(n)) by finding factor of every elements in a.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Time complexity will be O(N log N), because, each iteration we were adding N/i where, i is number iterations. In other words, N/1 + N/2 ... N/N ~= N*log(N).

»
5 weeks ago, # |
  Vote: I like it +28 Vote: I do not like it

My own set of video solutions, probably with some overcomplications (as usual...)

»
5 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Check out my explanations of problem F and G — solution

»
5 weeks ago, # |
  Vote: I like it +35 Vote: I do not like it

Screencast with narration + Solution Explanations: https://youtu.be/WynaHclse_4

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D if conveniences b[i]<=1e5 ?

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

My D is giving runtime error on 2nd case. exit code -12343838 something like this. I tried it for many test cases but it is giving me right output as well as i tried it for some cases which are shown for 2nd test-case also. It is working fine. Can anyone help me? submission: 105393105

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone want to increase their hack count??

Here you go.... 105318690

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem D, shouldn't 0-1 knapsack work? I did have a feeling that the convenience values of only 1 & 2 were important, but my initial intuition was to simply calculate the maximum convenience for memory up to (total memory of all applications — m). Then, the minimum convenience lost should be (total convenience of all applications — maximum convenience possible). My solution doesn't seem to work, but I am not sure why this solution would not work for all cases.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It sounds fine to me. Can you point out any case where it doesn't work or any code snippet with WA? I understand it may cause TLE but other than that sounds ok.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ah yes, it turns out I had a bug because I wasn't handling impossible case (-1) properly. Once I fixed that it seems to work, but it is very inefficient, as I am now hitting MLE and TLE as you predicted. I will try to optimize this solution, but I have a feeling I will just end up with the proposed solution in the editorial anyways. Good learning experience nonetheless!

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes. Knapsack makes sense with smaller constraints over N and M. These constraints don't look like typical knapsack constraints and usually when the problem is constrained in a new way (example each value is 1 or 2), then there is something else that must be taken advantage of.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I tried D with priority queues by making different queues more important and less important respectively. But it gave wrong ans with some case.

      This is my code https://codeforces.com/contest/1475/submission/105424077

      Any suggestion in code or logic will be helpful.

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I made a pair of power and convenience point and sorted it according to convince point but it also gave me the wrong answer.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    thought of the same approach but the constraints of m made me think of something else

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you share with problems like G where was O(N log N) trick?

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why can't we consider a number (say n) as it's own divisor in problem A? I mean a number is surely its own divisor! I don't think the problem setters have accounted for this, or am I missing something?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    There's no restriction like that allowing for prime numbers > 2 to pass

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I don't understand then why does 105409438 not work. Maybe you can help me realize my error?

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It probably has something to do with the following:

        Precision issues

        using == for comparing double

        the log function probably gives a not so accurate answer

        Try solving the problem without floats/doubles

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Noted & Thanks!

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In D why this does not works? Sort the array consistimg of all a[i] ( imp nd regualr both) in inc. order.

Select from beginning apps till the sum does not exceeds m. Then try to replace selected important apps by remaining regular apps.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Does your code work for this example? N=5, M=9

    A= 5 5 3 3 3 B= 2 2 1 1 1

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you tell how we can solve problem D by sliding window?? i solved it using binary search but want to know how will use sliding window.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks got that!

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anybody help me out with the difference between the 2 codes which are almost the same except for the fact in 1st I am directly using vector size and in the second submission I am saving the size in tmp variable and then using it: 105405168 [WA ON TC 7] 105408860 [AC]

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    size() returns an unsigned integer. It can give unusual output in case when size is 0 or in similar cases. So it is better to typecast it. When you stored the value in temp what you did was basically typecasted it to int and it worked fine.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

As many people are posting solutions on their youtube channel. I would love to see 15 minutes video from top performers like tourist. Hopefully he will add some contest video to his channel soon.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +85 Vote: I do not like it

    Just watch my video on 2x speed.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      My first question is hacked by n=1 but in question n>=2. Should I also consider cases which are not in input range

»
5 weeks ago, # |
  Vote: I like it -21 Vote: I do not like it
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

(Regarding Problem C)

Why does this TLE?

Also, in other sources for the same problem where I use a C-like array instead of std::vector (though this would also apply for std::vector, I think), why is it that occ[2][MAX_NR + 1] is considerably faster than occ[MAX_NR + 1][2] (514 ms. vs. 1357 ms.)? I kind of read about the difference between those two some time ago, but I didn't really remember much.., so it would be great if someone could perhaps give a link explaining this.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It TLEs because you are trying to allocate MAX_NR length for each test case, and there are 10^4 test cases.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't quite understand ' if(n & (n — 1))' in the solution to A. I did some research and found that the binary representation of any number that is a power of 2 is 10 to the i and the binary representation of any (power of 2) — 1 is a string of 1's the length of the power of 2 — 1. So performing an AND operation gives a string of 0's in the case that the input is a power of 2 and a string of 1's and 0's in the case that it isn't a power of 2. 1. How can that be used in an if statement? If it's 0's (i.e. the input was a power of 2), is that the equivalent of it being false, and the contrary for a string of 1's and 0's in the case that it isn't a power of 2?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Let's say $$$n$$$ is a power of $$$2$$$. Then, in base $$$2$$$, $$$n$$$ will look something like:

    $$$1000000\cdots000$$$

    and $$$n - 1$$$ will look something like:

    $$$0111111\cdots111$$$

    If we bitwise $$$AND$$$ these two, we obtain:

    $$$1000000\cdots000\space \&$$$

    $$$0111111\cdots111 =$$$

    $$$0000000\cdots000.$$$

    Which is equal to the representation of $$$0$$$, in base $$$2$$$. That is, if $$$n$$$ is a power of $$$2$$$, $$$n \space \& \space (n - 1)$$$ equals $$$0$$$. It's not hard to see this equals $$$0$$$ only if $$$n$$$ is a power of $$$2$$$. In all other cases, it will return some nonzero number. In a condition, $$$0$$$ evaluates to false, while any nonzero number always evaluates to true. Thus,

    if (n & (n - 1)) = if (false)
    

    when $$$n$$$ is a power of $$$2$$$, and

    if (n & (n - 1)) = if (true)
    

    when $$$n$$$ is not a power of $$$2$$$.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you for the thorough explanation! That cleared up everything. The reason I was particularly confused was that I didn't know that a binary number like, for example, 01010101110 (binary number after bitwise AND operation with non-base-2 number n and n-1), could be evaluated as true.

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Well, every number is represented in binary, internally. So, for example, you can have

        int x = 9 & (9 - 1);
        

        And $$$x$$$ will be equal to $$$8$$$, because the binary representation of the bitwise $$$AND$$$ between $$$9$$$ and $$$9 - 1$$$ is $$$1000_2$$$, which corresponds to the base $$$10$$$ number $$$8_{10}$$$.

»
5 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can anyone tell me what is binpow,bigmod,invfactorial.....(I saw them in some people's code)__ In problem E.I used simplified nCr,but it' giving WA

»
5 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

For problem E, I had a pure DP approach different from the editorial with no use of combinatorics, which I think works (at least I wasn't hacked yet if it wasn't the case).

Let's call $$$dp[i][j]$$$ the maximum number of followers we can get by choosing $$$j$$$ people in a prefix $$$[0,i]$$$ (the order of the array doesn't matter). Then let's also have another array $$$ways[i][j]$$$ which represents the number of ways to get to the amount of followers indicated by $$$dp[i][j]$$$. As a base case, it's easy to see that the maximum number of followers when choosing $$$0$$$ people is obviously $$$0$$$, and by that reason the number of ways of getting to that result is only $$$1$$$, so $$$dp[i][0] = 0, ways[i][0] = 1$$$ for all $$$i$$$. Then, we can calculate the value for the rest of the states: for each $$$i$$$ and $$$j$$$, $$$dp[i][j] = max(dp[i-1][j-1]+followers[j],dp[i-1][j])$$$. It means that the maximum amount of followers we can get by choosing $$$j$$$ people is already the calculated value for $$$j$$$ in the previous prefix, or choosing the blogger in position $$$j$$$ and adding the corresponding followers to the best way of choosing $$$j-1$$$ followers in the previous prefix. And $$$ways[i][j]$$$ is set to $$$ways[i-1][j-1]$$$ or $$$ways[i-1][j]$$$ in the first or second case respectively. Also, if we get to the case where $$$dp[i-1][j-1]+followers[j]$$$ is equal to $$$dp[i][j]$$$, then we add the corresponding ways from $$$ways[i-1][j-1]$$$ to $$$ways[i][j]$$$, applying $$$\%MOD$$$ to avoid overflow.

Just to be clear, I changed a little bit the wording from what I really implemented so it was easier to explain, but the idea is very similar. Here's the submission: 105415244

»
5 weeks ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

IMO easier solution for B: make a bool array DP length of the maximum possible n(1e6, as I remember) and fill it with false. Then make dp[2020]=dp[2021]=true. And for each number in [4040, 1e6] if dp[i — 2020] or dp[i — 2021] is true, than dp[i] = true. This basically means “if it is possible to reach B”. And then for each test case just print dp[n] ? Yes : No!

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone stuck at D , can watch this https://youtu.be/c7h4hUdXX1E

»
5 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Hello I use greedy to solve problem D :)

if max1_type2 > max1_type1 + max2_type1:
     choose max1_type2
else
     choose max1_type1

you can see my code here : https://codeforces.com/contest/1475/submission/105374802

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for contest, I thought D, F and G were very nice problems for beginners.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Another solution for B that is simpler I guess is to notice that (2021 — 2020 = 1) as U can make any number using only (1's), U can take as much as possible of 2020, if after that (n) equals to (2020 * taken_count), that's the answer, else I just check if the remaining is less than or equal to the count of (2020's) I've already taken to check if I can fill the missing value with (1's) (Simple enough ^^)

int taken = n / 2020, remaining = n % 2020;
cout << ((remaining <= taken)? "YES" : "NO") << endl; 
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I knew it had to be simple, why do editorial providers on codeforces insist on making editorials extremely hard. This was simple!

»
5 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can anyone share a more formal proof of F? Why are 2 cases handled in the solution? What is this 'times' variable?

Here is my current algorithm with logic:

  1. We have 2*N control variables: The flip of each row, and flip of each column. Each variable can be 0 or 1 (as the order doesn't matter)

  2. Elements in first row are determined only by the flip of 1st row and flip of all columns. So we look at all possible cases for this that can make first row of A equal to B. We do this for 2 cases: one where first row of A is flipped, one where it isn't. (note that the columns flipped in 2 cases will be complement of each other)

  3. Now, the flip or not of each column is fixed based on step 2. So only remaining variable is flip of each row other than 1st row. We can decide flip of each row by looking at first element in the row. Now all our variables are determined. At this point, A must equal B if the solution exists, in at least 1 of the 2 cases.

  4. But do we need to check both cases? In case 2, the flip of each row and column will be opposite to the flip of each row and column in case 1. Therefore for each(Row,column) pair (i,e. cell). The result will be the same in either case. Therefore, it suffices to check only 1 case.

  5. I follow this deterministic setup: where i first set first row of A as same of B by flipping columns (selecting the case where first row doesn't need flip). Then.I set first column of A as same of B by flipping rows. Then I check the other elements. Based on arguments in 1-4, this is sufficient.

Please help if I am overcomplicating this and there is a simpler understanding.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sorry for that I will not answer your post, instead I'll describe my solution, because I don't understand editorial.

    You should know from properties of XOR order does not matter, so we can reorder all operations into: perform all XORs of rows, and then all XORs of columns. Now, if any of operations is done twice then you can do nothing instead. Therefore you need to know for each of row and column do you need to perform corresponding XOR or not.

    For any cell in matrix after all XORs performed value will be changed or not. So, you can make matrix of "should I change value or not" — this is actually XOR of both matrices. You could also came up with this idea if you think of question "with what I should XOR to get from matrix A get matrix B?" Let's call this matrix C! So, C = A XOR B. Also C is "what cells should I flip?". This leads us to following equal problem: if you can make C matrix from zeroes matrix, then you can make B matrix from A matrix.

    How to figure out can we make C matrix from zeroes? Well... Let's split into two cases. Case 0: we don't need to XOR first row, then 0 and 1 in this row tells us: should we invert column or not. If any other row is same (identical, all 0 and 1 match first row) then after performing all columns XORs we get all we need. Otherwise, to be able to make it from zeroes, the only chance we have is to perform XOR of those rows, and to be able to make them they should look like our first row inverted.

    Case 1: we need to XOR first row, then 0 will tell that we should invert this column, and 1 tell us to not invert. And similarly, if we see same row somewhere else, then we just perform XOR of row and after all XORs of columns we get what we need. And for other rows, the only chance to make them is to NOT invert them, this means they should look like our firs row inverted.

    In both cases all rows of matrix C should consist of row 1 and inverted row 1. Therefore, solution is following: make matrix C, check that all rows is either identical to row 1 or identical to inversion of row 1.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you very much. I understand much more clearly now

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I have a very simple solution, got idea from comment section itself-

        one observation is that we can't apply same operation multiple time in a row or column. So basically we can fix one row/column(let's say row 0) and will check one time by taking XOR of this row and second time without taking XOR.

        Here is implementation — https://codeforces.com/contest/1475/submission/107153476

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Thanks to Stepavly and Supermagzzz. The contest went well, but unfortunately, it was delayed.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone Please help me,why I'm getting WA in problem c In case 3:( i think my idea is totally fine :)

105363911

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

For Problem G,why let the $$$\mathcal{O(\sqrt{n})}$$$ finding divisors algorithm pass!!!

»
5 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

For problem G, can someone please explain why is it incorrect to calculate dp in reverse. Why dp[i]=max(dp[i], cnt[i]+dp[i*j]) where i*j < 2e5 wrong? 105437344

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    1
    1
    200000
    You might get a TLE anyways.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for pointing out the bug. Complexity is O(NlogN), so didn't get TLE. Accepted solution: 105442203 (doesn't require the extra step of applying sieve)

»
5 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it
  • Hi everyone can anyone please suggest why this solution is not passing all the testcases. My idea is to use log aprroach---> z=log2(x) if z is an integer then the x is power of 2 else it must contain an odd number as is its divisor.
  • for example
  • if z is = 3.22.. then z is not exactly a multiple of 2
  • if z is = 3 the z is exactly a multiple of 2
  • My soultion get failed on test case 2 (8029th token)
  • code link : — > https://codeforces.com/contest/1475/submission/105435613
  • Thanks for your help
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why I get 'uninitialized value usage' error https://codeforces.com/contest/1475/submission/105439474?

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Usually I won't touch E, but this Problem E was pretty easy in this way..https://codeforces.com/contest/1475/submission/105444607

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello everyone i just want to share my approach for problem C. I used maps to solve this problem. I stored the frequency of boys and girls and also pair of a boy and girl. Now if we want to calculate how many other couple can go with current couple. Say a is boy and b is girl we have in current couple. Then the number of couple that can go with a and b are Total couple-frequency of a in boys -frequency of b in girls + frequency of pair a, b. And do this for all couple and just divide the answer by 2 because we will count every couple 2 times.

105342359 Check this submission.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

105451015 I am unable to figure out what is wrong with my submission please help

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I just finished my virtual for the contest. I was analyzing my solution for F and found a mistake. But that code had already passed system tests.

105447780

The mistake I found is that I have done this operation:

(1<<1000).

This operation is not practically correct but somehow is giving correct result.

I think the System Tests are weak coz this solution should not have passed.

»
5 weeks ago, # |
Rev. 3   Vote: I like it +3 Vote: I do not like it

I'd like to propose a super simple solution for F. Just scan every 2x2 square and count the number of difference in A matrix and B matrix in matching positions, if there exist a 2x2 square in which the count of different numbers is 1 or 3, output NO, otherwise output YES. I got AC but hasn't been able to prove why. I just feel like different numbers can never come in a single square surrounded by same numbers or create an L shape.

Here is my solution, who can prove why this is correct? https://codeforces.com/contest/1475/submission/105455476

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I tried D with priority queues by making different queues more important and less important respectively. But it gave wrong ans with some case.

This is my code https://codeforces.com/contest/1475/submission/105424077

Any suggestion in code or logic will be helpful.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
»
5 weeks ago, # |
  Vote: I like it -6 Vote: I do not like it

if anyone is still struggling with the problems, here is the video solutions to the last 5 problems. Primarily hinglish for now. Do let me know if this was helpful for you! Thankyou!

CODEFORCES ROUND 697

Problem C — https://youtu.be/kflXYDwum4k Problem D — https://youtu.be/oroRk1Ev5yY Problem E — https://youtu.be/dd0EOuUIYOQ Problem F — https://youtu.be/wjQknVeioec Problem G — https://youtu.be/UZjTR_NJEZ4

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem G, why can't we replace the N with max element in array a(for each test case)?

»
5 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Comment Retracted

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can any one tell why this method is giving TLE: Problem E: https://codeforces.com/contest/1475/submission/105468999

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I am new to cp, in the problem 3 I was able to follow the editorial to the very end but I didn't get why we are printing ans/2 instead of ans

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    we are counting each pair twice. We are fixing one pair and seeing all possibilities of second pair. But this first pair will also be counting again when its corresponding second pair is fixed.

    If you are doing a different solution where you are counting each pair only once, then you don't need to divide by 2

»
5 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

For Problem C, What is wrong with this Solution? I stored the number of times a particular boy or girl is present in more than one pair and calulate the invalid group of pairs. For Ex- If a 'b' boy is present in n pairs, then invalid group of pairs is going to be (n*(n-1))/2

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

O(1) solution for Problem B

Link to the solution

»
5 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Damnn, Quesion D was really-really fun :D, learned a lot from it, very very thankful to the problem setters...

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

please someone help, from last 2 months i started codeforces and i am not able to improve my performance yet i am a on a beginner level, I think the problems on codeforces are on little mathematics side. can anyonle please help me , and suggest me some resources for solving mathematical problems.

»
5 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

problem B had a much simple solution. my solution: 105333636

Approach: Let N be the given number and X be N modulo 2020. if X is 0 then we can say that N was sum of certain number of 2020 and if X is not 0 then we check whether X is less than or equal N/2020 if it is then we can put a combination 2020 and 2021.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I am getting WA in fourth question, my approach is almost exactly as shown in this editorial code.

Can someone tell me where I am wrong? https://codeforces.com/contest/1475/submission/105487065

»
5 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

Editorial for 1475G - Strange Beauty is masterpiece of utterly bad editorial. Why? dp[x] is following. Here is formula. No explanations at all, why there would be numbers like that, why they indeed pairwise ok and so on.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How i can solve the problem D use DP !!

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone Please explain how to solve E using Dp . :)

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Ez B

ll q;
cin>>q;
(q%2020<=q/2020)?cout<<"YES\n":cout<<"NO\n";
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem D, I used prefix sum + binary search and got AC, Can anyone share DP approach of problem D??

»
5 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me understand why I got TLE?

contest : Codeforces Round #697 (Div. 3) problem : C. Ball in Berland problem link : https://codeforces.com/contest/1475/problem/C

TLE solution : https://codeforces.com/contest/1475/submission/105347180

I resubmit same code. But I got AC AC solution : https://codeforces.com/contest/1475/submission/105608300

Why did this happen?

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I solved B using this logic :

Ans = (n/2020 >= n%2020)? Basically, if this is the case, I can replace reqd no. of 2020s with 2121s.

Accepted solution.

Any issues in this approach ?

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What does it mean to block edges in a graph?

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In Problem D how the editorial solution will work for test case a=[5 3 2 1 4] and b=[1 1 1 2 1] and m=7 the answer should be 5+2=7 and we lose 2 convinience points.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem C, I'm getting a TLE on test case 2 in this solution. Can anyone please help me??

#include<bits/stdc++.h>
#define ll long long int 
#define REP(i,x,y) for(long long i=x;i<y;i++)
const int N = 4e5+5;
using namespace std;
int main()
{
  //fast;
  ll t;
  cin>>t;
  
  while(t--)
  {
    ll a,b,k;
    cin>>a>>b>>k;
    ll n=a+b;
    vector<ll> u(N);
    vector<ll> v(N);
    vector<ll> sz(N,0);
    REP(i,1,k+1)
    {
        cin>>u[i];
        sz[u[i]]++;
    }
    REP(i,1,k+1)
    {
        cin>>v[i];
        sz[v[i]+a]++;
    }
    ll ans=0;
    REP(i,1,k+1)
    {
      ans+= k - sz[u[i]] - sz[v[i]+a] + 1;
    }
   
    
    cout<<ans/2<<endl;
    




      
  }
  return 0;
  
}
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone tell me what is the problem in my code because it was saying TLE on test case #2. Here is my code

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to approach problem D using DP ?

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Stepavly In the problem C why did you first decrement the x and y and then increment a and b

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Decrement to make indexing from zero, increment to count degree of the vertices.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

in E , i am having trouble while taking mod

when i submitted without taking mod while calculating factorial then i got overflow. 106346070

but when i changed and gave mod while calculating factorial itself then , i got the answer as 0 106343305

pls someone help me out.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    division doesnt work well with modulo operator, you have to use the modulo inverse instead. tho you could build pascals triangle instead, its a much simpler approach than calculating modulo inverses

»
3 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

for problem F, i found a different solution, however i am unable to prove why this solution must be true.

notice that for each n x n matrix, if we take the matrix of differences (if a[i][j] != b[i][j] for all i and j) each 2 x 2 matrix contained within it can always also be created from a zero 2 x 2 matrix using the two operations given.

for example:

1 1 0
0 0 1
1 1 0

contains:

1 1
0 0

1 0
0 1

0 0
1 1

0 1
1 0

these are all possible to create using the vertical and horizontal xor operations from an empty 2 x 2 matrix. you can check them yourself.

so the solution is to check each 2 x 2 matrix for this rule, and if they all work, the answer will be YES, otherwise NO.

however, i was not able to prove why this always works out. could anyone prove this? my solution: here

»
3 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I tried D using DP but getting MLE, It passes all test cases but fails on large input value https://codeforces.com/contest/1475/submission/107084258 Any solution??

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    M goes upto 10^9, you cant use that much memory.

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I feel problem-B more easier to use these codes.

include<bits/stdc++.h>

using namespace std; int main(){ int n; cin>>n; while(n--){ int k; cin>>k; int s; s=k/2020; if(k>=s*2020&&k<=s*2021)cout<<"YES"<<endl; else cout<<"NO"<<endl; } return 0; }