One sentence, that I will be downvoted, but saying true

→ Pay attention

Contest is running
Codeforces Round 995 (Div. 3)
02:06:56
Register now »

→ Streams

Codeforces Round 995 Solution Discussion

By aryanc403

Before stream 02:11:55

View all →

→ Top rated

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

Countries | Cities | Organizations

View all →

→ Top contributors

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

View all →

→ Find user

→ Recent actions

Detailed →

I_am_Drew's blog

One sentence, that I will be downvoted, but saying true

By I_am_Drew, history, 4 years ago, translation, In English

C1-C2 (div2) The shittiest problem of the November 2020 on CF

+356

I_am_Drew
4 years ago
81

Comments (74)

Show archived | Write comment?

basketballer

4 years ago, # |

agree

→ Reply

Aditya_Sharma

4 years ago, # ^ |

Such problems may lead a good coder to think (for a few hours) whether he/she really is a good coder.

Long implementation problems hurts a lot to brains.

→ Reply

Mridul323

4 years ago, # |

+22

Felt like solving Codechef long challenge problems.

→ Reply

Yukuk

4 years ago, # |

← Rev. 2 →

Agree. I think, almost everyone was solving it the whole contest and didn't have time to even think about solution of D and E

→ Reply

sevlll777

4 years ago, # |

-151

please downvote him

→ Reply

TheScrasse

4 years ago, # |

+85

C1-C2 (div2) The shittiest problem of ~~the November~~ 2020 on CF

→ Reply

keklol45

4 years ago, # ^ |

+60

C1-C2 (div2) The shittiest problem on CF

→ Reply

Candidate_Master_2021

4 years ago, # ^ |

+57

C1-C2 (div2) The shittiest problem to come out of polygon

→ Reply

Drew_is_me

4 years ago, # ^ |

+43

C1-C2 (div2) The shittiest problem

→ Reply

tem_shett

4 years ago, # ^ |

+78

C1-C2 (div2)

→ Reply

MikMirzoyanov

4 years ago, # ^ |

+70

C1-C2

→ Reply

Yukuk

4 years ago, # ^ |

+42

→ Reply

MarkZuckerberg

4 years ago, # ^ |

+40

→ Reply

Elegy_No_Programmer

4 years ago, # ^ |

+109

→ Reply

rotavirus

4 years ago, # ^ |

+52

C'est la vie

→ Reply

Why_am_i_here_

4 years ago, # ^ |

+13

-(C)

→ Reply

Ahmed_Solyman

4 years ago, # ^ |

-9

C1 and C2

→ Reply

snorkel

4 years ago, # ^ |

C(1-2)

→ Reply

snorkel

4 years ago, # ^ |

-13

C(-3)

→ Reply

snorkel

4 years ago, # ^ |

-8

-3C

→ Reply

arham_doshi

4 years ago, # ^ |

+20

no there was one long which had more shitter problem than this. It was about calenders and which day of the week the given day was.

→ Reply

nickcotforce

4 years ago, # ^ |

C1-C2 (problem) The shittiest div2 on CF

→ Reply

sam571128

4 years ago, # ^ |

-14

C1-C2(Div2) The shittest problem in the history of CF.

→ Reply

dca

4 years ago, # |

+26

Sometimes I feel amazed to see that so many Div1 participants solved C1/C2 in just 10 minutes

→ Reply

AtomicCoder

4 years ago, # ^ |

+52

That's why they are in div1

→ Reply

Dean_student

4 years ago, # |

+44

This problem is strong contender for most bullshit problem of the year. I have a strong feeling antontrygubO_o would have never allowed that.

→ Reply

pkhaustov

4 years ago, # |

+17

+1 to you, but I can't fully agree with it. Still think that problem Div1B is shitty enough to compete with Div1A.

→ Reply

Dean_student

4 years ago, # ^ |

I could not vote for 1B because i wasted complete 2 hrs fixing the bug in 1A and in the end found it was one ! which shouldn't be there. I decided that i will upsolve 1B but that i have changed mood after seeing your comment.

→ Reply

Q101

4 years ago, # |

-19

Was it the shittiest because you couldn't solve it?!

→ Reply

I_am_Drew

4 years ago, # ^ |

+13

Of course not. I solved C1, C2 — not. So, not solving a problem — it's not the parametr of the shittiest problem...

→ Reply

Q101

4 years ago, # ^ |

-45

So what's the reason? (Cause I found them interesting)

→ Reply

not-an-alt

4 years ago, # ^ |

+14

How the hell can you find a 200+ lines implementation problem with nothing to learn from it, with 20+ if-else/s and dozens of corner cases interesting. Just because you are from the same country as the authors ? Even you couldn't solve C2. Just wasting 2 hours straight on a case-handling problem in no way interests anyone

→ Reply

Q101

4 years ago, # ^ |

-31

Hmmm... so how do you explain this? It's less than 35 lines.

→ Reply

Len

4 years ago, # ^ |

Because it's a C1 solution?

→ Reply

Q101

4 years ago, # ^ |

Check this out. It's not even 100 lines :|

→ Reply

amarnathsama

4 years ago, # ^ |

The point isn't if it CAN be implemented in fewer lines, it's if the approach people are generally going to go with is even feasible for the difficulty or not. The target for this question was to add a distinction in skill between say a pupil and a specialist /expert(or something similar), if an overwhelming majority of these people are only able to solve it using 200+ lines of code then the fact that it can be implemented in much less is irrelevant.

→ Reply

SuperJ6

4 years ago, # ^ |

No, the point is that your overly whining because you haven't had enough practice in another what I believe is a significant part of cp, being able to implement efficiently and nicely.

Here's my code that was how I did it naturally my first time. Not saying it's great, or that the problem was that exciting, but it's not close to 200+ lines, and I knew it was bound for people to be overly rated without being well rounded in all skills cp.

→ Reply

amarnathsama

4 years ago, # ^ |

Did you even read my comment? I never said anything about it being a good or bad problem (even tho i hated it), it was about how bringing up randomn submissions with fewer lines doesn't change the fact that for most people in the skill group, that was implementation hell, your code has a lot of copy paste in it too, and while I'm sure implement is an important skill, you fail to understand that for the people that the question was for(pupil to expert or similar), it was JUST TOO HARD to implement because of the things mentioned above. I'm sure I and a lot other people are shit at a lot of skills essential for cp but out of all those things that we fail to do in contests this is the one on which (relative)outrage is happening, why? I don't think it's as simple as GIT GUD.

→ Reply

SuperJ6

4 years ago, # ^ |

Did you even read my comment?

Did you even read my comment? I said it was because people in your skill group aren't being exposed to enough implementation recently, which is supposed to be an easier skill in cp, not too hard, and that is why there is much more outrage. Also this is all I pretty much ever copy paste:

Code

/*
This is code of SuperJ6 for Codeforces.
Don't copy my code during f*kin' contests.

2.71828182845904523536
*/

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
#define endl '\n'
#define ll long long
#define pi pair<int, int>
#define f first
#define s second

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	

	return 0;
}

Besides the template which is shorter than yours, the cp people I talk to will all say I don't copy paste, I just practice implementing short...

→ Reply

Elegy_No_Programmer

4 years ago, # ^ |

amarnathsama What do you even mean? Isn't implementation a necessary skill in CP ?

→ Reply

amarnathsama

4 years ago, # ^ |

Yes, it is, among others.

→ Reply

Dean_student

4 years ago, # ^ |

I don't think that is the reason because i also didn't solve D,E,F.

→ Reply

_mndm

4 years ago, # |

← Rev. 2 →

+10

my solution of C1 was nearly 800 lines -_- -_-

→ Reply

Swistakk

4 years ago, # ^ |

+89

Not sure if you realize that, but that tells worse about you rather than about problem :P

→ Reply

SkyDreams

4 years ago, # |

I didnt even read D :( , thank you d2-c2

→ Reply

viwreck

4 years ago, # |

Then there exist people like me who realized C1 was worth less points than B after solving it

I guess problem setters prioritize brute force less.

→ Reply

Not-Afraid

4 years ago, # |

and i am still debugging my solution to C2. WA on testcase 2, test 48 (:

→ Reply

amurto

4 years ago, # ^ |

Let me know as well, if you get that testcase 48. I dont know how to check that.

→ Reply

Not-Afraid

4 years ago, # ^ |

1 2 3 111 110

→ Reply

sevlll777

4 years ago, # ^ |

← Rev. 2 →

I guess your solution fails test with just 3*3 square where all symbols are equal to 1

→ Reply

SkyDreams

4 years ago, # ^ |

I have the same wa on pretest two and the case is I think a 3*2 or 2*3 grid because my code prints the answer as 7 where the limit is [0,6] for the total moves

→ Reply

amurto

4 years ago, # ^ |

← Rev. 2 →

No, its this test case. This returns 7 moves for my code. I solve the left 2x2 grid and then right 2x2 grid

1
2 3
111
110
11 -> 01 -> 10 -> 11 -> 00
11    00    01    10    00
first 2x2 in 4 moves
then we have
001
000
So then I solve 01 in 3 moves, total of 7 moves.
                00
Am I missing something or is my implementation wrong? All other 2x3 test cases return moves <= 2*3

→ Reply

sevlll777

4 years ago, # ^ |

← Rev. 3 →

If you Will fix 2*2 aquare, where number of 1 is less (or equal) then in another, firstly, and another 2*2 square after this, it Will be not more than 6 moves always.

It is a trick that helps avoid this case, in generally yours implementation correct

→ Reply

_mndm

4 years ago, # ^ |

← Rev. 2 →

mine 48 too..and i know my solution are exceeding n*m in most of odd n * odd m containing all '1' cases

→ Reply

Radewoosh

4 years ago, # |

+301

Not agree. I have another sentence that will be downvoted, but is true: "think two times, so you won't have to code three times".

→ Reply

mesanu

4 years ago, # ^ |

preach

→ Reply

bleh0.5

4 years ago, # ^ |

+81

imagine being lgm and thinking you're gonna get downvoted

→ Reply

asfd221

4 years ago, # ^ |

+16

Its a relative terminology they often use. Had he commented "Hi" he would get 500 upvotes at least.

→ Reply

ffao

4 years ago, # ^ |

← Rev. 2 →

+87

Maybe I would agree with you if you had some clever solution that wasn't painful to code.

But no, I opened it and it is 174 lines (after I deleted the template!), full of copy-paste and +1 -1 in lines like zrob({i, j}, {i+1, j}, {i+1, j+1});. Anyone trying to code like this that isn't 90% as good at implementation as you would have made at least 20 mistakes.

→ Reply

Makise_Kurisu

4 years ago, # |

A neater implementation to problem Ca

CODE

#include<bits/stdc++.h>
#define vi vector
#define pb push_back
#define ar array 
using namespace std ;
void solve(){
  int n,m ;cin >> n >> m ;
  vi<string>a(n) ; 
  for(string &x:a) 
    cin >> x ; 
  vi<vi<ar<int,2>>>ans ;
  function<void(int,int)> fix=[&](int i,int j){
    vi<ar<int,2>>o,z ;
    for(int r=0;r<2;r++)
      for(int c=0;c<2;c++){
        if(a[i+r][j+c]=='1')
          o.pb({i+r,j+c}) ;
        else 
          z.pb({i+r,j+c}) ;
      }
    if(o.size()==0)
      return  ;
    a[o[0][0]][o[0][1]]='0' ;
    if(o.size()==1 || o.size()==2){
      a[z[0][0]][z[0][1]]='1' ;
      a[z[1][0]][z[1][1]]='1' ;
      ans.pb({o[0],z[0],z[1]}) ;
    }
    if(o.size()==3 || o.size()==4){
      a[o[1][0]][o[1][1]]='0' ;
      a[o[2][0]][o[2][1]]='0' ;
      ans.pb({o[0],o[1],o[2]}) ;
    }
    fix(i,j) ;
    return ;
  } ;
  for(int i=0;i<n-1;i++)
    for(int j=0;j<m-1;j++)
      fix(i,j)  ;
  cout << ans.size() << '\n' ;
  for(auto x:ans){
    for(auto y:x)
      cout << y[0]+1 << " " << y[1]+1 << " " ;
    cout << '\n' ;
  }
}
signed main(){
  int t ;
  cin >> t ;
  while(t--)
    solve() ;
}

→ Reply

AlexFetisov

4 years ago, # |

+17

What's wrong with that one? Seems that it is yet another ad-hoc regular CF problems that we have in all rounds. I wonder then, why authors though that A2 is 500 only. If that were 500-1000, I would say pretty good one, or just kill A1 and do A2 as B 1250 (implementation with lots of potential bugs) and create a good 500 A.

On the other hand, B was complete shit though.

→ Reply

WolfBlue

4 years ago, # |

Link for posteriority https://codeforces.net/contest/1440/problem/C1

→ Reply

endless_summer

4 years ago, # |

looks like many people felt that way but isn't quick implementation an essential skill to have? or am i missing something here?

→ Reply

oversolver

4 years ago, # |

But I see its upvoted.

So it is false?

→ Reply

Eason_AC

4 years ago, # |

Be confident guy, delete "the November 2020 on" and it'll be "C1-C2 (div2) The shittiest problem of CF". That makes sense, doesn't it?

→ Reply

Gassa

4 years ago, # |

+33

A problem such as this is, as any other, a learning opportunity. In this case, an opportunity to learn how to think of the least painful implementation, before starting to code. And, importantly, when to stop thinking and go back to coding.

There are different genres of contest problems. For example, if we group by the general question, there are "how to do it at all?", "how to do it efficiently?", and then there is "sure it can be done, but how to code it, reliably, so that it will work in the end?". Personally, I find the latter genre somewhat appealing as well as others, and generally applicable outside of algorithmic problem solving.

The butthurt it causes, like this original post, can be seen as an added perk by some authors. Still, a contestant willing and able to learn could turn the pain into a learning experience.

→ Reply

pkhaustov

4 years ago, # ^ |

+10

Yes, I think the main trouble is about these problems weren't used for ACM-style contest, where they would be very appropriate. Instead of this, the problems were used for CF round and the main portion of negative feedback should be mostly addressed to the CF coordinators, who must have a good understanding of how the tasks are suitable for the CF round. If I saw problems Div1A, Div1B, Div1C in ACM-style contest, I would not say anything wrong about them.

→ Reply

newbie_to_newbie

4 years ago, # |

-34

Downvote me!!! ORZ!!!

→ Reply

Eason_AC

4 years ago, # ^ |

← Rev. 2 →

-16

[Deleted]

→ Reply

SPyofgame

4 years ago, # |

← Rev. 2 →

If guys dont mind, I have some implementations with comments here

Problem C1 - Eliminate each 1x1 cells

#include <algorithm>
#include <iostream>

using namespace std;

#define all(x) (x).begin(), (x).end()
int main()
{
    int q;
    cin >> q;
    
    while (q-->0) /// For each query
    {
        /// Input
        int n, m;
        cin >> n >> m;
        
        string s[n];
        for (int i = 0; i < n; ++i)
            cin >> s[i];
            


        /// Calculation
        int cnt = 0;
        for (int i = 0; i < n; ++i)           /// For each '1' appear
            cnt += 3 * count(all(s[i]), '1'); /// We use 3 operations to turn off it
                                              /// These operations are independent
 
        /// Output the result
        cout << cnt << '\n';
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < m; ++j)
            {
                if (s[i][j] == '1')
                {
                    int cx = i + 1; /// +1 because we use 0-based loop
                    int cy = j + 1; /// +1 because we use 0-based loop
                    int px = (cx < n) ? cx + 1 : cx - 1; /// Next row
                    int py = (cy < m) ? cy + 1 : cy - 1; /// Next col

                    /// Notice that these operation are independent
                    /// They wont affect others cells, just turn off [i][j]

                    cout << px << ' ' << cy << ' ';  ///  X O  |  + +  |  O X
                    cout << cx << ' ' << py << ' ';  ///  O O  |  + _  |  X O
                    cout << cx << ' ' << cy << '\n'; ///   Operation: 1 -> 2

                    cout << px << ' ' << cy << ' ';  ///  O X  |  + _  |  X X
                    cout << px << ' ' << py << ' ';  ///  X O  |  + +  |  O X
                    cout << cx << ' ' << cy << '\n'; ///   Operation: 2 -> 3

                    cout << cx << ' ' << py << ' ';  ///  X X  |  + +  |  O O
                    cout << px << ' ' << py << ' ';  ///  O X  |  _ +  |  O O
                    cout << cx << ' ' << cy << '\n'; ///   Operation: 3 -> 0
                }
            }
        }
    }
    return 0;
}

Benchmark

$$$\text{Average case} = \frac{\text{Total count}}{\text{Rows}\ \cdot \text{Columns}\ \cdot \text{Total case}}$$$

For $$$N$$$ ones in table, it need exact $$$3 \times N$$$ operations

For every $$$N \cdot M$$$ table, it need averagely $$$\frac{3N}{2}$$$ operations

rows	columns	total count	total cases	average percase	maximum case
2	2	96	16	150%	12
2	3	576	64	150%	18
2	4	3072	256	150%	24
2	5	15360	1024	150%	30
2	6	73728	4096	150%	36
2	7	344064	16384	150%	42
2	8	1572864	65536	150%	48
2	9	7077888	262144	150%	54
2	10	31457280	1048576	150%	60
2	11	138412032	4194304	150%	66
2	12	603979776	16777216	150%	72
3	2	576	64	150%	18
3	3	6912	512	150%	27
3	4	73728	4096	150%	36
3	5	737280	32768	150%	45
3	6	7077888	262144	150%	54
3	7	66060288	2097152	150%	63
3	8	603979776	16777216	150%	72
4	2	3072	256	150%	24
4	3	73728	4096	150%	36
4	4	1572864	65536	150%	48
4	5	31457280	1048576	150%	60
4	6	603979776	16777216	150%	72
5	2	15360	1024	150%	30
5	3	737280	32768	150%	45
5	4	31457280	1048576	150%	60
5	5	1258291200	33554432	150%	75
6	2	73728	4096	150%	36
6	3	7077888	262144	150%	54
6	4	603979776	16777216	150%	72
7	2	344064	16384	150%	42
7	3	66060288	2097152	150%	63
8	2	1572864	65536	150%	48
8	3	603979776	16777216	150%	72
9	2	7077888	262144	150%	54
10	2	31457280	1048576	150%	60
11	2	138412032	4194304	150%	66
12	2	603979776	16777216	150%	72

Problem C2 - Eliminate odd row, odd column then eliminate 2x2 cells

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

#define all(x) (x).begin(), (x).end()

/// Each line of the answer
struct node { 
    int a, b, c, d, e, f; 
    node (int a, int b, int c, int d, int e, int f)
    :       a(a),  b(b),  c(c),  d(d),  e(e),  f(f) {}
};

vector<node> res;
vector<vector<int> > a;
void flip(const node &x)
{
    a[x.a][x.b] ^= 1;
    a[x.c][x.d] ^= 1;
    a[x.e][x.f] ^= 1;
    res.push_back(x);
}

int main()
{
    int q;
    cin >> q;
    
    while (q-->0) /// For each query
    {
        /// Input
        int n, m;
        cin >> n >> m;
        
        a.assign(n + 1, vector<int>(m + 1, 0));
        for (int i = 1; i <= n; ++i)
        {
            string s;
            cin >> s;
            
            for (int j = 1; j <= m; ++j)
                a[i][j] = s[j - 1] - '0'; /// Convert string to array
        }
        
        res.clear();
        
        /// Odd row elimination
        if (n & 1)
        {
            for (int j = 1; j <= m; ++j) /// Eliminate 2x1 cells by once
            {
                int p = (j == m) ? (j - 1) : (j + 1);
                if (a[n][j]) flip(node(n-0,j   ,   n-1,j   ,   n-1,p));
            }
            --n; /// <- Last row eliminated
        }
        
        /// Odd column elimination
        if (m & 1)
        {
            for (int i = 1; i <= n; ++i) /// Eliminate 1x2 cells by once
            {
                int p = (i == n) ? (i - 1) : (i + 1);
                if (a[i][m]) flip(node(i,m-0   ,   i,m-1   ,   p,m-1));
            }
            --m; /// <- last col eliminated
        }
        
        /// Eliminate 2x2 cells by once
        for (int i = 1; i <= n; i += 2)
        {
            for (int j = 1; j <= m; j += 2)
            {
                int x = 0, y = 0, z = 0, t = 0;
                if (a[i + 0][j + 0]) x ^= 0, y ^= 1, z ^= 1, t ^= 1;
                if (a[i + 1][j + 0]) x ^= 1, y ^= 0, z ^= 1, t ^= 1;
                if (a[i + 0][j + 1]) x ^= 1, y ^= 1, z ^= 0, t ^= 1;
                if (a[i + 1][j + 1]) x ^= 1, y ^= 1, z ^= 1, t ^= 0;
            
                if (x) flip(node(i+1,j+0   ,   i+0,j+1   ,   i+1,j+1));
                if (y) flip(node(i+0,j+0   ,   i+0,j+1   ,   i+1,j+1));
                if (z) flip(node(i+0,j+0   ,   i+1,j+0   ,   i+1,j+1));
                if (t) flip(node(i+0,j+0   ,   i+1,j+0   ,   i+0,j+1));
            }
        }
        
        /// Output the result
        cout << res.size() << '\n';
        for (const node &x : res)
        {
            cout << x.a << ' ' << x.b << ' ';
            cout << x.c << ' ' << x.d << ' ';
            cout << x.e << ' ' << x.f << '\n';
        }
    }
    return 0;
}

Benchmark

$$$\text{Average case} = \frac{\text{Total count}}{\text{Rows}\ \cdot \text{Columns}\ \cdot \text{Total case}}$$$

For $$$S$$$ ones in table, it need maximumly $$$min(N \cdot M, 3 \times S)$$$ operations

For every $$$N \cdot M$$$ table, it need averagely $$$\frac{N}{2}$$$ operations and maximumly $$$N * M$$$ operations

rows	columns	total count	total cases	average percase	maximum case
2	2	32	16	50%	4
2	3	192	64	50%	6
2	4	1024	256	50%	8
2	5	5120	1024	50%	10
2	6	24576	4096	50%	12
2	7	114688	16384	50%	14
2	8	524288	65536	50%	16
2	9	2359296	262144	50%	18
2	10	10485760	1048576	50%	20
2	11	46137344	4194304	50%	22
2	12	201326592	16777216	50%	24
3	2	192	64	50%	6
3	3	2304	512	50%	9
3	4	24576	4096	50%	12
3	5	245760	32768	50%	15
3	6	2359296	262144	50%	18
3	7	22020096	2097152	50%	21
3	8	201326592	16777216	50%	24
4	2	1024	256	50%	8
4	3	24576	4096	50%	12
4	4	524288	65536	50%	16
4	5	10485760	1048576	50%	20
4	6	201326592	16777216	50%	24
5	2	5120	1024	50%	10
5	3	245760	32768	50%	15
5	4	10485760	1048576	50%	20
6	2	24576	4096	50%	12
6	3	2359296	262144	50%	18
6	4	201326592	16777216	50%	24
7	2	114688	16384	50%	14
7	3	22020096	2097152	50%	21
8	2	524288	65536	50%	16
8	3	201326592	16777216	50%	24
9	2	2359296	262144	50%	18
10	2	10485760	1048576	50%	20
11	2	46137344	4194304	50%	22
12	2	201326592	16777216	50%	24

Problem C2 - Eliminate rows then columns then last 2x2 cells

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

#define all(x) (x).begin(), (x).end()

/// Each line of the answer
struct node { 
    int a, b, c, d, e, f; 
    node (int a, int b, int c, int d, int e, int f)
    :       a(a),  b(b),  c(c),  d(d),  e(e),  f(f) {}
};

vector<node> res;
vector<vector<int> > a;
void flip(const node &x)
{
    a[x.a][x.b] ^= 1;
    a[x.c][x.d] ^= 1;
    a[x.e][x.f] ^= 1;
    res.push_back(x);
}

int main()
{
    int q;
    cin >> q;
    
    while (q-->0) /// For each query
    {
        /// Input
        int n, m;
        cin >> n >> m;

        /// Initalization
        res.clear();
        a.assign(n + 1, vector<int>(m + 1, 0));
        for (int i = 1; i <= n; ++i)
        {
            string s;
            cin >> s;
            
            for (int j = 1; j <= m; ++j)
                a[i][j] = s[j - 1] - '0'; /// Convert string to array
        }
        


        /// Odd column elimination
        if (m & 1)
        {
            for (int i0 = 1; i0 <= n; ++i0) /// Eliminate 1x2 cells by once
            {
                if (a[i0][m] == 0) continue;
                int i1 = (i0 == n) ? (i0 - 1) : (i0 + 1);
//                if (a[i1][m]) flip(node(i0,m-0   ,   i1,m-0   ,   i0,m-1));
//                else          flip(node(i0,m-0   ,   i0,m-1   ,   i1,m-1));

                if (a[i1][m]) /// Greedy one more step
                {
                    int p = a[i1][m-1] ? i1 : i0; /// Select the one with one
                    flip(node(i0,m-0   ,   i1,m-0   ,   p,m-1));
                }
                else          flip(node(i0,m-0   ,   i0,m-1   ,   i1,m-1));
            }
            --m; /// <- Last col eliminated
        }
        


        /// Row Elimination: n * m -> 2 * m remaining
        while (n > 2)
        {
            for (int j0 = 1; j0 <= m; ++j0) /// Eliminate 2x1 cells by once
            {
                if (a[n][j0] == 0) continue;
                int j1 = (j0 == m) ? (j0 - 1) : (j0 + 1);
//                if (a[n][j1]) flip(node(n-0,j0   ,   n-0,j1   ,   n-1,j0));
//                else          flip(node(n-0,j0   ,   n-1,j0   ,   n-1,j1));

                if (a[n][j1])  /// Greedy one more step
                {
                    int p = a[n-1][j1] ? j1 : j0; /// Select the one with one
                    flip(node(n-0,j0   ,   n-0,j1   ,   n-1,p));
                }
                else          flip(node(n-0,j0   ,   n-1,j0   ,   n-1,j1));
            }
            --n; /// <- Last row eliminated
        }
        


        /// Col Elimination: 2 * m -> 2 * 2 remaining
        while (m > 2)
        {
            for (int i0 = 1; i0 <= n; ++i0) /// Eliminate 1x2 cells by once
            {
                if (a[i0][m] == 0) continue;
                int i1 = (i0 == n) ? (i0 - 1) : (i0 + 1);
//                if (a[i1][m]) flip(node(i0,m-0   ,   i1,m-0   ,   i0,m-1));
//                else          flip(node(i0,m-0   ,   i0,m-1   ,   i1,m-1));

                if (a[i1][m]) /// Greedy one more step
                {
                    int p = a[i1][m-1] ? i1 : i0; /// Select the one with one
                    flip(node(i0,m-0   ,   i1,m-0   ,   p,m-1));
                }
                else          flip(node(i0,m-0   ,   i0,m-1   ,   i1,m-1));
            }
            --m; /// <- Last col eliminated
        }
        


        /// Cells Elimination: 2 * 2 -> 0 * 0 remaining - Using modular equations
        int x = 0, y = 0, z = 0, t = 0;
        if (a[1][1]) x ^= 0, y ^= 1, z ^= 1, t ^= 1;
        if (a[2][1]) x ^= 1, y ^= 0, z ^= 1, t ^= 1;
        if (a[1][2]) x ^= 1, y ^= 1, z ^= 0, t ^= 1;
        if (a[2][2]) x ^= 1, y ^= 1, z ^= 1, t ^= 0;

        if (x) flip(node(2,1   ,   1,2   ,   2,2));
        if (y) flip(node(1,1   ,   1,2   ,   2,2));
        if (z) flip(node(1,1   ,   2,1   ,   2,2));
        if (t) flip(node(1,1   ,   2,1   ,   1,2));
     


        /// Output the result
        cout << res.size() << '\n';
        for (const node &x : res)
        {
            cout << x.a << ' ' << x.b << ' ';
            cout << x.c << ' ' << x.d << ' ';
            cout << x.e << ' ' << x.f << '\n';
        }
    }
    return 0;
}

Benchmark

$$$\text{Average case} = \frac{\text{Total count}}{\text{Rows}\ \cdot \text{Columns}\ \cdot \text{Total case}}$$$

For every $$$N \cdot M$$$ table, it need averagely $$$\frac{N}{2}$$$ operations and maximumly $$$min(N \cdot M, \lceil \frac{n + 1}{2} \rceil + \lceil \frac{m(n - 2)}{2} \rceil + (m - 2) + 3)$$$ operations

rows	columns	total count	total cases	average percase	maximum case
2	2	32	16	50%	4
2	3	176	64	45.8333%	5
2	4	880	256	42.9688%	6
2	5	4240	1024	41.4062%	7
2	6	19824	4096	40.332%	8
2	7	90768	16384	39.5717%	9
2	8	408944	65536	38.9999%	10
2	9	1819280	262144	38.5556%	11
2	10	8011120	1048576	38.2%	12
2	11	34980496	4194304	37.9091%	13
2	12	151666032	16777216	37.6667%	14
3	2	176	64	45.8333%	5
3	3	1968	512	42.7083%	7
3	4	19824	4096	40.332%	8
3	5	194352	32768	39.541%	10
3	6	1816240	262144	38.4911%	11
3	7	16814096	2097152	38.179%	13
3	8	151165600	16777216	37.5424%	14
4	2	880	256	42.9688%	6
4	3	19824	4096	40.332%	8
4	4	405088	65536	38.6322%	10
4	5	7938304	1048576	37.8528%	12
4	6	148856720	16777216	36.969%	14
5	2	4240	1024	41.4062%	7
5	3	193216	32768	39.3099%	10
5	4	7897792	1048576	37.6596%	12
5	5	311233920	33554432	37.102%	15
6	2	19824	4096	40.332%	8
6	3	1816240	262144	38.4911%	11
6	4	148979200	16777216	36.9994%	14
7	2	90768	16384	39.5717%	9
7	3	16718864	2097152	37.9627%	13
8	2	408944	65536	38.9999%	10
8	3	151165600	16777216	37.5424%	14
9	2	1819280	262144	38.5556%	11
10	2	8011120	1048576	38.2%	12
11	2	34980496	4194304	37.9091%	13
12	2	151666032	16777216	37.6667%	14

→ Reply

Swistakk

4 years ago, # |

+16

I mean, I agree it is quite coding-heavy, but I would not agree that problem was super shitty or whatever. Idea behind the problem is not that bad. I would think that if it was on some ICPC contest nobody would bat an eye, but this positioning here was something that caused so much outrage since it is not pleasant for problem you start with (in Div1) and problem that should be fairly simple to Div2 people as well (cause they will drown in badly written code more than Div1 people).

→ Reply

newbie_to_newbie

4 years ago, # ^ |

← Rev. 2 →

-43

I agree!!

→ Reply

-is-this-fft-

4 years ago, # ^ |

+44

Please, don't write such comments on 4 month old threads, unless you actually have something new and valuable to add. If your comment is "this problem is shit" (in this case, provide arguments) or "I agree" (in this case, just upvote) then there is no need to write it at all. It's just polluting Recent Actions.

→ Reply

Sai_t

4 years ago, # |

-30

You're actually getting up-votes bro...(I think you're right.)

→ Reply