Submission #466081

#	Time	Username	Problem	Language	Result	Execution time	Memory
466081		ChrisGe123	Calvinball championship (CEOI15_teams)	C++14	100 / 100	125 ms	536 KiB

teams

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
// #include <ext/pb_ds/tree_policy.hpp>
// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;
// template <class T> using Tree = tree<T, null_type, less<T>,
//     rb_tree_tag, tree_order_statistics_node_update>;

const int maxn = 10001;
#define mp make_pair
#define pb push_back
#define f first
#define s second

const int mod = 1000007;

typedef pair<int, int> pii;
int n;
int seq[maxn];
ll dp[2][maxn]; // we're going to sliding window on the first dimension

/*
We're looking at sequences of the integers 1..k, where the first occurrence of 1..k are in precisely that order
- interesting note: this means that all sequences should start with 1
Want to find how many of these sequences appear lexicographically before our current sequence

number of seuqences of each length
1: 1
2: 2
3: 5
4: 15

1 2 2
- Everything with 1 1 is before: there are 2 options (that's easy to count)
- Everything with 1 2 1 is before: only 1 option
- this should be 4

Observation: the first n numbers in a length n+1 sequence also form a valid sequence (maybe we'll just call them sequences from now on)
- from a length n sequence where the numbers 1..k are used, you have k+1 options for the next thing to append to it

1 2 3 2
- everything that starts with a sequence that is before 1 2 3 is before it
- this is still problematic though because of the fact that the number of ways to make a sequence of length 4 depends on the numbers used 

What if we have a function S(n, k) that tells us the number of sequences of size n that use 1..k
S(n+1, k) = S(n, k-1) + kS(n, k)
This is stirling numbers of the second kind
So the number of sequences is the Bell numbers

Size n = number of ways to partition a set of size n, the largest element we use should somehow correlate to the number of subsets
There should be one subset per each number
Wait this bijection is literally what the question is asking

So I guess back to the examples: 1 2 3 2
The problem is that we don't just need the number of 3-sequences below 1 2 3, we need for each sequence the highest k value that it uses, which seems a lot harder to get

Is it easy to count everything that starts with 1 1? 
- yes because there should just be 5 (the number of length 3 sequences)
What about 1 2 1: this is fine for now because there's only one more option, but what about when we need something of like length 5
- Ok this fowards strategy seems quite bad

This still feels like a dp problem
Let T(m, k) be the number of sequences of size m using 1..k that are strictly lower in lexicographic order than the first m elements of our sequence
Answer would be sum of the T(n, 1..n)
There are n^2 states = 10^8 which might run in time

The transition
T(i+1, j) = (number of sequences that perfectly match first i and have lower i+1th position) + T(i, j-1) + jT(i, j)
This seems O(1) enough
Figuring out the first part is just a matter of preprocessing which numbers are used at each point in our given sequence

Sliding window so that we have enough memory
*/

void setupIO(string s)
{
	freopen((s + ".in").c_str(), "r", stdin);
	freopen((s + ".out").c_str(), "w", stdout);
}


int main()
{
	//setupIO("calvinball");
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for (int i=0; i<n; i++)
	{
		cin >> seq[i];
	}
	int largestnum = 1;
	for (int i=1; i<n; i++)
	{
		for (int j=1; j<=i+1; j++)
		{
			dp[i%2][j] = (dp[(i-1)%2][j-1] + j*dp[(i-1)%2][j])%mod;
			if (largestnum == j)
			{
				dp[i%2][j] = (dp[i%2][j]+seq[i]-1)%mod;
				//because seq[i] is at most largestnum+1, so the largest number used in any sequence that's the first i-1 terms + something lower than seq[i] is largestnum
			}
		}
		largestnum = max(largestnum, seq[i]);
	}
	ll ans = 1;
	for (int i=1; i<=n; i++)
	{
		ans = (ans + dp[(n-1)%2][i])%mod;
	}
	cout << ans << endl;
}

Compilation message (stderr)

teams.cpp: In function 'void setupIO(std::string)':
teams.cpp:78:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |  freopen((s + ".in").c_str(), "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
teams.cpp:79:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |  freopen((s + ".out").c_str(), "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10