## GCC '16 #1

Welcome to the first Generic Computer Contest!

The problem writers of this contest are Shinigami and r3mark.

The GCC will be a 2-hour virtual contest, which will allow contestants to participate in any 2-hour windows between Dec 21, 5PM EST and Dec 21, 11PM EST. It is forbidden to use two accounts to participate, and it is also forbidden to discuss the problems and/or solutions with other people during the entire contest period. Owing to relatively short contest time window, there will be no systests.

This contest will not be rated.

Before the contest date, you may wish to check out the tips and help pages. The contest consists of 3 questions with 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 may range anywhere from CCC Junior to CCO level. You will have 2 hours to complete the contest. After the contest window begins, you may begin at any time. Your personal timer will start counting down, and you will be able to submit until 2 hours from when you started, or until the hard deadline (December 21, 11PM EST), whichever comes first. 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.
• 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.
• It is guaranteed that all the problems will be solvable with Java and C++. At the end of the contest, you may comment below to appeal a judging verdict. In the case of appeals, the decision(s) of our staff is final.

## Problems

Problem Points AC Rate Users
GCC '16 P1 - Watching Anime 10p 16.6% 37
GCC '16 P2 - Classified Documents 15p 8.2% 3
GCC '16 P3 - Hang Gliding Fun 25p 22.3% 14

• r3mark  commented on Dec. 21, 2016, 11:54 p.m. edited

I might write proper editorials, but here are the sketches for now.

P1: Fairly simple, you use coordinate compression with a difference array.

P2: Pretty convoluted problem statement which tripped quite a few people up unfortunately. The solution is to count how many messages of length there are (regardless of whether or not they are confidential) and then subtract that by the number of messages which are not confidential. Both these numbers can be found using linear recurrences for a time complexity of . This can be sped up by using the matrix method of computing linear recurrences for a time complexity of .

P3: Notice that the buildings and the paths can be interpreted as a tree where the parent of building is the southmost building taller than it. This is because if there is another one north of the aforementioned parent which Bob can glide from to , then it would be better to simply glide from that building to the parent to (since the view values are non-negative). (Set building with height to be the root of this tree.)

In this tree, begin with all the view values of the nodes set to . Loop from to for the danger value and set the proper view value of each node with . Each query is now essentially asking for maximum sum of the views on the path from the root to any node in the subtree of subtracted by the sum of the views on the path from the root to the parent of when . Let be the sums of views along the path from node to the root. When a node is set to the proper value, then every node in the subtree of has incremented by . Using DFS, an array can be constructed so that all the nodes in a subtree lie in a range. So we can now do these updates and queries using lazy propagation on an RMQ segment tree.

• r3mark  commented on Dec. 21, 2016, 11:15 p.m. edited

Thanks to everyone who participated! We hope you enjoyed the contest!

Solution sketches will be posted in the comments soon.

Edit: Problems will be made public tomorrow.