ANewHope
SRM 678 · 2016-01-04 · by ltaravilse
SRM 678 · 2016-01-04 · by ltaravilse · Math
Problem Statement
Problem Statement
In a galaxy far far away... each week has N days.
Luke Skywalker has exactly N shirts.
The shirts are numbered 1 through N.
Each day he wears one of those N shirts.
Each week he wears each shirt exactly once.
In different weeks Luke may wear his shirts in different orders.
However, not all orders are always possible.
Whenever Luke wears a shirt for a day, he has to wash it before he can use it again.
Washing and drying a shirt takes D-1 full days.
In other words, if he wears a shirt on day x, the earliest day when he can wear it again is day x+D.
Master Yoda recently sent Luke on a training mission that lasted for some unknown number of full N-day weeks. He remembers the order in which he wore his shirts during the first week of the mission. He also remembers the order in which he wore his shirts during the last week of the mission. You are given this information inint[] s firstWeek and lastWeek.
Each of these int[] s contains N elements: the numbers of shirts he wore during that week, in order.
You are also given the number of days D that it takes to wash a shirt.
For example, assume that N = 4, firstWeek = {1,2,3,4}, and lastWeek = {4,3,2,1} and D = 3. It is possible that this particular mission took four weeks. One possible order in which Luke could have worn his shirts looks as follows:
Luke Skywalker has exactly N shirts.
The shirts are numbered 1 through N.
Each day he wears one of those N shirts.
Each week he wears each shirt exactly once.
In different weeks Luke may wear his shirts in different orders.
However, not all orders are always possible.
Whenever Luke wears a shirt for a day, he has to wash it before he can use it again.
Washing and drying a shirt takes D-1 full days.
In other words, if he wears a shirt on day x, the earliest day when he can wear it again is day x+D.
Master Yoda recently sent Luke on a training mission that lasted for some unknown number of full N-day weeks. He remembers the order in which he wore his shirts during the first week of the mission. He also remembers the order in which he wore his shirts during the last week of the mission. You are given this information in
For example, assume that N = 4, firstWeek = {1,2,3,4}, and lastWeek = {4,3,2,1} and D = 3. It is possible that this particular mission took four weeks. One possible order in which Luke could have worn his shirts looks as follows:
- week 1: {1,2,3,4}
- week 2: {2,3,4,1}
- week 3: {3,4,2,1}
- week 4: {4,3,2,1}
Notes
- N can be calculated as the number of elements of firstWeek
Constraints
- firstWeek will contain between 2 and 2500 integers inclusive.
- firstWeek and lastWeek will contain the same number of elements.
- firstWeek and lastWeek will represent permutations of the first N positive integers.
- D will be between 1 and N-1 inclusive.
Examples
0)
{1,2,3,4}
{4,3,2,1}
3
Returns: 4
The example from the problem statement.
1)
{8,5,4,1,7,6,3,2}
{2,4,6,8,1,3,5,7}
3
Returns: 3
2)
{1,2,3,4}
{1,2,3,4}
2
Returns: 1
Be careful, the first week and the last week can be the same week.
3)
{44,36,71,33,13,59,32,11,54,19,74,69,16,50,24,49,41,73,7,43,58,1,46,57,62,12,3,6,55,40,65,2,23,67,29,15,4,39,17,52,18,21,10,5,31,60,56,20,64,38,47,61,42,68,72,26,34,9,25,45,30,22,53,28,27,37,63,8,48,51,35,70,14,66}
{40,26,38,53,22,3,18,46,20,65,74,72,58,42,34,57,39,61,24,45,17,44,71,41,29,23,33,73,30,10,9,14,12,60,31,27,32,6,13,70,1,4,28,19,25,59,35,69,5,47,21,15,67,8,55,62,16,7,51,43,50,37,66,54,48,2,11,64,56,36,63,68,52,49}
71
Returns: 21
4)
{113,29,106,28,74,13,77,89,57,102,112,100,108,56,20,48,91,16,84,44,114,21,5,36,62,54,72,82,50,27,105,31,7,30,96,42,11,32,117,87,99,78,79,103,8,104,1,10,61,86,75,41,15,59,101,67,38,64,119,66,51,9,40,73,37,71,55,60,98,33,43,58,69,83,110,109,115,97,65,6,45,23,68,88,80,39,12,111,26,18,22,35,17,95,63,46,19,47,4,24,92,34,81,49,53,14,2,93,52,85,116,3,76,70,25,94,90,107,118}
{43,42,66,8,35,40,5,29,10,71,34,65,96,41,103,87,119,37,27,100,110,77,76,118,17,22,107,57,46,28,80,98,4,53,104,101,50,36,94,31,47,83,73,44,61,69,74,93,79,75,19,91,89,1,92,55,78,70,33,109,67,45,52,59,105,116,102,56,32,108,90,54,82,26,14,12,3,106,72,21,84,38,111,16,99,117,85,9,97,23,62,88,49,18,63,13,15,2,24,20,112,6,51,11,58,48,30,113,60,115,68,64,7,95,81,114,86,25,39}
74
Returns: 4
Submissions are judged against all 55 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class ANewHope with a public method int count(vector<int> firstWeek, vector<int> lastWeek, int D) · 55 test cases · 2 s / 256 MB per case