CCC '21 S2 - Modern Art
View as PDFCanadian 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.
| Subtask | Description | |||
|---|---|---|---|---|
| only one cell, and up to | ||||
| only one row, and up to | ||||
| up to up to | ||||
| up to up to | ||||
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
3
3
2
R 1
C 1Output for Sample Input 1
4Explanation of Output for Sample Input 1
After running the brush along the first row, the canvas looks like this:
GGG
BBB
BBBThen after running the brush along the first column, four cells are gold in the final pattern determined by the artist's choices:
BGG
GBB
GBBSample Input 2
4
5
7
R 3
C 1
C 2
R 2
R 2
C 1
R 4Output for Sample Input 2
10Explanation 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
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
Your code only accounts for brushes made before row/column 10.
rows[int(i[2])-1] += 1Inputs such as
R 12will be read asR 1.rows[int(i[2:])-1] += 1would suffice - https://dmoj.ca/submission/5081809I have O(NM+K) as Time complexity of my code, but still I got TLE. Why?
the intended solution runs in O(N+M+K) time
edit: nvm im trolling
well there is a possible solution that works in O(N+M+K) time - but it's not the intended solution.
https://dmoj.ca/problem/ccc21s2/editorial#comment-16184
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.
thanks for the tip but I have a different solution.
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
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.
Wait could you explain to me why its O(max(n, 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.
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?
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.
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.
Why is my code wrong
You're going out of bounds with your array.
I don't know about that one, but all I did was to change
to
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 thisEDIT: I tested it on my GCC compiler and seems to do the exact same thing (
{0},{})? Clear up wantedEDIT 2: I think
{0}only sets the first item to 0 - everything else is undefined, but{}initializes every item to 0.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?
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 :)
Thanks. Was this the requirement on the CCC as well?
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.
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.
Is this possible in python ?
Yes https://dmoj.ca/problem/ccc21s2/rank/?language=PY2&language=PY3&language=PYPY&language=PYPY3