Back to School '17

It's that time of the (school) year again, and to celebrate, we present the Back to School '17 contest! Get back into your tip top programming shape and start the school year with a new rating!

banner

The problem writers of this contest are atarw, aurpine, d and Daniel123.

Back to School '17 will consist of 8 problems, with difficulty ranging between CCC Junior to IOI level. The contest questions have a wide range of difficulty, 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.

Contestants can participate in any 4 hour window between the 48 hour period of Saturday, September 9 to Sunday, September 10 EDT. Once you enter the contest, you will be able to submit until 4 hours from when you started, or until the hard deadline (September 11, 12:00 AM EDT), whichever comes first

Of course, it is forbidden to use multiple accounts to participate, and it is also forbidden to discuss the problems and/or their solutions with other people during the entire contest period.

Due to the large contest time window, we will be using a pretest/systest format in order to prevent cheating. On problems 5-8, when you submit, you will receive your result on some of the test data, called preliminary tests (pretests). After the contest, we will rejudge all solutions on the complete set of test data, and that will determine your final score. Note that getting AC on pretests does not ensure that you will pass system testing.

The pretests may be weak, so be sure to check the correctness and complexity of your solutions! You might also want to constant optimize to prevent TLEing by a small margin. In particular, non-AC submissions on the pretests will likely result in a score of 0 on the systests.

This contest will be rated for contestants with at least one submission.

Before the contest date, you may wish to check out the tips and help pages.

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 C++ and Java.
Read carefully, and try to attempt all the problems. They may not be as hard as they seem and you may get partial points!

At the end of the contest, you may comment below to appeal a judging verdict. In the case of appeals, the decision(s) of staff is final.

Problems

Problem	Points	AC Rate	Users	Editorials
Back To School '17: 🅱aram🅱e	3p	41.6%	412
Back To School '17: Avalon	5p	29.4%	351
Back To School '17: Physics	7	6.8%	73
Back To School '17: Wet Mud	10p	19.5%	338
Back To School '17: New English	12p	10.1%	82	Editorial
Back To School '17: Sour Candy	15p	28.5%	85	Editorial
Back To School '17: Hot and Cold	20p	16.1%	79	Editorial
Back To School '17: Big Integer	35p	5.9%	27	Editorial

Comments

4

Xue_Alex commented on Sept. 11, 2017, 8:12 p.m.

will there be editorials? specifically for p5 : new english, thank you

7

bqi343 commented on Sept. 16, 2017, 1:15 a.m. ← edit 2 →

P8 Outline (d):

First, create a digit retrieval system with $\mathcal{O}(N)$ ~\mathcal{O}(N)~ memory. Given the $i$ ~i~'th number and $j$ ~j~'th MSD (most significant digit), you can get the digit in $\mathcal{O}(\log N)$ ~\mathcal{O}(\log N)~. Next, form a list of $2^{19}$ ~2^{19}~ numbers. $2^{19}$ ~2^{19}~ is too big, so make the remaining missing numbers equal to the last number. then calculate the answer for this list of numbers and delete a suffix to get the final answer. Another way is to just make all the remaining missing numbers have length $0$ ~0~.

After doing this, form a segment tree which stores the length of the shortest number in this segment range; call this the value of the segment. Now for each segment, let $u$ ~u~ be the value of parent segment, and $v$ ~v~ be the value of this segment. If the segment is the root, use $u=0$ ~u=0~. You want to add all of the digits in the rectangle defined by

(all of the numbers in this segment) * ((u+1)'th MSD ... v'th MSD) to the answer array.

Notice that digits $u+1$ ~u+1~ to $v$ ~v~ are the same for all of the numbers in the segment, and also, $v-u$ ~v-u~ is bounded by the length of the segment (because the length changes by at most $1$ ~1~ each time). Then it is possible to perform multiplication in $\mathcal{O}((\text{segment length}) \log (\text{segment length}))$ to get all of the integers to add to the answer array, using Number Theoretic Transform.

After getting the answer array, do a bit of carrying and print the answer. The overall runtime is $\mathcal{O}(N \log^2 N)$ ~\mathcal{O}(N \log^2 N)~.

15

r3mark commented on Sept. 13, 2017, 2:53 a.m. ← edit 2 →

Here are some solution sketches:

P5: Sort the queries based on the index (least to greatest). For each query, greedily place the letters in the earliest possible location so that it does not interfere with any of the earlier queries with the same character (after sorting). This can be done by using a set or similar data structure. After that, sort the queries based on index (greatest to least now) and fill in the empty spaces with characters which have not yet been in a query (according to the second sort). It is not hard to see that this placement of characters will work if and only if any placement of characters works.

P6: The least number of moves is $N - X$ ~N - X~ where $X$ ~X~ is the length of the longest subarray of the second sequence which is also a subsequence of the first sequence. This is because minimizing the number of moves is maximizing the number of elements which are never directly moved. It is not hard to compute $X$ ~X~ (map each element to its index in the first sequence and apply a simple dp). The rest is fairly straightforward, though you need to keep track of the indices after each move using a fenwick tree.

P7: Using LCA's, each query is reduced to adding $V$ ~V~ to node $X$ ~X~, $V+1$ ~V+1~ to $par[X]$ ~par[X]~, $V+2$ ~V+2~ to $par[par[X]]$ ~par[par[X]]~, and so on (or $V, V-1, V-2, \dots$ ~V, V-1, V-2, \dots~). For each query, you can implement a double difference array idea (difference array of a difference array) so that you can apply each query in $\mathcal{O}(1)$ ~\mathcal{O}(1)~ and compute all the final values in a single dfs.

P8: Contact d via Discord.

5

maxhflow commented on Sept. 13, 2017, 5:59 a.m. ← edit 2 →

Very nice sketches.

For P7, I had a different idea, but I couldn't implement it in time since I didn't have the data structures needed in my code library. You can break every query into two arithmetic sequence range updates on a path in the tree--one ascending, and one descending. Then, we can handle these updates by doing a heavy-light decomposition of the tree, and keeping the appropriate segment tree variant for each chain. This means we can update our path doing range updates going up two chains in the HLD. This gets us to about $\mathcal{O}(S \log^2 N + N \log N)$ ~\mathcal{O}(S \log^2 N + N \log N)~. This type of approach would also handle interleaved 'update' and 'query' events, so it is definitely overly complex for the question.

1

Cueball1234 commented on Sept. 13, 2017, 5:49 p.m.

I am sorry, but I am still a little confused as to how to use heavy-light decomposition to add the distance to the target node to each node along the path from a to b. The tutorials I have seen for HLD only show how to get the maximum/minimum along the path from a to b, but here, how do you update all of the nodes? Thank you!

1

maxhflow commented on Sept. 14, 2017, 1:12 a.m. ← edit 3 →

The line of reasoning goes like this. The distances to the target will form two ascending/descending sequences as the path approaches the target bifurcation, and then goes past it. We can update our HLD by keeping an arithmetic progression segment tree at each HLD chain. This lets us update any range of our HLD chain by addition of an arithmetic progression. This means we can update any node by doing at most 2 (2 in the case where the target bifurcation is in a chain, 1 in all other cases) range update operations. Also, there are at most $\mathcal{O}(\log N)$ ~\mathcal{O}(\log N)~ chains. Hence, we need to do only $\mathcal{O}(\log^2 N)$ ~\mathcal{O}(\log^2 N)~ work to update every node in the path.

In short, you can update an entire sub-range of a HLD chain efficiently with a segment tree that supports range updates. This means we don't need to do some operation for each node in a path.

1

Cueball1234 commented on Sept. 14, 2017, 6:26 p.m.

Ah I see, thank you so much for all your help!

5

imaxblue commented on Sept. 9, 2017, 12:18 p.m. ← edited →

You might also want to constant optimize to prevent TLEing by a small margin.

Is this intended for me?

https://dmoj.ca/contest/tle16c5/ranking/