For a better experience please click here.
Solution: CF731D 80-th Level Archeology -- Letter, Interval, and Reverse Thinking
Link to the question: CF Luogu
Preface
Assertion: "STL set is the most 'powerful' tool throughout C++."
"Not because it is capable of various tasks, but because we don't need to code it ourselves."
What is lexicographical order?
Lexicographical order is an ordering of strings based on the ordering of characters. A string is less than another string when, at the first position of difference, the letter in the first string is less than the corresponding letter in the second.
It is the ordering of words in a dictionary.
E.g. In the normal alphabet, 'abceb'<'abdca' since 'c'<'d' at their third position, the first position of difference. Note that we only consider the first position of difference. Even though 'e' is greater than 'c' at the fourth position and 'b' is greater than 'a' at the fifth, they cannot affect our comparison.
P.s. We let the 'empty character' be the smallest. E.g. To compare 'an' and 'and', we may consider the third position of 'an' as the empty character, then 'an'<'and' as the empty character is less than 'd'.
Back to the question
"One operation replaces each letter with the next letter in the alphabet."
We try to find the number of operations to make all the words in lexicographical order.
Reverse Thinking: One operation replaces each letter in the alphabet with its previous one.
E.g. Consider the first example (We use letters to make it more intuitive). The strings are
cb
a
bca
bcab
and the alphabet is a<b<c.
After one operation, the strings become
ac
b
cab
cabc
which are in lexicographical order.
Reverse Thinking: after one operation, we 'rotate the alphabet' to c<a<b. And now, the strings are in lexicographical order based on our new alphabet.
The solution is to find a reordering of the alphabet to make the strings in lexicographical order.
How to reorder the alphabet?
"From the order of characters, we develop an order of strings."
Reverse Thinking: From the order of strings, we deduce the order of characters.
E.g. Given that 'ace'<'abd' in some alphabet, we know that 'c'<'b' in that alphabet (and this is the only information we can extract).
The method is: Find the first position of difference, then the character in the first string at that position is less than the corresponding character in the second string.
P.s. As we know that the empty character is invariantly the smallest, there is no alphabet satisfying 'and'<'an'.
To deal with this question, we assume that the strings are in lexicographical order in some alphabet, and by comparing strings, we know some orders between characters in that alphabet. At last, we check whether a rotation of the switch results in an alphabet satisfying all conditions.
We know that after rotation, the new alphabet must be in the form of
$$$a,a+1,\cdots,n-1,n,1,2,\cdots,a-1$$$
for some $$$a\in{1,\cdots, n},$$$ which is the smallest character (except empty character).
In the following text, we use '$$$<$$$' to denote the normal comparison between numbers, and '$$$\prec$$$' to denote the comparison in alphabetical order.
Case 1:
By comparing two strings, we know that $$$u\prec v,$$$ while $$$u<v.$$$
E.g. If the strings 1 2 3 < 1 3 2, then we know that $$$2\prec 3$$$ in this alphabet, while $$$2<3$$$ in number order.
We may use $$$u$$$ and $$$v$$$ to restrict the range of $$$a,$$$ the smallest character in the new alphabet.
The restriction is: $$$a\notin [u+1,v]$$$ because contrarily, if $$$a$$$ is in the range, the alphabet is
$$$a,a+1,\cdots,v,\cdots,n,1,\cdots,u,\cdots,a-1,$$$ where $$$v\prec u$$$ in the alphabet, a contradiction.
We may check that $$$a$$$ outside the interval satisfies $$$u\prec v.$$$
Case 2:
By comparing two strings, we know that $$$u\prec v,$$$ while $$$u>v.$$$
E.g. If the strings 1 3 2 < 1 2 3, then we know that $$$3\prec 2$$$ in this alphabet, while $$$3>2$$$ in number order.
The restriction now is: $$$a\in [v+1,u].$$$ (Why?)
Implementation
To combine all the restrictions, $$$a$$$ is
- not in the union of all the intervals of case 1;
- in the intersection of all the intervals of case 2.
For case 2, maintaining the intersection of intervals is easy. Suppose the current interval is $$$[l,r],$$$ then its intersection with $$$[u,v]$$$ is just $$$[\max(l,u),\min(r,v)].$$$ (If the right boundary is less than the left, then we regard it as the empty interval.)
For case 1, maintaining the union of intervals is not so easy. One offline method is to sort all the intervals by left boundaries, and then combine them if they have non-empty intersections.
However, I'd like to introduce an online method of maintaining unions of intervals, which is, sometimes, even easier to implement than the offline method.
Use STL set to maintain the union of intervals.
That's why it is the most powerful tool in C++
We let the set store disjoint intervals (i.e. intervals that don't intersect) in order. Whenever we try to add a new interval, we combine it with the existing intervals that intersect with it.
Our data structure:
struct T{int l,r;
bool operator<(T b)const{return r<b.l;}
};
set<T>//our data structure
Note the way we define the order between intervals (which is necessary when using set). We define an interval to be less than another only when the first is on the left of the second and they are disjoint. Thus, if two intervals intersect, the set considers them equal (more exactly, neither less than nor greater than).
Another important feature of set is its find() function, which returns the iterator (the pointer) to the first element that is 'equal' to our input.
Now, suppose we have a set with intervals $$${[1,3],[5,5],[7,9],[10,11]}$$$ and we want to add the interval $$$[2,8]$$$. What should we do?
- We use
find()to search for the first interval that intersects with $$$[2,8],$$$ which is $$$[1,3].$$$ Combine them to get $$$[1,8].$$$ Erase $$$[1,3]$$$ in the set. Now, our task becomes "adding $$$[1,8]$$$ to the set $$${[5,5],[7,9],[10,11]}$$$". - We find $$$[5,5]$$$ in the set. As it is already contained in $$$[1,8]$$$ we erase it from the set. Now, our task becomes "adding $$$[1,8]$$$ to the set $$${[7,9],[10,11]}$$$".
- We find $$$[7,9]$$$ in the set. Combine it with $$$[1,8]$$$ to get $$$[1,9]$$$. Now, our task becomes "adding $$$[1,9]$$$ to the set $$${[10,11]}$$$".
- As there is no interval in the set that interests with $$$[1,9],$$$ we add it to the set. The set becomes $$${[1,9],[10,11]}.$$$ Terminate.
The general procedure is: When adding an interval $$$[u,v]$$$ to the set $$$S$$$,
- if no interval in $$$S$$$ intersects with $$$[u,v],$$$ then add it by
insert()method. - otherwise, find the interval $$$[l,r]\in S$$$ that intersects with $$$[u,v].$$$
- combine them to get $$$[\min(u,l),\max(v,r)]$$$ and make it the new $$$[u,v].$$$
- remove $$$[l,r]$$$ from $$$S.$$$ Repeat step 1.
Derive the answer
Let $$$[l,r]$$$ be the intersection of intervals from case 2, then $$$a\in[l,r].$$$
Let $$$S$$$ be the union of intervals from case 1, then $$$a$$$ is not contained by any interval in $$$S$$$.
We may reformulate the second point: "$$$[a,a]$$$ does not intersect with any interval in $$$S.$$$" This makes our lives easier as we may use find() method to check if there is an interval in $$$S$$$ that is 'equal' to $$$[a,a],$$$ which means there is an interval that intersects with $$$[a,a].$$$
Lastly, if $$$a$$$ really exists, the number of operations is $$$(c+1-a)\bmod c.$$$ (Why?)
Complexity
Time: as there are $$$n$$$ strings, there are $$$O(n)$$$ restrictions (every comparison between adjacent strings gives at most one restriction). Each restriction in case 1 is an interval, which can only be inserted into the set, found by find(), and erased once. The set operations above take $$$O(\log n)$$$ times each (as the set has $$$O(n)$$$ elements), so overall the time complexity is $$$O(n\log n).$$$
Memory: $$$O(n).$$$
Code
In the following code, we use $$$[pl,pr]$$$ as the interval of 'possibility' (case 2). The set for case 1 is named ip for 'impossiblilty'.
//This program is written by Brian Peng.
#include<bits/stdc++.h>
using namespace std;
#define Rd(a) (a=rd())
#define Gc(a) (a=getchar())
#define Pc(a) putchar(a)
int rd(){
int x;char c(getchar());bool k;
while(!isdigit(c)&&c^'-')if(Gc(c)==EOF)exit(0);
c^'-'?(k=1,x=c&15):k=x=0;
while(isdigit(Gc(c)))x=x*10+(c&15);
return k?x:-x;
}
void wr(int a){
if(a<0)Pc('-'),a=-a;
if(a<=9)Pc(a|'0');
else wr(a/10),Pc((a%10)|'0');
}
signed const INF(0x3f3f3f3f),NINF(0xc3c3c3c3);
long long const LINF(0x3f3f3f3f3f3f3f3fLL),LNINF(0xc3c3c3c3c3c3c3c3LL);
#define Ps Pc(' ')
#define Pe Pc('\n')
#define Frn0(i,a,b) for(int i(a);i<(b);++i)
#define Frn1(i,a,b) for(int i(a);i<=(b);++i)
#define Frn_(i,a,b) for(int i(a);i>=(b);--i)
#define Mst(a,b) memset(a,b,sizeof(a))
#define File(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout)
#define N (1000010)
int n,c,w[2][N],l[2],pl(1),pr;
bool t;
struct T{int l,r;
bool operator<(T b)const{return r<b.l;}
};
set<T>ip;//set of case 1
set<T>::iterator it;
void mdf(int u,int v);//adding a restriction "u is less than v in the alphabet"
signed main(){
Rd(n),pr=Rd(c);//the possibility interval is originally set as [1,c]
Rd(l[t]);
Frn1(i,1,l[t])Rd(w[t][i]);
Frn1(i,2,n){
t^=1,cin>>l[t];
Frn1(i,1,l[t])Rd(w[t][i]);
w[t][l[t]+1]=0;//set the empty character
Frn1(i,1,l[t^1])if(w[t][i]!=w[t^1][i]){
if(!w[t][i])wr(-1),exit(0);//the case when the empty character
//is greater than another character, which is impossible
mdf(w[t^1][i],w[t][i]);//add restriction
break;
}
}
Frn1(i,pl,pr)if(ip.find({i,i})==ip.end())wr((c+1-i)%c),exit(0);
//check whether i is in the interval [pl,pr] for case 2
//while not contained in the set for case 1
wr(-1),exit(0);
}
void mdf(int u,int v){
if(u<v){//case 1
++u;//the interval added is [u+1,v]
while((it=ip.find({u,v}))!=ip.end())//find the interval in the set
//that intersects with it
u=min(u,it->l),v=max(u,it->r),ip.erase(it);//combine and remove
ip.insert({u,v});//insert the combined interval
}else pl=max(pl,v+1),pr=min(pr,u);//case 2
}
Extension
What if the question becomes that you can reorder the alphabet to any permutation of $$${1,\cdots,c}$$$?
We still need to find the restriction between characters. But now, as we don't have a specific reordering pattern, we may treat each restriction $$$u\prec v$$$ as a directed edge $$$u\to v$$$ in a graph with vertices $$${1,\cdots, c}.$$$ Then, we may find the reordering of the alphabet as a topological ordering of the vertices, if it exists (i.e. the graph is a DAG).
Do you want to ask me why I thought about this? Because I originally thought this is the solution, but I found it too difficult to find a topological order being a cycle of $$$(1,2,\cdots,n).$$$ Eventually, I came up with this solution, making use of the reordering being a cycle.
A slight change in question leading to a totally different method, maybe this is just why algorithms are so intriguing...
Comments (0)
