Forethought Future Cup - Final Round (Onsite Finalists Only)

Solutions are presented as using the least memory and the fastest execution time. It also takes the top 10 most recent solutions from each language. If you want to limit to a specific index, click the "Solved" button and go to that problem.

ContestId
Name
Phase
Frozen
Duration (Seconds)
Relative Time
Start Time
1147 Forethought Future Cup - Final Round (Onsite Finalists Only) FINISHED False 7200 174833699 May 4, 2019, 5:05 p.m.

Problems

Solved$
Index
Name
Type
Tags
Community Tag
Rating
( 5262 ) A Hide and Seek PROGRAMMING graphs 1500

B'Alice and Bob are playing a game on a line with n cells. There are n cells labeled from 1 through n . For each i from 1 to n-1 , cells i and i+1 are adjacent. Alice initially has a token on some cell on the line, and Bob tries to guess where it is. Bob guesses a sequence of line cell numbers x_1, x_2, ldots, x_k in order. In the i -th question, Bob asks Alice if her token is currently on cell x_i . That is, Alice can answer either "YES" or "NO" to each Bob 's question. At most one time in this process, before or after answering a question, Alice is allowed to move her token from her current cell to some adjacent cell. Alice acted in such a way that she was able to answer "NO" to all of Bob 's questions. Note that Alice can even move her token before answering the first question or after answering the last question. Alice can also choose to not move at all. You are given n and Bob 's questions x_1, ldots, x_k . You would like to count the number of scenarios that let Alice answer "NO" to all of Bob 's questions. Let (a,b) denote a scenario where Alice starts at cell a and ends at cell b . Two scenarios (a_i, b_i) and (a_j, b_j) are different if a_i neq a_j or b_i neq b_j . The first line contains two integers n and k ( 1 <= q n,k <= q 10^5 ) -- the number of cells and the number of questions Bob asked. The second line contains k integers x_1, x_2, ldots, x_k ( 1 <= q x_i <= q n ) -- Bob 's questions. Print a single integer, the number of scenarios that let Alice answer "NO" to all of Bob 's questions. The notation (i,j) denotes a scenario where Alice starts at cell i and ends at cell j . In the first example, the valid scenarios are (1, 2), (2, 1), (2, 2), (2, 3), (3, 2), (3, 3), (3, 4), (4, 3), (4, 5) . For example, (3,4) is valid since Alice can start at cell 3 , stay t'...

Tutorials

Forethought Future Cup Final Round Tutorial

Submissions

Submission Id
Author(s)
Index
Submitted
Verdict
Language
Test Set
Tests Passed
Time taken (ms)
Memory Consumed (bytes)
Tags
Rating
56538736 jiang5ye A July 5, 2019, 3:17 a.m. OK FPC TESTS 16 31 716800 1500
56538748 jiang5ye A July 5, 2019, 3:18 a.m. OK FPC TESTS 16 46 716800 1500
53844266 zhenGG A May 7, 2019, 9:42 a.m. OK GNU C++11 TESTS 16 30 1228800 1500
63710751 nicky_ua A Oct. 29, 2019, 9:57 a.m. OK GNU C++11 TESTS 16 31 102400 1500
55513618 luogu_bot4 A June 13, 2019, 2:57 a.m. OK GNU C++11 TESTS 16 31 307200 1500
53979662 JCHF A May 11, 2019, 6:28 a.m. OK GNU C++11 TESTS 16 31 614400 1500
53977307 lhy0930 A May 11, 2019, 5:07 a.m. OK GNU C++11 TESTS 16 31 614400 1500
53979108 ffffxk A May 11, 2019, 6:09 a.m. OK GNU C++11 TESTS 16 31 819200 1500
53806348 Rubbish12345 A May 6, 2019, 1:19 a.m. OK GNU C++11 TESTS 16 31 819200 1500
53836661 x_faraway_x A May 7, 2019, 3:41 a.m. OK GNU C++11 TESTS 16 31 921600 1500
64738690 1124828077 A Nov. 12, 2019, 11:15 a.m. OK GNU C++11 TESTS 16 31 1024000 1500
57288267 Handsome2004 A July 18, 2019, 3:30 p.m. OK GNU C++11 TESTS 16 31 1024000 1500
53831767 L_lawliet A May 6, 2019, 8:41 p.m. OK GNU C++14 TESTS 16 31 819200 1500
53799402 ftiasch A May 5, 2019, 5:30 p.m. OK GNU C++14 TESTS 16 31 819200 1500
53748114 Fdg A May 4, 2019, 5:14 p.m. OK GNU C++14 TESTS 16 31 819200 1500
53977207 tsingcbx A May 11, 2019, 5:03 a.m. OK GNU C++14 TESTS 16 31 1228800 1500
53864039 poojanpatel101 A May 8, 2019, 1:20 a.m. OK GNU C++14 TESTS 16 31 1228800 1500
53748080 Svlad_Cjelli A May 4, 2019, 5:14 p.m. OK GNU C++14 TESTS 16 31 1228800 1500
53748040 xiaowuc1 A May 4, 2019, 5:14 p.m. OK GNU C++14 TESTS 16 31 1228800 1500
65765280 Undercover_F_Brother A Nov. 26, 2019, 5:38 p.m. OK GNU C++14 TESTS 16 46 819200 1500
64740500 suzhen A Nov. 12, 2019, 11:50 a.m. OK GNU C++14 TESTS 16 46 819200 1500
64737370 xjq A Nov. 12, 2019, 10:49 a.m. OK GNU C++14 TESTS 16 46 819200 1500
55610354 ReaLNero1 A June 16, 2019, 5:17 a.m. OK GNU C++17 TESTS 16 15 819200 1500
53850626 .tx A May 7, 2019, 1:17 p.m. OK GNU C++17 TESTS 16 30 819200 1500
54243700 jdh A May 16, 2019, 1:59 p.m. OK GNU C++17 TESTS 16 30 2457600 1500
56536798 jiang5ye A July 5, 2019, 1:41 a.m. OK GNU C++17 TESTS 16 31 716800 1500
59594029 daikimatsu A Aug. 27, 2019, 11:25 p.m. OK GNU C++17 TESTS 16 31 819200 1500
57378386 krea7or A July 20, 2019, 1:31 p.m. OK GNU C++17 TESTS 16 31 819200 1500
54790314 dixitgarg A May 29, 2019, 6:46 a.m. OK GNU C++17 TESTS 16 31 819200 1500
64737357 boen_boen A Nov. 12, 2019, 10:49 a.m. OK GNU C++17 TESTS 16 31 1228800 1500
54421853 vjudge4 A May 20, 2019, 3:56 p.m. OK GNU C++17 TESTS 16 31 1638400 1500
53835808 yswness A May 7, 2019, 2:40 a.m. OK GNU C++17 TESTS 16 31 2048000 1500
65492262 shubh_jha98 A Nov. 21, 2019, 3:09 p.m. OK Java 11 TESTS 16 405 1228800 1500
58068055 hasan5788 A July 31, 2019, 9:35 a.m. OK Java 8 TESTS 16 109 0 1500
56003173 eztso A June 24, 2019, 2:04 p.m. OK Java 8 TESTS 16 109 1228800 1500
56728308 vjudge5 A July 8, 2019, 9:45 p.m. OK Java 8 TESTS 16 124 0 1500
53810128 jebaited A May 6, 2019, 5:56 a.m. OK Java 8 TESTS 16 124 0 1500
53798023 catforce A May 5, 2019, 4:25 p.m. OK Java 8 TESTS 16 124 0 1500
53759495 gojira A May 4, 2019, 6:46 p.m. OK Java 8 TESTS 16 124 0 1500
53747555 Suzukaze A May 4, 2019, 5:11 p.m. OK Java 8 TESTS 16 124 0 1500
56003204 eztso A June 24, 2019, 2:05 p.m. OK Java 8 TESTS 16 155 1228800 1500
53747623 liymbear A May 4, 2019, 5:12 p.m. OK Java 8 TESTS 16 155 1740800 1500
54888086 Nutella3000 A May 31, 2019, 6:34 p.m. OK Java 8 TESTS 16 155 8908800 1500
59978736 Spheniscine A Sept. 4, 2019, 7:16 a.m. OK Kotlin TESTS 16 171 0 1500
54858403 abarragan A May 30, 2019, 9:54 p.m. OK Kotlin TESTS 16 234 9830400 1500
54858410 vjudge4 A May 30, 2019, 9:54 p.m. OK Kotlin TESTS 16 249 9830400 1500
56619256 og.kostya A July 6, 2019, 11:17 a.m. OK Mono C# TESTS 16 46 1126400 1500
53830064 abhishek_1 A May 6, 2019, 7:14 p.m. OK MS C++ TESTS 16 78 1228800 1500
54664929 vjudge5 A May 26, 2019, 12:47 p.m. OK MS C++ TESTS 16 109 9830400 1500
55038956 Dragostan A June 3, 2019, 3:01 p.m. OK MS C++ 2017 TESTS 16 93 1638400 1500
53813056 osamasabri A May 6, 2019, 8:20 a.m. OK MS C++ 2017 TESTS 16 93 11980800 1500
57014962 anshuman16423 A July 14, 2019, 11:11 a.m. OK PyPy 2 TESTS 16 171 7987200 1500
56240747 Prateek A June 28, 2019, 6:19 p.m. OK PyPy 3 TESTS 16 233 10752000 1500
54981961 shubhankarsharma00 A June 2, 2019, 1:37 p.m. OK Python 2 TESTS 16 529 18227200 1500
53843517 Yazan_Eagle2 A May 7, 2019, 9:09 a.m. OK Python 3 TESTS 16 218 7680000 1500
53787723 gaidash A May 5, 2019, 11:05 a.m. OK Python 3 TESTS 16 249 18432000 1500
53792412 Niteshx2 A May 5, 2019, 1:35 p.m. OK Python 3 TESTS 16 264 6758400 1500
67609179 MinecraftFuns A Dec. 25, 2019, 2:42 p.m. OK Python 3 TESTS 16 265 7680000 1500
53878288 vvvb A May 8, 2019, 1:13 p.m. OK Python 3 TESTS 16 295 8499200 1500
57777189 PhmHngThai A July 26, 2019, 4:13 a.m. OK Python 3 TESTS 16 358 7987200 1500
54063671 UR5ANO A May 13, 2019, 12:23 p.m. OK Python 3 TESTS 16 468 14540800 1500
53859538 romanysik A May 7, 2019, 6:43 p.m. OK Python 3 TESTS 16 498 14540800 1500
53956605 petushny A May 10, 2019, 12:09 p.m. OK Python 3 TESTS 16 514 14848000 1500
56540263 cxh007 A July 5, 2019, 4:38 a.m. OK Python 3 TESTS 16 732 18841600 1500

remove filters

Back to search problems