CCC '16 S5 - Circle of Life - Olympiads Online Judge

CCC '16 S5 - Circle of Life

Points: 20 (partial)

Time limit: 2.0s

Memory limit: 256M

Author:

Problem type

Canadian Computing Competition: 2016 Stage 1, Senior #5

You may have heard of Conway's Game of Life, which is a simple set of rules for cells on a grid that can produce incredibly complex configurations. In this problem we will deal with a simplified version of the game.

There is a one-dimensional circular strip of $N$ ~N~ cells. The cells are numbered from $1$ ~1~ to $N$ ~N~ in the order you would expect: that is, cell $1$ ~1~ and cell $2$ ~2~ are adjacent, cell $2$ ~2~ and cell $3$ ~3~ are adjacent, and so on up to cell $N-1$ ~N-1~, which is adjacent to cell $N$ ~N~. Since the trip is circular, cell $1$ ~1~ is also adjacent to cell $N$ ~N~.

Each cell is either alive (represented by a 1) or dead (represented by a 0). The cells change over a number of generations. If exactly one of the cell's neighbours is alive in the current generation, then the cell will be alive in the next generation. Otherwise, the cell will be dead in the next generation.

Given the initial state of the strip, find the state after $T$ ~T~ generations.

Input Specification

The first line will contain two space-separated integers $N$ ~N~ and $T$ ~T~ ( $3 \le N \le 100\,000; 1 \le T \le 10^{15}$ ). The second line will contain a string consisting of exactly $N$ ~N~ characters, representing the initial configuration of the $N$ ~N~ cells. Each character in the string will be either 0 or 1. The initial state of cell $I$ ~I~ is given by the $i^{th}$ ~i^{th}~ character of the string. The character 1 represents an alive cell and the character 0 represents a dead cell.

For 1 of the 15 available marks, $N \le 15$ ~N \le 15~ and $T \le 15$ ~T \le 15~.
For an additional 6 of the 15 available marks, $N \le 15$ ~N \le 15~.
For an additional 4 of the 15 available marks, $N \le 4\,000$ ~N \le 4\,000~ and $T \le 10\,000\,000$ ~T \le 10\,000\,000~.

Note that for full marks, solutions will need to handle 64-bit integers. For example:

in C/C++, the type long long should be used;
in Java, the type long should be used;
in Pascal, the type int64 should be used.

Output Specification

Output the string of $N$ ~N~ characters representing the final state of the cells, in the same format and order as the input.

Sample Input 1

7 1
0000001

Output for Sample Input 1

Explanation for Output for Sample Input 1

Cell $1$ ~1~ and cell $N-1$ ~N-1~ are adjacent to cell $N$ ~N~, and thus alive after one generation.

Sample Input 2

5 3
01011

Output for Sample Input 2

Explanation for Output for Sample Input 2

After one generation, configuration becomes 00011.

After two generations, configuration becomes 10111.

Comments

0

Eric422 commented on Nov. 22, 2020, 5:51 a.m. ← edit 3 →

I'm TLE'ing on Case 3 of Batch 6. My Java solution should implement in $\mathcal{O}(N \log T)$ ~\mathcal{O}(N \log T)~ time. Does anyone have any suggestions?

Edit: Never mind, I fixed by using character array instead of string manip

14

aaronhe07 commented on July 10, 2020, 5:57 a.m.

Wow this problem is very elegant.

-4

notpeachay420 commented on April 16, 2020, 4:39 p.m.

I'm getting TLE on most cases... any suggestions?

56
richardzhang commented on April 16, 2020, 8:07 p.m. ← edit 2 →
I'd suggest you take a look on the upper bounds of $N$ ~N~ and $T$ ~T~. If we're generous, and assume that DMOJ judges can run ~1e8 operations per second for Python 3, and your algorithm is $\mathcal O(NT)$ ~\mathcal O(NT)~, then we can ballpark your algorithm to run for approximately $10^{15} \times 10^{5} \div 10^{8} = 10^{12}$ seconds $= 31\ 689$ ~ = 31\ 689~ years. In that time, we will:

most likely have upgraded to better judges at some point

possibly find a conclusion for $P=NP$ ~P=NP~

probably find a theory for quantum gravity

witness the 31st nuclear winter

u͏n̴̹͕l̺̹̯͚e͘a̤̻̭͎̞ͅs͏̪̟h͖͚͖͕ ̮̥͚t͎h͔̦̼͍͓͚͙e̙̺̞͍̗͈ͅ ̭k̻̕r͔̥͉̗̦a̸̼͚k͕̩̥̦e̯͖ņ̤͖

likely have achieved AI supremacy

probably all died out from said AI supremacy

TL;DR: $10^{15}$ ~10^{15}~ is a very big number. Can you think of a way to greatly reduce this number down? (A starting place might be to think of cycles.)

If you're still struggling, the editorial exists :blobthumbsup: (but not for you to copy and gain free points).

22

Tzak commented on April 16, 2020, 8:09 p.m.

:richard:

-4

Plasmatic commented on April 16, 2020, 8:19 p.m.

:richad:

-8

Bobliu commented on April 16, 2020, 9:35 p.m.

:lct:

This comment is hidden due to too much negative feedback. Show it anyway.

2

zurtar commented on June 26, 2019, 11:22 p.m.

Getting TLE for batch 4-6 any tips or general directions to look into. A bit stuck here.

1

discoverMe commented on July 1, 2019, 12:19 p.m.

Remember that $T$ ~T~ can be very large, look at the editorial for a faster algorithm

-65

rougi139 commented on Dec. 23, 2017, 5:47 p.m.

i submitted with editorial and i m not banned hhahahahahahahahhahahahahaha they are just lying copy that shit guys

This comment is hidden due to too much negative feedback. Show it anyway.

14

Mrs_Clean commented on Nov. 23, 2020, 12:53 a.m.

how to get away with murder

32

injust commented on Dec. 23, 2017, 6:30 p.m. ← edited →

I'm pretty sure this is what they call asking for a ban.

Edit: How did that banhammer taste?

31

Kirito commented on Dec. 23, 2017, 6:59 p.m.

That is correct.

13
Kirito commented on Feb. 9, 2017, 11:52 p.m. ← edited →
This is a reminder that copy-pasting the editorial submission is neither approved, nor is it a learning opportunity. As such, anyone who has copy-pasted the editorial will:

Be banned from the problem.

Have their submission replaced with a cheeky message.

Have their points removed.

3

thomas0115 commented on Feb. 23, 2016, 9:16 p.m.

I got WA on the second last test case... but the same code AC'd

5

cheesecake commented on Feb. 23, 2016, 9:29 p.m. ← edited →

This is likely due to the floating-point precision errors caused by different behavior of the function log on different judges.

0

thomas0115 commented on Feb. 23, 2016, 9:34 p.m.

I'm getting WA on wcipeg

4

cheesecake commented on Feb. 23, 2016, 9:35 p.m.

Try writing your own log function.

4

thomas0115 commented on Feb. 23, 2016, 9:36 p.m.

Thanks, that worked!

1

justyooalex commented on Feb. 21, 2016, 9:37 p.m.

What does Invalid Return mean? I guess my algorithm isn't just outputting a wrong answer but something else entirely?

10

awaykened commented on Feb. 21, 2016, 9:51 p.m. ← edited →

likely, you are going over the python recursion depth limit ( $10^{14}$ ~10^{14}~ times is too much)

here is a link to stackoverflow