11402 - Ahoy, Pirates!

All about problems in Volume 114. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11402 - Ahoy, Pirates

Post by brianfry713 » Thu Jul 11, 2013 2:39 am

Input:

Code: Select all

1
1
64
110000011101011110011110110010001
345
F 951 1793
S 43 491
S 36 1431
I 1529 2065
I 516 946
S 344 1395
S 440 745
F 609 1598
F 410 1438
S 484 1211
I 956 1141
E 909 1447
E 1547 1793
I 1244 1500
I 334 398
E 807 1356
I 3 1616
S 586 1167
I 226 493
E 978 1562
E 71 1209
F 980 1808
S 401 661
F 490 1969
I 191 2108
E 82 1547
I 1550 1564
E 89 1374
I 379 1857
F 703 2006
S 760 1167
F 863 1837
E 137 1329
S 1819 2097
I 1397 1880
I 1159 1962
F 1414 1729
E 676 1867
E 422 1060
S 746 1189
I 1475 1950
I 162 1675
S 1813 2006
I 288 1862
I 603 1147
E 258 1173
S 1179 2051
F 752 1806
I 413 818
S 518 1629
E 581 992
E 1218 1748
I 1113 1794
F 1057 1465
S 91 2068
E 942 1193
E 261 1707
S 1013 1838
I 534 1490
S 1764 2009
S 24 542
E 242 297
I 134 2036
S 1045 1848
S 1137 1200
E 31 1827
I 601 1802
S 1426 1528
E 2009 2063
I 1299 1779
E 106 1803
S 2081 2101
F 187 1051
E 1133 2036
I 569 1188
E 24 904
S 673 1569
F 883 1583
S 780 1522
I 840 2080
I 138 182
S 3 108
I 67 1159
I 119 180
S 813 1216
S 838 1403
F 1511 1556
S 1047 1464
S 521 788
S 63 1425
I 1117 1608
I 1611 1927
E 678 1742
E 1729 1925
S 655 1094
E 385 770
F 1853 2005
S 281 1421
E 97 1704
I 160 1796
I 1342 1983
I 197 1221
F 631 1900
I 176 1581
F 188 2078
E 569 959
I 700 2010
F 802 982
E 574 706
I 322 1067
F 258 869
E 104 455
E 1014 1087
I 1327 1618
S 1293 2100
I 1500 1862
I 1413 1760
F 515 1220
S 400 1221
E 240 1789
S 1109 1227
S 1213 2071
I 179 2089
E 1862 1894
S 1233 1850
E 760 1303
I 604 1310
E 448 1888
I 240 633
I 1456 2030
S 489 1145
E 1169 1957
F 1210 1768
I 554 992
E 177 731
F 90 1001
F 199 1376
E 198 712
E 1409 1647
S 93 753
E 955 1306
I 814 1151
F 807 1887
F 1092 1425
I 46 109
S 263 851
S 847 1639
S 1512 1837
F 1436 2017
E 650 1593
S 436 1314
S 1075 1315
I 1090 2005
F 134 2097
E 181 1069
F 283 1096
F 499 1944
E 1042 1408
I 121 1313
S 737 2027
F 1229 2042
S 192 557
E 149 160
F 198 699
E 615 1332
E 640 1615
E 66 992
E 936 1108
I 606 1293
I 1776 2094
S 315 2024
F 470 1467
E 694 1886
F 1284 1457
F 24 816
S 593 728
I 1466 1721
I 124 609
F 189 1215
I 943 1632
S 878 1259
E 678 1417
S 37 517
E 919 1801
E 569 2063
I 251 1226
S 182 644
F 180 768
F 1022 1415
S 606 1831
I 117 1548
E 492 853
I 891 1465
S 1021 1874
F 1825 2034
I 28 1023
I 210 741
S 132 455
E 197 1870
S 1413 1653
S 1524 1770
F 215 847
S 912 1680
E 653 1494
I 639 1765
I 557 1663
E 356 575
F 553 1237
I 620 814
S 115 1089
E 116 1703
F 502 627
E 1414 2056
I 215 796
I 249 513
E 1070 2107
E 1645 1882
I 835 1931
F 323 1519
S 561 649
S 516 677
E 105 1369
F 1377 2022
F 1523 1592
I 1613 1841
F 295 1901
I 704 1671
E 1470 1554
F 740 1941
E 478 889
S 1058 1152
F 1071 1163
E 1137 1557
E 612 1345
S 114 1993
F 473 1043
S 1178 1228
E 600 946
I 1404 1499
F 181 1523
I 1398 2109
E 357 1260
S 1844 1978
S 1211 1693
E 1022 1157
S 152 209
E 1233 1444
E 278 1880
E 1841 1969
S 1317 1951
E 299 1314
I 526 1817
E 258 339
F 62 1951
E 397 925
I 847 1135
I 320 1898
E 153 2015
I 74 620
S 629 2026
E 213 884
S 425 2031
E 322 388
F 281 384
I 781 1385
E 1535 1692
E 1542 1901
I 1445 1599
E 1640 2065
S 647 1411
F 386 1595
S 740 2085
E 425 1619
E 645 706
S 1685 2091
S 1514 1539
I 480 1367
S 919 1918
E 447 1396
F 1013 1858
S 197 544
F 353 1001
E 144 572
S 258 1217
S 755 855
E 50 282
E 827 1038
F 697 1456
S 45 1271
I 1059 1104
S 1648 1667
F 1676 2084
F 117 1676
I 54 375
E 1185 1194
S 248 1245
I 171 890
S 787 1691
E 914 1603
F 754 2083
S 1619 1892
F 1115 1247
E 876 1403
F 216 930
I 67 246
S 316 1195
I 378 1206
E 389 2057
F 1160 1548
S 254 1977
I 35 1805
I 1214 1253
I 570 673
F 274 786
S 250 1096
S 179 1420
E 557 1724
I 150 1010
I 59 332
E 1428 2100
F 383 1858
I 999 1021
F 859 1736
I 1509 2074
I 212 1041
E 577 1632
S 556 1308
E 1523 1742
F 760 1855
E 1171 1327
S 100 1618
I 591 1084
I 1170 1451
F 912 1827
F 1221 1954
F 483 1776
E 461 1039
F 733 1816
S 22 1494
I 462 773
F 937 955
S 1194 2021
I 384 1079
S 858 1310
E 32 150
AC output:

Code: Select all

Case 1:
Q1: 246
Q2: 981
Q3: 737
Q4: 148
Q5: 728
Q6: 361
Q7: 0
Q8: 408
Q9: 234
Q10: 0
Q11: 169
Q12: 342
Q13: 1045
Q14: 1182
Q15: 53
Q16: 132
Q17: 128
Q18: 305
Q19: 0
Q20: 103
Q21: 9
Q22: 137
Q23: 640
Q24: 9
Q25: 304
Q26: 279
Q27: 113
Q28: 268
Q29: 1029
Q30: 23
Q31: 104
Q32: 371
Q33: 765
Q34: 0
Q35: 134
Q36: 557
Q37: 145
Q38: 146
Q39: 139
Q40: 793
Q41: 326
Q42: 0
Q43: 0
Q44: 891
Q45: 91
Q46: 848
Q47: 136
Q48: 109
Q49: 416
Q50: 138
Q51: 810
Q52: 478
Q53: 30
Q54: 0
Q55: 0
Q56: 0
Q57: 507
Q58: 89
Q59: 162
Q60: 95
Q61: 619
Q62: 0
Q63: 0
Q64: 171
Q65: 29
Q66: 0
Q67: 4
Q68: 9
Q69: 605
Q70: 880
Q71: 26
Q72: 0
Q73: 449
Q74: 159
Q75: 634
Q76: 101
Q77: 699
Q78: 20
Q79: 860
Q80: 791
Q81: 274
Q82: 615
Q83: 513
Q84: 823
Q85: 994
Q86: 0
Q87: 853
Q88: 945
Q89: 828
Q90: 231
Check input and AC output for thousands of problems on uDebug!

darkstallion
New poster
Posts: 3
Joined: Fri Jul 05, 2013 9:07 am

Re: 11402 - Ahoy, Pirates

Post by darkstallion » Thu Jul 11, 2013 8:57 am

woah! that's really a long test case! How did you make that test case?

However I managed to know the bug in my code and I got AC, thanks to your test case, brianfry713! :)

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11402 - Ahoy, Pirates

Post by brianfry713 » Thu Jul 11, 2013 10:53 pm

I wrote a test case generator using rand()
Check input and AC output for thousands of problems on uDebug!

tamim1382csedu19
New poster
Posts: 18
Joined: Mon Jun 03, 2013 5:09 pm

Re: 11402 - Ahoy, Pirates

Post by tamim1382csedu19 » Mon Aug 05, 2013 8:57 pm

Is it solvable using BIT? I am trying to solve it using fenwick tree. But its giving me TLE. Heres my code , http://ideone.com/krmc4n

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11402 - Ahoy, Pirates

Post by brianfry713 » Tue Aug 06, 2013 12:08 am

From uhunt:
AKJ88> tamimcsedu19, Use segment tree and count the number of Buccaneer pirates in each range.
Check input and AC output for thousands of problems on uDebug!

tamim1382csedu19
New poster
Posts: 18
Joined: Mon Jun 03, 2013 5:09 pm

Re: 11402 - Ahoy, Pirates

Post by tamim1382csedu19 » Tue Aug 06, 2013 1:45 pm

I have used lazy updates. Still getting TLE. :( Here's My code
http://ideone.com/EKNaRN

tamim1382csedu19
New poster
Posts: 18
Joined: Mon Jun 03, 2013 5:09 pm

Re: 11402 - Ahoy, Pirates

Post by tamim1382csedu19 » Tue Aug 06, 2013 7:48 pm

SomeOne please help.. I am Trying all day long but couldn't find a way to do >.... getting TLE after using segment tree with lazy updates too.. :( http://ideone.com/WDK1eu

vaush
New poster
Posts: 1
Joined: Thu Aug 08, 2013 2:07 am

Re: 11402 - Ahoy, Pirates

Post by vaush » Thu Aug 08, 2013 2:11 am

Both of your versions, and i think a lot of others', are coded with the same mistake: you don't get the newline character between the number of repetitions of the binary string and the string itself. After getting the number of repetitions, use a double getline(cin, str), where str is the variable in which you want to record the binary string: the first time you get rid of the newline and the awful lot of spaces in between, and with the second one you get the actual string

tamim1382csedu19
New poster
Posts: 18
Joined: Mon Jun 03, 2013 5:09 pm

Re: 11402 - Ahoy, Pirates

Post by tamim1382csedu19 » Thu Aug 15, 2013 10:51 am

But, I am getting TLE,, How I avoid that?

Blackwizard
New poster
Posts: 12
Joined: Fri May 25, 2012 5:36 pm

Re: 11402 - Ahoy, Pirates

Post by Blackwizard » Fri Sep 27, 2013 11:44 am

Hi...

I used segment tree with lazy propagation to update for this problem.
But I'm getting WA! :(
Is there any tricky case?!

Here's my code: http://ideone.com/4NNbV5

Thanks for your help...

vector9x
New poster
Posts: 3
Joined: Sun Jul 06, 2014 8:57 pm

Re: 11402 - Ahoy, Pirates

Post by vector9x » Wed Jul 09, 2014 8:07 am

Blackwizard wrote:Hi...

I used segment tree with lazy propagation to update for this problem.
But I'm getting WA! :(
Is there any tricky case?!

Here's my code: http://ideone.com/4NNbV5

Thanks for your help...
I think you need to interchange lines 45 and 46 as well as 60 and 61.
I mean, perform lazy_propagation after checking the interval, because lazy_propagation uses r and l

AmirAz
New poster
Posts: 8
Joined: Tue May 20, 2014 12:34 pm

Re: 11402 - Ahoy, Pirates

Post by AmirAz » Sat Jul 19, 2014 2:11 pm

I used segment tree, O(n log n) building, and maximum O(2 log n) = O(log n) for each query or update. here is my code and i get TLE can you tell me what should I change?

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <set>
#include <algorithm>
#include <ctype.h>
#include <map>
#include <vector>
#include <stack>
#include <climits>
#include <functional>
#include <sstream>
#include <math.h>

using namespace std;
#define lli long long int
#define llu long long unsigned
#define ii pair<int, int>
#define vii vector<ii>
#define vi vector<int>
#define log2(n) log10(n) / log10(2)
#define getMid(a, b) floor(a + b) /2;
#define mii map<int,int>

class SegmentTree{

public:
int tree_len, *tree; bool *source; int size;
int build(int p, int s, int e){
if (s == e)
return tree[p] = (source[s]?1:0);
int mid = getMid(s, e);
return tree[p] = build((p<<1), s, mid) + build((p<<1) + 1, mid + 1, e);
}
SegmentTree(bool *ex , int n){
size = n;
int h = ceil(log2(size));
source = new bool [n];
for (int i = 0; i < n; i++)
source = ex;
tree_len = 2 * pow(2, h);
tree = new int[tree_len+1];
build(1, 0, size-1);
}

void update(int p, int s, int e, int idx, int diff){
if (s > idx || e < idx)
return;

if (s == e){
tree[p] += diff;
source[idx] = tree[p];
return;
}
int mid = getMid(s, e);
tree[p] += diff;
update((p<<1), s, mid, idx, diff);
update((p<<1) + 1, mid+ 1, e, idx, diff);
}

int getSum(int p, int s, int e, int i, int j){
if (s > j || e < i)
return 0;
if ((s == e) || ( s >= i && e <= j))
return tree[p];
int mid = getMid(s, e);
return getSum((p<<1), s, mid, i, j) + getSum((p<<1)+1, mid + 1, e, i, j);
}



};

int main(){
bool *source = new bool[1024000];
int T; cin >> T;

for (int tc = 1; tc <= T; tc++){
int m; cin >> m;
int size = 0;
for (int i = 0; i < m; i++)
{
int time; cin >> time;
string orig; cin >> orig;
for (int j = 0; j < time; j++)
for (int k = 0; k < orig.size(); k++)
source[size++] = (orig[k]=='1'?true:false);


}
SegmentTree st(source, size);
cout << "Case " << tc << ":\n";
int q; cin >> q; int god = 0;
for (int i = 0; i < q; i++){
int s, e; char a;
cin >> a >> s >> e;
if (a == 'F'){
for (int pos = s; pos <= e; pos++)
st.update(1, 0, size -1, pos, (st.source[pos] ? 0 : 1));
}
else if (a == 'E'){
for (int pos = s; pos <= e; pos++)
st.update(1, 0, size -1, pos, (st.source[pos] ? -1 : 0));
}
else if (a == 'I'){
for (int pos = s; pos <= e; pos++)
st.update(1, 0, size -1, pos, (st.source[pos] ? -1 : 1));
}
else if (a == 'S'){
cout << "Q" << ++god << ": " << st.getSum(1, 0, size -1, s, e) << "\n";
}
}


}
delete [] source;
}

lbv
Experienced poster
Posts: 128
Joined: Tue Nov 29, 2011 8:40 am

Re: 11402 - Ahoy, Pirates

Post by lbv » Sat Jul 19, 2014 9:08 pm

AmirAz wrote:I used segment tree, O(n log n) building, and maximum O(2 log n) = O(log n) for each query or update. here is my code and i get TLE can you tell me what should I change?
Using a segment tree does little good if you still do loops proportional to the size of the underlying array for every operation:

Code: Select all

for (int pos = s; pos <= e; pos++)
	st.update( ... );
There are ways to handle every operation in this problem with just one segment tree traversal. Try googling and you'll find a number of editorials on the web that discuss this in detail.

P.S. When posting source code, please use the code tags. Thanks.

AmirAz
New poster
Posts: 8
Joined: Tue May 20, 2014 12:34 pm

Re: 11402 - Ahoy, Pirates

Post by AmirAz » Sun Jul 20, 2014 10:20 am

Can you tell me what should I exactly search? I read the tutorial on geeksforgeeks.org and topcode.com but I found nothing useful :(

lbv
Experienced poster
Posts: 128
Joined: Tue Nov 29, 2011 8:40 am

Re: 11402 - Ahoy, Pirates

Post by lbv » Sun Jul 20, 2014 10:50 am

AmirAz wrote:Can you tell me what should I exactly search? I read the tutorial on geeksforgeeks.org and topcode.com but I found nothing useful :(
I was referring to editorials about this specific problem, not about segment trees in general, but maybe I wasn't very clear, sorry.

Anyway, one such editorial that I know of is this one. You may find it helpful.

Post Reply

Return to “Volume 114 (11400-11499)”