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

→ Обратите внимание

До соревнования
Codeforces Round 941 (Div. 1)
4 дня
Зарегистрироваться »

*есть доп. регистрация

До соревнования
Codeforces Round 941 (Div. 2)
4 дня
Зарегистрироваться »

*есть доп. регистрация

→ Трансляции

CodeChef Starters 131 Solution Discussion

aryanc403

До начала 23:51:08

Всё →

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	ecnerwala	3650
2	Benq	3582
3	Geothermal	3570
3	orzdevinwang	3570
5	cnnfls_csy	3569
6	tourist	3565
7	maroonrk	3532
8	Radewoosh	3522
9	Um_nik	3483
10	jiangly	3468

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	maomao90	174
2	awoo	164
3	adamant	163
4	TheScrasse	159
5	nor	158
6	maroonrk	156
7	-is-this-fft-	151
8	SecondThread	147
9	orz	146
10	pajenegod	145

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

Блог пользователя I_am_Drew

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

Автор I_am_Drew, история, 3 года назад, По-русски

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

+356

I_am_Drew
3 года назад
82

Комментарии (74)

Показать архивные | Написать комментарий?

basketballer

3 года назад, # |

agree

→ Ответить

Aditya_Sharma

3 года назад, # ^ |

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.

→ Ответить

Mridul323

3 года назад, # |

+22

Felt like solving Codechef long challenge problems.

→ Ответить

Yukuk

3 года назад, # |

← 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

→ Ответить

sevlll777

3 года назад, # |

-151

please downvote him

→ Ответить

TheScrasse

3 года назад, # |

+85

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

→ Ответить

keklol45

3 года назад, # ^ |

+60

C1-C2 (div2) The shittiest problem on CF

→ Ответить

Candidate_Master_2021

3 года назад, # ^ |

+57

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

→ Ответить

Drew_is_me

3 года назад, # ^ |

+43

C1-C2 (div2) The shittiest problem

→ Ответить

tem_shett

3 года назад, # ^ |

+78

C1-C2 (div2)

→ Ответить

MikMirzoyanov

3 года назад, # ^ |

+70

C1-C2

→ Ответить

Yukuk

3 года назад, # ^ |

+42

→ Ответить

MarkZuckerberg

3 года назад, # ^ |

+40

→ Ответить

Elegy_No_Programmer

3 года назад, # ^ |

+109

→ Ответить

rotavirus

3 года назад, # ^ |

+52

C'est la vie

→ Ответить

Why_am_i_here_

3 года назад, # ^ |

+13

-(C)

→ Ответить

Ahmed_Solyman

3 года назад, # ^ |

-9

C1 and C2

→ Ответить

snorkel

3 года назад, # ^ |

C(1-2)

→ Ответить

snorkel

3 года назад, # ^ |

-13

C(-3)

→ Ответить

snorkel

3 года назад, # ^ |

-8

-3C

→ Ответить

arham_doshi

3 года назад, # ^ |

+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.

→ Ответить

nickcotforce

3 года назад, # ^ |

C1-C2 (problem) The shittiest div2 on CF

→ Ответить

sam571128

3 года назад, # ^ |

-14

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

→ Ответить

dca

3 года назад, # |

+26

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

→ Ответить

AtomicCoder

3 года назад, # ^ |

+52

That's why they are in div1

→ Ответить

Dean_student

3 года назад, # |

+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.

→ Ответить

pkhaustov

3 года назад, # |

+17

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

→ Ответить

Dean_student

3 года назад, # ^ |

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.

→ Ответить

Q101

3 года назад, # |

-19

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

→ Ответить

I_am_Drew

3 года назад, # ^ |

+13

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

→ Ответить

Q101

3 года назад, # ^ |

-45

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

→ Ответить

not-an-alt

3 года назад, # ^ |

+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

→ Ответить

Q101

3 года назад, # ^ |

-31

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

→ Ответить

Len

3 года назад, # ^ |

Because it's a C1 solution?

→ Ответить

Q101

3 года назад, # ^ |

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

→ Ответить

amarnathsama

3 года назад, # ^ |

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.

→ Ответить

SuperJ6

3 года назад, # ^ |

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.

→ Ответить

amarnathsama

3 года назад, # ^ |

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.

→ Ответить

SuperJ6

3 года назад, # ^ |

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...

→ Ответить

Elegy_No_Programmer

3 года назад, # ^ |

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

→ Ответить

amarnathsama

3 года назад, # ^ |

Yes, it is, among others.

→ Ответить

Dean_student

3 года назад, # ^ |

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

→ Ответить

_mndm

3 года назад, # |

← Rev. 2 →

+10

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

→ Ответить

Swistakk

3 года назад, # ^ |

+89

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

→ Ответить

SkyDreams

3 года назад, # |

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

→ Ответить

viwreck

3 года назад, # |

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.

→ Ответить

Not-Afraid

3 года назад, # |

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

→ Ответить

amurto

3 года назад, # ^ |

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

→ Ответить

Not-Afraid

3 года назад, # ^ |

1 2 3 111 110

→ Ответить

sevlll777

3 года назад, # ^ |

← Rev. 2 →

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

→ Ответить

SkyDreams

3 года назад, # ^ |

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

→ Ответить

amurto

3 года назад, # ^ |

← 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

→ Ответить

sevlll777

3 года назад, # ^ |

← 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

→ Ответить

_mndm

3 года назад, # ^ |

← 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

→ Ответить

Radewoosh

3 года назад, # |

+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".

→ Ответить

mesanu

3 года назад, # ^ |

preach

→ Ответить

bleh0.5

3 года назад, # ^ |

+81

imagine being lgm and thinking you're gonna get downvoted

→ Ответить

asfd221

3 года назад, # ^ |

+16

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

→ Ответить

ffao

3 года назад, # ^ |

← 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.

→ Ответить

Makise_Kurisu

3 года назад, # |

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() ;
}

→ Ответить

AlexFetisov

3 года назад, # |

+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.

→ Ответить

WolfBlue

3 года назад, # |

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

→ Ответить

endless_summer

3 года назад, # |

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

→ Ответить

oversolver

3 года назад, # |

But I see its upvoted.

So it is false?

→ Ответить

Eason_AC

3 года назад, # |

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?

→ Ответить

Gassa

3 года назад, # |

+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.

→ Ответить

pkhaustov

3 года назад, # ^ |

+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.

→ Ответить

newbie_to_newbie

3 года назад, # |

-34

Downvote me!!! ORZ!!!

→ Ответить

Eason_AC

3 года назад, # ^ |

← Rev. 2 →

-16

[Deleted]

→ Ответить

SPyofgame

3 года назад, # |

← 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

→ Ответить

Swistakk

3 года назад, # |

+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).

→ Ответить

newbie_to_newbie

3 года назад, # ^ |

← Rev. 2 →

-43

I agree!!

→ Ответить

-is-this-fft-

3 года назад, # ^ |

+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.

→ Ответить

Sai_t

3 года назад, # |

-30

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

→ Ответить

Соревнования по программированию 2.0

Время на сервере: 23.04.2024 19:53:52 (j3).

Десктопная версия, переключиться на мобильную.

При поддержке