competitive programming

Codeforces 984E Elevator

The problem: Codeforces 984E Elevator
I failed to solve the problem by myself although I believed it should be solved by dp immediately after I read the problem. The difficult and interesting part of this problem is how to arrange the state of the whole process so that the total number of state is as small as possible.
Let’s think about it. For a state transition, we need to know:

  1. How many people have got in the elevator(may have got out).
  2. Current floor.
  3. Which floors do people currently in the elevator want to go.

The only problem is third one. There are at most 4 people in the elevator and each person may go to each of the 9 floors. So there would be
$$ 10^4=10000 $$
states in total in the 3rd dimension of dp.
However, it is a little bit more than we can afford. Actually some of the states in the above are repeated. Say, person 1 goes to floor 3 and person 2 goes to floor 4 is the same as person 1 goes to floor 4 and person 2 goes to 3. So we only care about how many people go to each floor, with no need to know who. Hence the total number of state is:
$$ \binom{9}{0} + \binom{9}{1} + \binom{9}{2} + \binom{9}{3} + \binom{9}{4} = 256 $$

This enable us to get accepted.
And some technique should be adopted to represent the state. Instead of using integers, we use a 4-char-long string to represent a state. With the help of map, we can implement it nicely:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

#include <iostream>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <map>

using namespace std;

#define int_ int64_t
#define pb push_back
#define mp make_pair
#define ll long long
#define ull unsigned ll
#define db double
#define INF 0x3f3f3f3f
#define MOD 1000003
#define PII pair<int, int>

const int N=2010;
int n,a[N],b[N];
map<string,int> dp[N][10];

int dfs(int idx,int cur,const string& s) {
    if (idx>n&&s=="0000") { return 0; }
    int& res=dp[idx][cur][s];
    if (res) return res;
    res=INF;
    for (char c='1';c<='9';c++) {
        string t=s;
        int x=0;
        for (int i=0;i<4;i++) {
            if (t[i]==c) t[i]='0',x++;
        }
        int now=idx;
        for (int i=0;i<4;i++) {
            if (t[i]=='0'&&now<=n&&a[now]+'0'==c) {
                t[i]=b[now++]+'0';
                x++;
            }
        }
        sort(t.begin(),t.end());
        if (idx==now&&t==s) continue;
        res=min(res,abs(cur-(c-'0'))+x+dfs(now,c-'0',t));
    }
    return res;
}

int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++) {
        scanf("%d%d",a+i,b+i);
    }
    printf("%d\n",dfs(1,1,"0000"));
}