Glenforest Winter Open 2015 (Senior)

Beep... Boop.... Beep...

Butane has turned himself into a robot! Unfortunately, he is very badly programmed (by himself), so none of his intended functions work properly. Can you help debug ButaneBot?

Warning: The Senior contest is recommended for those who have knowledge of algorithms and data structures. Good luck :-).

The problem writers for this contest will be Awaykened and Butane

The contest consists of 5 questions with a range of difficulties, and you can get partial marks for partial solutions in the form of subtasks. If you cannot solve a problem fully, we encourage you to go for these partial marks. The difficulty of the problems will range from CCC Senior level to CCO level.

After joining the contest, you proceed to the Problems tab to begin. You can also go to Users if you wish to see the rankings.

We have listed below some advice as well as contest strategies:

Start from the beginning. Ties will be broken by the sum of times used to solve the problems starting from the beginning of the contest. The last submission time of your highest score will be used.
It is strongly advised to run your code on your own computer with the sample input we provide before submitting. It's faster to find and fix mistakes at this stage rather than submitting and waiting only to find out that your solution doesn't compile.
Remove all extra debugging code and/or input prompts from your code before submitting. The judge is very strict — most of the time, it requires your output to match exactly.
Do not pause program execution at the end. The judging process is automated. You should use stdin / stdout to perform input / output, respectively.
Just because your program works with the sample input doesn't guarantee that it will earn full points. Read the problem statement very carefully to look for things you may have missed on the first read-through. It is not forbidden — in fact, even encouraged to make your own test cases to debug your program on.
The test data is guaranteed to fit within the constraints given. You do not have to perform any extra checks to make sure of this fact.

Good luck!

Problems

Problem	Points	AC Rate	Users	Editorials
GFSSOC '15 Winter S1 - OR-deal	5p	31.5%	366	Editorial
GFSSOC '15 Winter S2 - Soko-Boop	12p	22.5%	63	Editorial
GFSSOC '15 Winter S3 - PalinDrone	7p	19.9%	212	Editorial
GFSSOC '15 Winter S4 - Starry Nights	12p	22.3%	115	Editorial
GFSSOC '15 Winter S5 - ORBOT	15p	17.3%	22	Editorial

Comments

0

XIAOAGE commented on Dec. 15, 2015, 12:26 p.m. ← edited →

When can i find the editorial? I m looking forward to reading it!!!!

2

awaykened commented on Dec. 15, 2015, 12:34 p.m. ← edit 4 →

Sorry, problem setters are a bit busy for the time being. Editorials will likely be released sometime Thursday :)

Edit: here are some simple solution sketches for senior from our Facebook group:

s1 - the answer only has '1's. how many '1's? go find out!

s2 - BFS, state is $(r, c)$ ~(r, c)~ of player, $(r, c)$ ~(r, c)~ of box

s3 - the answer does not change when $N$ ~N~ goes beyond a certain point due to mod 1e9, so simply calculating answers up to that $N$ ~N~ is all that is necessary.

s4 - bitmask dp, realize that there are only $2745$ ~2745~ "good" states that you can precompute, so your complexity is $R \times 2745^2$ ~R \times 2745^2~ instead of $R \times (2^C)^2$ ~R \times (2^C)^2~

s5 - if all array elements are positive, output the or sum of all elements in the array. if all array elements are negative, output the or sum of all elements in the array. otherwise, you want to take the maximum of the OR-sum of any contiguous POSITIVE subsequence of the the array. you can handle the last case using sets or smart implementation of segment trees.

0

XIAOAGE commented on Dec. 15, 2015, 12:40 p.m.

Thank u very much!!!!!!