| Submit | All submissions | Best solutions | Back to list |
COLORCAT - Magical colorful cats (easy) |
There is a circle with n cats, includes white cats, red cats and green cats. When two cats with different color talk with each other, they both change to third color. If they are same color, nothing will happen.
At each step, the 1st cat talks with 2nd cat, the 2nd cat talks with the 3rd cat,… and the nth cat talks with 1st cat.
Given the original color of n cats, your task is find the color of n cats after k steps.
Input :
- First line : n and k (1 ≤ n ≤ 20000, 1 ≤ k ≤ 30000)
- Second line : n characters, the i-th charater denotes color of the i-th cat at first state
Output :
- n characters denotes the color of n cats after k steps.
Sample :
Input :
3 1
GRR
Output :
RGR
Input :
5 4
WRWRW
Output :
GGGWG
Note : After solved this problem, you may want to try BLCATS
| Added by: | Kata |
| Date: | 2014-03-13 |
| Time limit: | 1s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ASM64 |
| Resource: | VNOI |
hide comments
|
2015-08-02 12:05:14
ANY HINT PLEASE |
|
|
2015-01-29 11:38:50 Kata
At the time I publish this problem, my brute force solution couldn't pass in 1s, but my optimized solution could pass (also in 0.3s), so I set time limit to 1s. But some day after, I found that only a little optimizations make it pass in 1s, so I changed it. It's my fault that I didn't notice it any more. I agree with Min_25. Time limit set back to 1s. Thanks your helps. Last edit: 2015-01-29 11:41:03 |
|
|
2015-01-29 10:39:21 Min_25
As far as I remember, the time limit of this problem has been changed twice; 1.00 -> 0.50 -> 0.30s. And there were 3 solvers for this problem. I think the time limit should be set back to 1.00s. Last edit: 2015-01-29 10:40:13 |
|
|
2015-01-29 05:40:31 Kata
I have changed the time limit after publish the problem some days and leave a comment, but it was deleted (?). Because it's a old problem, I didn't notice it. Sorry. p/s : The new time limit is decided based on the idea of original problem. |
|
|
2015-01-29 05:09:44 Mitch Schwartz
Why was time limit changed so that Robert Gerbicz no longer gets AC? That doesn't seem fair. Edit: Thanks for that info. I can't say I'm entirely satisfied with all of that, but I would like to be constructive. Please consider: (1) Whether you accidentally set the time limit too tightly. (2) Creating tutorial version of the problem with relaxed time limit, which could help people test. (3) Take screenshots of important comments to your problems so you have a backup in case they get lost, and/or add a short note to the bottom of the problem description whenever an important change is made. (4) Be very reluctant to change problems after publication, out of respect for solvers. A better option in many cases would be to move the original problem to tutorial and create a new version for classical. And of course, try to publish very carefully to avoid issues in the first place. (5) Time limits are generally chosen according to problem setter's solution at time of publication. It's possible that after publication, there are some very fast submissions that used ideas the problem setter never thought of. That sort of situation is generally not good justification for lowering time limit, in my view. It can cause various issues, which may or may not be obvious, and I can go into that later if it seems useful / applicable. Thanks. Last edit: 2015-01-29 08:59:29 |
|
|
2015-01-29 03:08:06 Kata
No, but it need some special optimizations. |
|
|
2015-01-27 18:03:35 Ivan Katanic
Time limit seems very tight..is O(n*log(n)*log(k)) supposed to pass? Last edit: 2015-01-27 18:03:53 |
RSS