Skip to content

Commit dc9a046

Browse files
daiwbdaiwb
committed
TC config
1 parent fca5422 commit dc9a046

File tree

2 files changed

+319
-0
lines changed

2 files changed

+319
-0
lines changed

‎TopCoder/Tournaments/TCO14/R2C/InverseRMQ.cpp‎

Lines changed: 300 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,300 @@
1+
// BEGIN CUT HERE
2+
3+
// END CUT HERE
4+
#include <algorithm>
5+
#include <iostream>
6+
#include <sstream>
7+
#include <string>
8+
#include <vector>
9+
#include <queue>
10+
#include <set>
11+
#include <map>
12+
#include <cstdio>
13+
#include <cstdlib>
14+
#include <cctype>
15+
#include <cmath>
16+
#include <string>
17+
#include <cstring>
18+
using namespace std;
19+
20+
// BEGIN CUT HERE
21+
#define ARRSIZE(x) (sizeof(x)/sizeof(x[0]))
22+
23+
template<typename T> void print( T a ) {
24+
cerr << a;
25+
}
26+
static void print( long long a ) {
27+
cerr << a << "L";
28+
}
29+
static void print( string a ) {
30+
cerr << '"' << a << '"';
31+
}
32+
template<typename T> void print( vector<T> a ) {
33+
cerr << "{";
34+
for ( int i = 0 ; i != a.size() ; i++ ) {
35+
if ( i != 0 ) cerr << ", ";
36+
print( a[i] );
37+
}
38+
cerr << "}" << endl;
39+
}
40+
template<typename T> void eq( int n, T have, T need ) {
41+
if ( have == need ) {
42+
cerr << "Case " << n << " passed." << endl;
43+
} else {
44+
cerr << "Case " << n << " failed: expected ";
45+
print( need );
46+
cerr << " received ";
47+
print( have );
48+
cerr << "." << endl;
49+
}
50+
}
51+
template<typename T> void eq( int n, vector<T> have, vector<T> need ) {
52+
if( have.size() != need.size() ) {
53+
cerr << "Case " << n << " failed: returned " << have.size() << " elements; expected " << need.size() << " elements.";
54+
print( have );
55+
print( need );
56+
return;
57+
}
58+
for( int i= 0; i < have.size(); i++ ) {
59+
if( have[i] != need[i] ) {
60+
cerr << "Case " << n << " failed. Expected and returned array differ in position " << i << ".";
61+
print( have );
62+
print( need );
63+
return;
64+
}
65+
}
66+
cerr << "Case " << n << " passed." << endl;
67+
}
68+
static void eq( int n, string have, string need ) {
69+
if ( have == need ) {
70+
cerr << "Case " << n << " passed." << endl;
71+
} else {
72+
cerr << "Case " << n << " failed: expected ";
73+
print( need );
74+
cerr << " received ";
75+
print( have );
76+
cerr << "." << endl;
77+
}
78+
}
79+
// END CUT HERE
80+
81+
#define REP(i,n) for(int i=0;i<(n);++i)
82+
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
83+
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
84+
#define FOREACH(it,c) for(typeof((c).begin())it=(c).begin();it!=(c).end();++it)
85+
#define CLR(x) memset((x),0,sizeof((x)))
86+
#define SORT(x) sort(x.begin(), x.end())
87+
#define REVERSE(x) reverse(x.begin(), x.end())
88+
#define SZ(x) x.size()
89+
#define MP make_pair
90+
#define MPI make_pair<int, int>
91+
#define PB push_back
92+
typedef long long LL;
93+
typedef vector<bool> VB;
94+
typedef vector<int> VI;
95+
typedef vector<vector<int> > VVI;
96+
typedef vector<string> VS;
97+
typedef pair<int, int> PI;
98+
typedef vector<pair<int, int> > VPI;
99+
100+
// BEGIN CUT HERE
101+
vector<string> split( const string& s, const string& delim =" " ) {
102+
vector<string> res;
103+
string t;
104+
for ( int i = 0 ; i != s.size() ; i++ ) {
105+
if ( delim.find( s[i] ) != string::npos ) {
106+
if ( !t.empty() ) {
107+
res.push_back( t );
108+
t = "";
109+
}
110+
} else {
111+
t += s[i];
112+
}
113+
}
114+
if ( !t.empty() ) {
115+
res.push_back(t);
116+
}
117+
return res;
118+
}
119+
120+
vector<int> splitInt( const string& s, const string& delim =" " ) {
121+
vector<string> tok = split( s, delim );
122+
vector<int> res;
123+
for ( int i = 0 ; i != tok.size(); i++ )
124+
res.push_back( atoi( tok[i].c_str() ) );
125+
return res;
126+
}
127+
// END CUT HERE
128+
129+
// BEGIN CUT HERE
130+
int s2i(string s) {
131+
stringstream ss;
132+
ss << s;
133+
int res;
134+
ss >> res;
135+
return res;
136+
}
137+
138+
string i2s(int n) {
139+
stringstream ss;
140+
ss << n;
141+
string res;
142+
ss >> res;
143+
return res;
144+
}
145+
// END CUT HERE
146+
147+
class seg {
148+
public:
149+
int val;
150+
PI uni, ins;
151+
bool operator<(const seg& rhs) const {
152+
return val < rhs.val;
153+
}
154+
};
155+
156+
vector<seg> mm;
157+
158+
int doit(PI p, int cnt) {
159+
VPI t;
160+
t.PB(p);
161+
REP(j,cnt) {
162+
PI u = mm[j].uni;
163+
VPI q;
164+
REP(k,SZ(t)) {
165+
PI now = t[k];
166+
if (u.second < now.first) q.PB(now);
167+
else if (u.first > now.second) q.PB(now);
168+
else {
169+
if (u.first > now.first) q.PB(MP(now.first, u.first - 1));
170+
if (u.second < now.second) q.PB(MP(u.second + 1, now.second));
171+
}
172+
}
173+
t = q;
174+
}
175+
176+
int sum = 0;
177+
REP(ii,SZ(t)) {
178+
sum += t[ii].second - t[ii].first + 1;
179+
}
180+
181+
return sum;
182+
}
183+
184+
class InverseRMQ {
185+
public:
186+
string possible(int n, vector <int> A, vector <int> B, vector <int> ans) {
187+
n = n;
188+
mm.clear();
189+
REP(i,SZ(A)) {
190+
seg s;
191+
s.val = ans[i];
192+
s.uni = MP(A[i], B[i]);
193+
s.ins = MP(A[i], B[i]);
194+
mm.PB(s);
195+
}
196+
SORT(mm);
197+
int idx = 0;
198+
REP(i,SZ(A)) {
199+
int next = i + 1;
200+
while (next < SZ(A) && mm[next].val == mm[i].val) {
201+
int a = mm[next].uni.first, b = mm[next].uni.second;
202+
mm[i].uni.first = min(mm[i].uni.first, a);
203+
mm[i].uni.second = max(mm[i].uni.second, b);
204+
mm[i].ins.first = max(mm[i].ins.first, a);
205+
mm[i].ins.second = min(mm[i].ins.second, b);
206+
++next;
207+
}
208+
if (mm[i].ins.first > mm[i].ins.second) return "Impossible";
209+
mm[idx++] = mm[i];
210+
i = next - 1;
211+
}
212+
mm.erase(mm.begin() + idx, mm.end());
213+
214+
int used = 0;
215+
REP(i,SZ(mm)) {
216+
int sum = doit(mm[i].ins, i);
217+
if (sum == 0) return "Impossible";
218+
219+
used += doit(mm[i].uni, i);
220+
if (used > mm[i].val) return "Impossible";
221+
}
222+
223+
return "Possible";
224+
}
225+
};
226+
// BEGIN CUT HERE
227+
int main() {
228+
{
229+
int AARRAY[] = {2,5};
230+
vector <int> A( AARRAY, AARRAY+ARRSIZE(AARRAY) );
231+
int BARRAY[] = {6,8};
232+
vector <int> B( BARRAY, BARRAY+ARRSIZE(BARRAY) );
233+
int ansARRAY[] = {3,3};
234+
vector <int> ans( ansARRAY, ansARRAY+ARRSIZE(ansARRAY) );
235+
InverseRMQ theObject;
236+
eq(0, theObject.possible(9, A, B, ans),"Impossible");
237+
}
238+
{
239+
int AARRAY[] = {1,2,4};
240+
vector <int> A( AARRAY, AARRAY+ARRSIZE(AARRAY) );
241+
int BARRAY[] = {2,4,5};
242+
vector <int> B( BARRAY, BARRAY+ARRSIZE(BARRAY) );
243+
int ansARRAY[] = {3,4,5};
244+
vector <int> ans( ansARRAY, ansARRAY+ARRSIZE(ansARRAY) );
245+
InverseRMQ theObject;
246+
eq(0, theObject.possible(5, A, B, ans),"Possible");
247+
}
248+
{
249+
int AARRAY[] = {1,2,3};
250+
vector <int> A( AARRAY, AARRAY+ARRSIZE(AARRAY) );
251+
int BARRAY[] = {1,2,3};
252+
vector <int> B( BARRAY, BARRAY+ARRSIZE(BARRAY) );
253+
int ansARRAY[] = {3,3,3};
254+
vector <int> ans( ansARRAY, ansARRAY+ARRSIZE(ansARRAY) );
255+
InverseRMQ theObject;
256+
eq(1, theObject.possible(3, A, B, ans),"Impossible");
257+
}
258+
{
259+
int AARRAY[] = {1,101,201,301,401,501};
260+
vector <int> A( AARRAY, AARRAY+ARRSIZE(AARRAY) );
261+
int BARRAY[] = {100,200,300,400,500,600};
262+
vector <int> B( BARRAY, BARRAY+ARRSIZE(BARRAY) );
263+
int ansARRAY[] = {100,200,300,400,500,600};
264+
vector <int> ans( ansARRAY, ansARRAY+ARRSIZE(ansARRAY) );
265+
InverseRMQ theObject;
266+
eq(2, theObject.possible(600, A, B, ans),"Possible");
267+
}
268+
{
269+
int AARRAY[] = {1234,1234};
270+
vector <int> A( AARRAY, AARRAY+ARRSIZE(AARRAY) );
271+
int BARRAY[] = {5678,5678};
272+
vector <int> B( BARRAY, BARRAY+ARRSIZE(BARRAY) );
273+
int ansARRAY[] = {10000,20000};
274+
vector <int> ans( ansARRAY, ansARRAY+ARRSIZE(ansARRAY) );
275+
InverseRMQ theObject;
276+
eq(3, theObject.possible(1000000000, A, B, ans),"Impossible");
277+
}
278+
{
279+
int AARRAY[] = {1,2,3,4,5,6,7,8};
280+
vector <int> A( AARRAY, AARRAY+ARRSIZE(AARRAY) );
281+
int BARRAY[] = {1,2,3,4,5,6,7,8};
282+
vector <int> B( BARRAY, BARRAY+ARRSIZE(BARRAY) );
283+
int ansARRAY[] = {4,8,2,5,6,3,7,1};
284+
vector <int> ans( ansARRAY, ansARRAY+ARRSIZE(ansARRAY) );
285+
InverseRMQ theObject;
286+
eq(4, theObject.possible(8, A, B, ans),"Possible");
287+
}
288+
{
289+
int AARRAY[] = {1};
290+
vector <int> A( AARRAY, AARRAY+ARRSIZE(AARRAY) );
291+
int BARRAY[] = {1000000000};
292+
vector <int> B( BARRAY, BARRAY+ARRSIZE(BARRAY) );
293+
int ansARRAY[] = {19911120};
294+
vector <int> ans( ansARRAY, ansARRAY+ARRSIZE(ansARRAY) );
295+
InverseRMQ theObject;
296+
eq(5, theObject.possible(1000000000, A, B, ans),"Impossible");
297+
}
298+
return 0;
299+
}
300+
// END CUT HERE

‎TopCoder/Tournaments/TCO14/R2C/InverseRMQ.html‎

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
<html><body bgcolor="#ffffff" text="#000000"><table><tr><td colspan="2"><h3>Problem Statement</h3></td></tr><tr><td>&#160;&#160;&#160;&#160;</td><td>The range maximum query (RMQ) problem looks as follows:
2+
You are given a permutation P of the numbers 1 through <b>n</b>, and a sequence of queries.
3+
Each query is a pair of integers (L,R) such that 1 &lt;= L &lt;= R &lt;= <b>n</b>.
4+
The answer to the query is the maximum of the values that occur in P at (1-based) positions L through R, inclusive.
5+
<br></br>
6+
<br></br>
7+
For example, if P is the permutation (3,1,4,2,5), then:
8+
<ul>
9+
<li>The answer to the query (1,2) is max(3,1)=3.</li>
10+
<li>The answer to the query (2,4) is max(1,4,2)=4.</li>
11+
<li>The answer to the query (4,5) is max(2,5)=5.</li>
12+
</ul>
13+
<br></br>
14+
<br></br>
15+
In this problem, we ask you to solve the inverse problem.
16+
You are given the int <b>n</b>, and three vector &lt;int&gt;s <b>A</b>, <b>B</b>, and <b>ans</b>, each containing the same number of elements.
17+
We are looking for a permutation P of numbers 1 through <b>n</b> with the following property:
18+
For each valid i, the answer to the query (<b>A</b>[i], <b>B</b>[i]) must be <b>ans</b>[i].
19+
Return "Possible" (quotes for clarity) if at least one such permutation P exists, and "Impossible" otherwise.</td></tr><tr><td colspan="2"><h3>Definition</h3></td></tr><tr><td>&#160;&#160;&#160;&#160;</td><td><table><tr><td>Class:</td><td>InverseRMQ</td></tr><tr><td>Method:</td><td>possible</td></tr><tr><td>Parameters:</td><td>int, vector &lt;int&gt;, vector &lt;int&gt;, vector &lt;int&gt;</td></tr><tr><td>Returns:</td><td>string</td></tr><tr><td>Method signature:</td><td>string possible(int n, vector &lt;int&gt; A, vector &lt;int&gt; B, vector &lt;int&gt; ans)</td></tr><tr><td colspan="2">(be sure your method is public)</td></tr></table></td></tr><tr><td colspan="2"><h3>Limits</h3></td></tr><tr><td>&#160;&#160;&#160;&#160;</td><td><table><tr><td>Time limit (s):</td><td>2.000</td></tr><tr><td>Memory limit (MB):</td><td>256</td></tr></table></td></tr><tr><td colspan="2"><h3>Constraints</h3></td></tr><tr><td align="center" valign="top">-</td><td><b>n</b> will be between 1 and 1,000,000,000, inclusive.</td></tr><tr><td align="center" valign="top">-</td><td><b>A</b> will contain between 1 and 50 elements, inclusive.</td></tr><tr><td align="center" valign="top">-</td><td><b>A</b>, <b>B</b>, and <b>ans</b> will each contain the same number of elements.</td></tr><tr><td align="center" valign="top">-</td><td>Each element in <b>A</b> will be between 1 and <b>n</b>, inclusive.</td></tr><tr><td align="center" valign="top">-</td><td>Each element in <b>B</b> will be between 1 and <b>n</b>, inclusive.</td></tr><tr><td align="center" valign="top">-</td><td>For all i, <b>A</b>[i] will be less than or equal to <b>B</b>[i].</td></tr><tr><td align="center" valign="top">-</td><td>Each element in <b>ans</b> will be between 1 and <b>n</b>, inclusive.</td></tr><tr><td colspan="2"><h3>Examples</h3></td></tr><tr><td align="center" nowrap="true">0)</td><td></td></tr><tr><td>&#160;&#160;&#160;&#160;</td><td><table><tr><td><table><tr><td><pre>5</pre></td></tr><tr><td><pre>{1,2,4}</pre></td></tr><tr><td><pre>{2,4,5}</pre></td></tr><tr><td><pre>{3,4,5}</pre></td></tr></table></td></tr><tr><td><pre>Returns: &quot;Possible&quot;</pre></td></tr><tr><td><table><tr><td colspan="2">This is the example from the problem statement. One valid permutation is (3,1,4,2,5). There are also some other valid permutations.</td></tr></table></td></tr></table></td></tr><tr><td align="center" nowrap="true">1)</td><td></td></tr><tr><td>&#160;&#160;&#160;&#160;</td><td><table><tr><td><table><tr><td><pre>3</pre></td></tr><tr><td><pre>{1,2,3}</pre></td></tr><tr><td><pre>{1,2,3}</pre></td></tr><tr><td><pre>{3,3,3}</pre></td></tr></table></td></tr><tr><td><pre>Returns: &quot;Impossible&quot;</pre></td></tr><tr><td><table><tr><td colspan="2">The only sequence that corresponds to these queries is (3,3,3), but that is not a permutation.</td></tr></table></td></tr></table></td></tr><tr><td align="center" nowrap="true">2)</td><td></td></tr><tr><td>&#160;&#160;&#160;&#160;</td><td><table><tr><td><table><tr><td><pre>600</pre></td></tr><tr><td><pre>{1,101,201,301,401,501}</pre></td></tr><tr><td><pre>{100,200,300,400,500,600}</pre></td></tr><tr><td><pre>{100,200,300,400,500,600}</pre></td></tr></table></td></tr><tr><td><pre>Returns: &quot;Possible&quot;</pre></td></tr><tr><td><table><tr><td colspan="2">One valid permutation is the permutation (1,2,3,...,600).</td></tr></table></td></tr></table></td></tr><tr><td align="center" nowrap="true">3)</td><td></td></tr><tr><td>&#160;&#160;&#160;&#160;</td><td><table><tr><td><table><tr><td><pre>1000000000</pre></td></tr><tr><td><pre>{1234,1234}</pre></td></tr><tr><td><pre>{5678,5678}</pre></td></tr><tr><td><pre>{10000,20000}</pre></td></tr></table></td></tr><tr><td><pre>Returns: &quot;Impossible&quot;</pre></td></tr><tr><td><table><tr><td colspan="2">There is no permutation such that two identical queries have different answers.</td></tr></table></td></tr></table></td></tr><tr><td align="center" nowrap="true">4)</td><td></td></tr><tr><td>&#160;&#160;&#160;&#160;</td><td><table><tr><td><table><tr><td><pre>8</pre></td></tr><tr><td><pre>{1,2,3,4,5,6,7,8}</pre></td></tr><tr><td><pre>{1,2,3,4,5,6,7,8}</pre></td></tr><tr><td><pre>{4,8,2,5,6,3,7,1}</pre></td></tr></table></td></tr><tr><td><pre>Returns: &quot;Possible&quot;</pre></td></tr><tr><td><table><tr><td colspan="2">The only valid permutation is clearly (4,8,2,5,6,3,7,1).</td></tr></table></td></tr></table></td></tr><tr><td align="center" nowrap="true">5)</td><td></td></tr><tr><td>&#160;&#160;&#160;&#160;</td><td><table><tr><td><table><tr><td><pre>1000000000</pre></td></tr><tr><td><pre>{1}</pre></td></tr><tr><td><pre>{1000000000}</pre></td></tr><tr><td><pre>{19911120}</pre></td></tr></table></td></tr><tr><td><pre>Returns: &quot;Impossible&quot;</pre></td></tr><tr><td><table><tr><td colspan="2">Obviously, for <b>n</b>=1,000,000,000 the maximum of the entire permutation must be 1,000,000,000.</td></tr></table></td></tr></table></td></tr></table><p>This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved. </p></body></html>

0 commit comments

Comments
 (0)