GCC '16 #1

Welcome to the first Generic Computer Contest!

The problem writers of this contest are Kirito 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	Editorials
GCC '16 P1 - Watching Anime	10p	16.5%	72	Editorial
GCC '16 P2 - Classified Documents	15p	10.9%	4	Editorial
GCC '16 P3 - Hang Gliding Fun	25p	12.5%	44	Editorial

Comments

3

r3mark commented on Dec. 22, 2016, 4:54 a.m. ← edit 2 →

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

P1: Fairly simple, you use coordinate compression with a difference array. $\mathcal{O}((A+C)\log(A+C))$ ~\mathcal{O}((A+C)\log(A+C))~

P2: Pretty convoluted problem statement which tripped quite a few people up unfortunately. The solution is to count how many messages of length $L$ ~L~ 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 $\mathcal{O}(NL)$ ~\mathcal{O}(NL)~. This can be sped up by using the matrix method of computing linear recurrences for a time complexity of $\mathcal{O}(N^3\log L)$ ~\mathcal{O}(N^3\log L)~.

P3: Notice that the buildings and the paths can be interpreted as a tree where the parent of building $j$ ~j~ 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 $j$ ~j~, then it would be better to simply glide from that building to the parent to $j$ ~j~ (since the view values are non-negative). (Set building $0$ ~0~ with height $1000001$ ~1000001~ to be the root of this tree.)

In this tree, begin with all the view values of the nodes set to $0$ ~0~. Loop $i$ ~i~ from $1$ ~1~ to $1000000$ ~1000000~ for the danger value and set the proper view value of each node $k$ ~k~ with $d_k=i$ ~d_k=i~. 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 $B$ ~B~ subtracted by the sum of the views on the path from the root to the parent of $B$ ~B~ when $i=M$ ~i=M~. Let $s_k$ ~s_k~ be the sums of views along the path from node $k$ ~k~ to the root. When a node $j$ ~j~ is set to the proper value, then every node $k$ ~k~ in the subtree of $j$ ~j~ has $s_k$ ~s_k~ incremented by $v_j$ ~v_j~. 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. $\mathcal{O}(Q\log N)$ ~\mathcal{O}(Q\log N)~

2

r3mark commented on Dec. 22, 2016, 4:15 a.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.