New Year's 2016

It's almost 2016! A new year means setting new year resolutions, bettering yourself, and of course — a contest!

The problem writers this time will be k_53P, cheesecake, awaykened, Xyene, and FatalEagle.

The pretest/systest format will not be used. This means that submissions will be judged on the full set of data during the contest. However, partial output will be disabled.

This contest will be rated for all participants.

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

The contest will run from Jan 1, 12 PM EST to Jan 3, 12 PM EST. It will consist of 7-8 problems in approximated increasing order of difficulty. The problems will be allotted different point values based on their difficulties. As usual, if you cannot fully solve a problem, there are subtasks you can complete for partial points. We encourage contestants to read all problems and go for these partial marks. It is also highly recommended that you join and start the contest as soon as possible since ties are broken by your submission times.

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. Your last submission time 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++.

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

Good luck and Happy New Year!

Problems

Problem	Points	AC Rate	Users	Editorials
New Year's '16 P1 - Late Christmas Shopping	3p	30.2%	185	Editorial
New Year's '16 P2 - The 365 Days of Christmas	5p	25.1%	145	Editorial
New Year's '16 P3 - Arithmetic Snowman	5p	15.7%	228	Editorial
New Year's '16 P4 - DIY Christmas Tree	10p	34.3%	66	Editorial
New Year's '16 P5 - Eggnog Dilemma	12p	5.6%	27	Editorial
New Year's '16 P6 - Cake Balancing	15p	41.2%	131	Editorial
New Year's '16 P7 - Old Christmas Lights	17p	19.0%	128	Editorial
New Year's '16 P8 - S-NO-wall	20p	16.5%	69	Editorial

Comments

9

cheesecake commented on Jan. 3, 2016, 5:06 p.m. ← edited →

There won't be an official editorial so here are some rough solution sketches and hints:

P1 - Apologies once again for the issues with test data. Anyone who still WAs on the last case needs to consider the case where one bag has multiple copies of the same item.

P2 - Easy implementation, most errors were on the suffixes for the numbers.

P3 - Constraints were set loosely on this problem. Counting the occurrences of each size and sorting the sizes gives us a $\mathcal{O}(N^2)$ ~\mathcal{O}(N^2)~ solution.

P4 - Multiple ways to approach this problem. One way is to DFS and get the size of the subtree rooted at each node. Number the nodes by depth and from left to right. For node $i$ ~i~, leave a "gap" between node $i$ ~i~ and node $i-1$ ~i-1~ equal to the size of $i$ ~i~'s subtree.

P5 - Consider a restricted version of the problem where $D = 1$ ~D = 1~. Some may have noticed that the inspiration for the problem came from a famous puzzle involving a king, some prisoners, and a poisoned barrel of wine.

P6 - Standard bitmask DP. The state is $dp[i][j]$ ~dp[i][j]~, the minimum number of moves required to reach the state where $i$ ~i~ represents the items in the left pan and $j$ ~j~ represents the items in the right pan.

P7 - Consider a restricted version of the problem where queries have no upper bound. In other words, what is the maximum size consistent subarray of $[l:N]$ ~[l:N]~?

P8 - We can use segment tree where each node keeps track of the contiguous prefix and suffix length of 1s in that segment. When merging nodes, the new maximum contiguous section is either the prefix, suffix, or the new section created by merging the two.

Hope you guys enjoyed the contest. Happy new year!

0

XIAOAGE commented on Jan. 3, 2016, 5:38 p.m.

Anyone knows the puzzle name for problem 5?

0

alexyu commented on Jan. 3, 2016, 5:49 p.m. ← edited →

https://gurmeet.net/puzzles/poisoned-wine-barrels/

0

XIAOAGE commented on Jan. 3, 2016, 5:54 p.m.

Thx

0

odaniel commented on Jan. 3, 2016, 5:43 p.m.

"All the King's Wine"

0

XIAOAGE commented on Jan. 3, 2016, 5:54 p.m.

Thx

0

ahmedtn commented on Jan. 1, 2016, 5:39 p.m.

Pascal is not available for this contest?

Happy new year everybody :)

0

cheesecake commented on Jan. 1, 2016, 5:43 p.m.

P1 was on a separate judge, it's now available for all languages.

0

ahmedtn commented on Jan. 1, 2016, 5:52 p.m.

Thanks a lot!

9

cheesecake commented on Jan. 1, 2016, 5:34 a.m.

HAPPY NEW YEAR

4

bobhob314 commented on Jan. 1, 2016, 2:09 p.m.

YOU TOO BUD

6

moladan123 commented on Dec. 27, 2015, 2:11 a.m.

What kind of difficulty levels can we expect, roughly speaking?

4

cheesecake commented on Dec. 27, 2015, 4:57 a.m.

With lots of problems and lots of time, there will be something for everyone!

4

bobhob314 commented on Dec. 27, 2015, 11:01 a.m. ← edited →

If there will be something for Fatal, you, etc., it's going to be hard ;_;

3

d commented on Jan. 1, 2016, 2:53 a.m. ← edited →

They probably made an Aubrey Alston-style problem just for you (which is why there are 7 problems, not 6)

3

cheesecake commented on Jan. 1, 2016, 3:12 a.m.

There may be 8 problems actually, not confirmed yet :)

3

bobhob314 commented on Dec. 27, 2015, 2:16 a.m.

last year's was pretty hard :/