TWOGRS - Editorial

editorial
, , , ,
43

You should provide the link of your solution or format it correctly.
Just copy and pest your code between ``` and ```

\```
Code here
\```

[Without back slash \]

44

Ready my editorial for detailed explanation :slight_smile:

46

Umm,Better explained :heart_eyes:

Have some similarity with my logic:

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int main() {
  ios_base::sync_with_stdio(false); cin.tie(NULL);
  ll t; cin >> t;
  while (t--) {
    ll a, b, c; 
    cin >> a >> b >> c;
    if ((a + c) % 2 == 0) {
      if (a > 0 and b > 0 and c > 0)
        cout << "YES" << "\n";
      else if (a + b == 0 or a + c == 0 or b + c == 0) {
        if ((a + b + c) % 2 == 0)
          cout << "YES"<< "\n";
        else
          cout << "NO" << "\n";
      } else if (a == 0 and b > 1) 
        cout << "YES" << "\n";
      else if (b == 0 and a > 1) 
        cout << "YES"<< "\n";
      else if (c == 0)
        cout << "YES"<< "\n";
      else
        cout << "NO" << "\n";
    } else
      cout << "NO" << "\n";
  }
  return 0;
}
47

https://www.codechef.com/viewsolution/26744442
how can these solution pass all the test case o(3*1e9) complexity ??

2 Likes
48

s = 1A + 2B + 3C
=> (2-1)A + 2B + (2 + 1)C
=> 2(A +B + C) + (C-A)
NOW
S/2 = (A +B +C) + (C-A)/2
entire problem depends upon weather c-a is even or not
just run a loop that sees if c-a is even then calculate S based upon above equation, i suppose it might work

49

Omg…this is some serious stuff here…

50

@anon55659401 is there any proof for that 2nd point you have written

1 Like
51

There is the detailed proof in the editorial I wrote.

1 Like
52

where it exactly is?
@anon55659401

55

Can you please explain tester’s solution ?

56

Any testcase for this code , I am getting WA someone please suggest one test case @ taran_1407
https://www.codechef.com/viewsolution/26729140

57

It is not working actuallyyyyyyyyy

58

Your approach is not correct bro check for number of 1’s 2’s and 3’s you are limiting that your groups will have same number of elements but my test case (0,3,2) will not go along with your approach see {2,2,2}and {3,3}, this case should result YES but it will output NO in your code

1 Like
59

Bro basically this problem is Subset problem of “Partition of a set into K subsets with equal sum” (Partition of a set into K subsets with equal sum - GeeksforGeeks ) where k=2 and approach in above code is just partitioning

60

https://www.codechef.com/viewsolution/26746245
Here is the link of my code.

61

@taran_1407 can you explain how j and jj are been used in editorialist solution ?

62

Hi,

I am unable to get this statement below :
mask < (1 << sum)

Could you please explain?

Thanks

63

That is incorrect because the time complexity of that solution is exponential, that solution passed because of weak test cases.

@taran_1407 @vijju123 please look into this matter and add it in the post that many solutions with exponential time complexity passed because of weak test cases or else their solution was wrong, so the beginners don’t go on the wrong track !

1 Like
64

@vibhoragrawal You should format your code or share your solution link for better alignment. Use three backticks ``` then press enter and write your code, when finish your code press enter and three backticks ``` again.

Example:
```
Code
```

65

@tushar0609 Check out the following test cases:

0 1 52
0 1 100
0 1 98

Your code just failed for a = 0 condition, Here is a logic to solve it:

if ((a + c) % 2 == 0) {
    if (a == 0 and b > 1)
      cout << "YES"<< "\n";
    else
      cout << "NO"<< "\n";
  }
//You must use your logic for two of a, b, c are 0 before checking a = 0

My logical solution here