## CCC '21 S2 - Modern Art

View as PDF

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 -by- 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 . The second line of input will be a positive integer . The third line of input will be a positive integer . The remaining input will be 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 to . Columns are numbered left to right from to .

The following table shows how the available marks are distributed.

mark only one cell, and
up to choices by the artist
marks only one row, and
up to choices by the artist
marks up to rows, up to columns, and
up to choices by the artist
marks up to cells, and
up to 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.

3
3
2
R 1
C 1

4

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

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

10

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

• commented on Oct. 29, 2022, 8:04 p.m. edit 3

I don't understand why I got WA here: https://dmoj.ca/src/4987790

But I ACed with the same code with a split: https://dmoj.ca/src/4987788

• commented on Nov. 30, 2022, 11:12 p.m.

rows[int(i[2])-1] += 1

Inputs such as R 12 will be read as R 1.

rows[int(i[2:])-1] += 1 would suffice - https://dmoj.ca/submission/5081809

• 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?

• 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

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

• commented on Feb. 13, 2022, 11:50 a.m. edit 3

thanks for the tip but I have a different solution.

• 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

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

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

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

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

• 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?

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

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

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

Why is my code wrong

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

You're going out of bounds with your array.

• commented on Jan. 4, 2022, 5:58 p.m. edit 2

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

EDIT 2: I think {0} only sets the first item to 0 - everything else is undefined, but {} initializes every item to 0.

• 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?

• 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 :)

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

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

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

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.

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

Is this possible in python ?

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