CCC '21 S2 - Modern Art - DMOJ: Modern Online Judge

CCC '21 S2 - Modern Art

Points: 7 (partial)

Time limit: 3.0s

Memory limit: 1G

Problem type

Canadian Computing Competition: 2021 Stage 1, Junior #5, Senior #2

A new and upcoming artist has a unique way to create checkered patterns. The idea is to use an $M$ ~M~-by- $N$ ~N~ canvas which is initially entirely black. Then the artist repeatedly chooses a row or column and runs their magic brush along the row or column. The brush changes the colour of each cell in the row or column from black to gold or gold to black. Given the artist's choices, your job is to determine how much gold appears in the pattern determined by these choices.

Input Specification

The first line of input will be a positive integer $M$ ~M~. The second line of input will be a positive integer $N$ ~N~. The third line of input will be a positive integer $K$ ~K~. The remaining input will be $K$ ~K~ lines giving the choices made by the artist. Each of these lines will either be R followed by a single space and then an integer which is a row number, or C followed by a single space and then an integer which is a column number. Rows are numbered top down from $1$ ~1~ to $M$ ~M~. Columns are numbered left to right from $1$ ~1~ to $N$ ~N~.

The following table shows how the available $15$ ~15~ marks are distributed.

Subtask	$M$ ~M~	$N$ ~N~	$K$ ~K~	Description
$1$ ~1~ mark	$M = 1$ ~M = 1~	$N = 1$ ~N = 1~	$K \le 100$ ~K \le 100~	only one cell, and up to $100$ ~100~ choices by the artist
$4$ ~4~ marks	$M = 1$ ~M = 1~	$N \le 100$ ~N \le 100~	$K \le 100$ ~K \le 100~	only one row, and up to $100$ ~100~ choices by the artist
$5$ ~5~ marks	$M \le 100$ ~M \le 100~	$N \le 100$ ~N \le 100~	$K \le 100$ ~K \le 100~	up to $100$ ~100~ rows, up to $100$ ~100~ columns, and up to $100$ ~100~ choices by the artist
$5$ ~5~ marks	$MN \le 5\,000\,000$ ~MN \le 5\,000\,000~		$K \le 1\,000\,000$ ~K \le 1\,000\,000~	up to $5\,000\,000$ ~5\,000\,000~ cells, and up to $1\,000\,000$ ~1\,000\,000~ choices by the artist

Output Specification

Output one non-negative integer which is equal to the number of cells that are gold in the pattern determined by the artist's choices.

Sample Input 1

Output for Sample Input 1

Explanation of Output for Sample Input 1

After running the brush along the first row, the canvas looks like this:

GGG
BBB
BBB

Then after running the brush along the first column, four cells are gold in the final pattern determined by the artist's choices:

BGG
GBB
GBB

Sample Input 2

4
5
7
R 3
C 1
C 2
R 2
R 2
C 1
R 4

Output for Sample Input 2

Explanation of Output for Sample Input 2

Ten cells are gold in the final pattern determined by the artist's choices:

BGBBB
BGBBB
GBGGG
GBGGG

Comments

0

cchungelliot commented on Feb. 10, 2022, 9:21 p.m.

I have O(NM+K) as Time complexity of my code, but still I got TLE. Why?

0

henrybaolol9 commented on Feb. 11, 2022, 9:57 a.m. ← edit 2 →

the intended solution runs in O(N+M+K) time

edit: nvm im trolling

2

Marshmellon commented on Feb. 11, 2022, 9:56 a.m.

Your code is actually O(NMK) instead of O(NM+K). Python's .count() has a complexity of O(K) not O(1) because it does a linear search on the list.

0

cchungelliot commented on Feb. 13, 2022, 11:50 a.m. ← edit 3 →

thanks for the tip but I have a different solution.

0

mahes0640 commented on Feb. 5, 2022, 8:33 p.m.

Does anyone know how I can optimize my code so I don't get a TLE on the last batch? https://dmoj.ca/src/4296538

3

Marshmellon commented on Feb. 5, 2022, 8:46 p.m.

Each brush operation must be O(1), your code currently has O(max(N, M)) per brush operation. Refer to the editorial for help, and if still stuck, consult the #help channel in DMOJ Hub.

0

mahes0640 commented on Feb. 6, 2022, 9:24 p.m.

Wait could you explain to me why its O(max(n, m))?

1

Marshmellon commented on Feb. 11, 2022, 9:48 a.m.

There are N columns and M rows on a given canvas. On each operation, your code loops all the way through a row or all the way down a column depending on if it's an R or C operation. Hence, in the worst case, your code will loop across whichever one is longer of rows and columns on each operation.

-2

Gordon commented on Jan. 9, 2022, 9:55 p.m.

For this question I used like 2 nested for loops and it made my thing go over the time limit for the last check. I found this other answer online that used C++ instead of Python(which is what I use). Their code also had nested for loops and had essentially and the same idea for the algorithm. Somehow their's still got passed the last check. Is C++ really that much faster?

-1

zhanc commented on Feb. 10, 2022, 8:59 p.m.

It's also possible that your nested for loop is iterating for much longer. A nested for loop using M and N has a max iteration count of 5 million, while a nested for loop using K will be much higher as K alone is at most 1 million.

0

Spitfire720 commented on Jan. 10, 2022, 8:28 a.m.

Python is an extremely slow language, which I would know because I use it :(

C++ is one of the fastest programming languages and most of the people use it

Although, this is still passable by python, if you check the editorial, the intended solution uses a nested for loop.

0

TheBoss123 commented on Jan. 4, 2022, 12:01 a.m.

Why is my code wrong

-1

Spitfire720 commented on Jan. 4, 2022, 9:23 a.m.

You're going out of bounds with your array.

2
Badmode commented on Jan. 4, 2022, 5:58 p.m. ← edited →
I don't know about that one, but all I did was to change

int painting[m][n] = {0};

to

int painting[m][n] = {};

To pass everything and TLE on Batch #6

I'm guessing {0} doesn't initialize it properly on c++ which causes undefined behaviour? Don't quote me on this

EDIT: I tested it on my GCC compiler and seems to do the exact same thing ({0}, {})? Clear up wanted

-1

TheBoss123 commented on Jan. 5, 2022, 1:45 a.m.

Thanks. I tried optimizing my code by checking if it is even/odd right after adding 1 to the array value. I believe this is O(K*max(M,N)) complexity. I am still getting a TLE on #6. What else can I do to make it faster?

1

yunz_qiao commented on Jan. 5, 2022, 8:47 a.m.

necessarily, for full mark in this problem, the intended time complexity if O(MN + K), which mean you cannot one-by-one do the operation, you need to think a better way to do it in O(1) time for each operation, and compute each cell after, hope this helps :)

0

TheBoss123 commented on Jan. 5, 2022, 9:36 p.m.

Thanks. Was this the requirement on the CCC as well?

-1

uselessleaf commented on Jan. 5, 2022, 9:39 p.m.

Yes, you can assume that the data here on DMOJ is the same as the data from CCC unless otherwise specified, so the requirement was on the CCC as well.

1

Spitfire720 commented on Jan. 5, 2022, 8:14 a.m.

The intended solution does not require a 2-D array. For test cases where M * N <= 5000000 your solution would indeed TLE. If you are stuck, you can read the editorial, or ask the DMOJ Discord.

0

Someone_you_can_trust commented on April 2, 2021, 8:49 p.m.

Is this possible in python ?

0

BalintR commented on April 2, 2021, 9:46 p.m.

Yes https://dmoj.ca/problem/ccc21s2/rank/?language=PY2&language=PY3&language=PYPY&language=PYPY3