| ENG RUS | Timus Online Judge |
Common Boardlxn range tree [11] // Problem 1896. War Games 2.1 9 Jun 2016 16:15 Is there a solution without randge tree structure? Shen Yang Re: range tree [10] // Problem 1896. War Games 2.1 23 Aug 2016 17:26 I use Fenwick Tree get AC,0.452 seconds coder Re: range tree [3] // Problem 1896. War Games 2.1 17 Jan 2017 16:33 There possible segment tree with uint16_t for indexes greater than 2^15, and uin32_t for less 2^15. (two arrays: uint16_t tree[N+N]; and uint32_t rem[32768] ) But I got WA38 (( coder Re: range tree // Problem 1896. War Games 2.1 17 Jan 2017 20:57 I Got AC with segment tree!! uraaaaa. __Andrewy__ Re: range tree [1] // Problem 1896. War Games 2.1 27 Feb 2018 21:41 You can use segment tree where vertex is segment with length=4. 1 2 3 4 5 6 7 8 9 10 => [1,2,3,4] [5,6,7,8] [9,10,11,12] Memory is N*sizeof(int)+N*sizeof(bool) Complexity is N*log(N/4)*4+N*log(N/4) 🐒🍌[PermSU] Re: range tree // Problem 1896. War Games 2.1 22 Nov 2021 01:13 decomposition also works here, i've chosen amount of block about 300 Nikita Mogilevets Re: range tree [5] // Problem 1896. War Games 2.1 9 Jul 2017 21:42 I can't do that. C/C++. I am using two cycles. One to set up Fenwick tree and one to calculate the answer. Probably you are avoiding the use of the set up cycle somewhat. I tested my solution on war games 2 and have got 93 ms. UPD: got 46 ms on version 1 Edited by author 09.07.2017 22:20 Nikita Mogilevets Re: range tree [4] // Problem 1896. War Games 2.1 9 Jul 2017 22:39 Finally, I understood how to get rid of initialization cycle. Still TLE the same test 37. Nikita Mogilevets Re: range tree [3] // Problem 1896. War Games 2.1 9 Jul 2017 22:47 http://ideone.com/cUMY7U I have no idea what can be optimized. Nikita Mogilevets Re: range tree [2] // Problem 1896. War Games 2.1 9 Jul 2017 22:57 Maybe bitwise operations are faster with UNSIGNED integers... Nikita Mogilevets Re: range tree [1] // Problem 1896. War Games 2.1 10 Jul 2017 13:24 So, I tried to not calculate cnt=n-i+1 every iteration, made while (1) cycle, not call decrement on Fenwick tree after last soldier. TLE#37. Nikita Mogilevets Re: range tree // Problem 1896. War Games 2.1 6 Aug 2017 15:09 My mistake was I was using queries for O(log(N) *log(N)) time in Fenwick tree But for that task, there are suitable queries in just O(log(N)) hakka_no_togame dp - O(m^2) // Problem 1303. Minimal Coverage 21 Nov 2021 19:10 dp[i] - минимальное количество отрезков, если последний отрезок заканчивался в позиции i. ответ dp[m]. Ealham Some Test Cases ... [3] // Problem 1106. Two Teams 20 Jun 2016 22:16 I've been struggling hard to overcome WA 8... Then I've made these test cases and got AC in one go. I hope these tests will be helpful to overcome WA... :) Case 1: 4 3 0 4 0 1 0 2 0 Ans: 2 1 2 Case 2: 2 2 0 1 0 Ans: 1 1 Case 3: 3 2 3 0 1 3 0 1 2 0 Ans: 1 1 Case 4: 3 2 0 1 3 0 2 0 Ans: 2 1 3 Case 5: 4 2 4 0 1 0 4 0 1 3 0 Ans: 2 1 3 Case 6: 5 5 0 5 0 5 0 5 0 1 2 3 4 0 Ans: 4 1 2 3 4 Case 7: 5 2 0 1 0 5 0 5 0 3 4 0 Ans: 3 1 3 4 Let me know if any1 finds any error... Thanks. Edited by author 20.06.2016 22:19 kitxuli Re: Some Test Cases ... [2] // Problem 1106. Two Teams 21 Sep 2016 17:32 My program passed all this tests but still I have WA7 Desserg Re: Some Test Cases ... [1] // Problem 1106. Two Teams 27 Nov 2019 12:56 the same situation Лев Re: Some Test Cases ... // Problem 1106. Two Teams 21 Nov 2021 18:34 same, but even WA 1 Maxim Afripov HINT If you get WA22 // Problem 2033. Devices 21 Nov 2021 01:44 If you get WA22, problem in saving minimal price of devices. If there are several popular devices, you need to display the one with the cheapest price Try test: a htc 10000 b nexus 10000 c htc 99999 d nexus 10000 e htc 5000 f nexus 10000 answer is htc (the most minimal price is 5000) andreyDagger`~ Don't need DP, just greedy algo // Problem 1427. SMS 19 Nov 2021 13:31 qualdum solution // Problem 1635. Mnemonics and Palindromes 19 Nov 2021 02:17 might it is very complicated but i use hash and dp to solve this problem Yrii Please give me a test with"No Solution" [5] // Problem 1042. Central Heating 15 Feb 2002 03:21 Ivan Georgiev Re: [1] // Problem 1042. Central Heating 15 Feb 2002 23:17 There is always a solution and it is always only one -- you have n linear independent vectors (that is the determinant of the linear system is <> 0) and using Cramer's rule you have a single solution. Vinicius Fortuna Re: // Problem 1042. Central Heating 7 Mar 2002 00:54 But they are modular equations. Is Cramer's rule still valid for such equations? > There is always a solution and it is always only one -- > > you have n linear independent vectors (that is the determinant of the > linear system is <> 0) and using Cramer's rule you have a single > solution. Yrii Re: Please give me a test with"No Solution" [1] // Problem 1042. Central Heating 16 Feb 2002 01:26 Ok I understand that but i decided that there are bugs in my proof so ... cyc Re: Please give me a test with"No Solution" // Problem 1042. Central Heating 17 Jul 2010 19:16 3 1 2 -1 2 3 -1 2 3 -1 Edited by author 17.07.2010 19:16 Edited by author 17.07.2010 19:16 elManco Re: Please give me a test with"No Solution" // Problem 1042. Central Heating 18 Nov 2021 20:39 3 1 -1 1 2 -1 2 -1 andreyDagger`~ This is not mentioned in statement // Problem 1078. Segments 17 Nov 2021 23:48 Segments can be with zero length andreyDagger`~ Small hint // Problem 1141. RSA Attack 17 Nov 2021 13:58 (p-1)(q-1) is euler function value of n. Smilodon_am [Obninsk INPE] Some test cases [2] // Problem 2113. Survive the flood 29 Oct 2019 02:12 See some test cases below. I hope some of them will help you. 2 5 2 3 9 2 100 1 2 5 4 100 2 1 1 5 ans: 0 5 1 100000 0 1 100000 1 4 1 5 1 ans: 0 5 1 100000 0 1 100000 1 3 1 5 1 ans: 0 5 1 100000 0 1 1 1 4 1 5 1 ans: 100000 5 1 100000 1 1 1 1 4 1 5 1 ans: 99999 3 4 1 2 2 1 1 2 2 1 1 2 2 1 2 1 3 4 ans: 0 Pravă Felix-Mihai Re: Some test cases // Problem 2113. Survive the flood 8 Apr 2021 21:39 For WA16 these cases helped me: 4 6 1 1 1 2 2 2 2 2 2 3 3 3 4 4 4 4 4 4 4 5 5 5 5 4 2 2 3 1 ans: -1 4 6 1 1 1 2 2 2 2 2 2 3 3 3 4 4 4 4 4 4 4 5 5 5 5 4 2 3 3 1 ans: 1 andreyDagger`~ Re: Some test cases // Problem 2113. Survive the flood 16 Nov 2021 18:14 Thank you! andreyDagger`~ WA 4 // Problem 1651. Shortest Subchain 16 Nov 2021 10:29 5 1 2 1 3 2 ans: 1 2 Vadim Nikulin You don't need to read the array into memory ;) // Problem 2141. Sasha Vilkin 13 Nov 2021 12:49 It's strange that it has a tag "DP" as well. andreyDagger`~ Small clarification // Problem 1121. Branches 13 Nov 2021 12:28 You don't need to sum the branches, you need to do binary OR "|" on them. andreyDagger`~ How to not write many "if-elif-...." // Problem 1302. Delta-wave 13 Nov 2021 10:42 On every step you move one level down. You have three choices to go down-left, down-right and just down (it's not always possible). So, you check which side m is on. If on the right, then we go down-right, otherwise - down-lef, if it's right below us, then we just go down irinaguseva Some tips // Problem 1073. Square Country 13 Nov 2021 00:26 The most important idea for this task is the fact that according to Lagrange’s Four Square Theorem, every natural number can be written as the sum of squares of four non-negative integers. Good luck, hope this will help! Edited by author 13.11.2021 00:26 Edited by author 13.11.2021 00:26 andreyDagger`~ Another approach // Problem 1218. Episode N-th: The Jedi Tournament 11 Nov 2021 22:35 I see many people solved this with graph algorithms, there is also greedy approach. Let's build graph: u->v, if jedi u is winning v. You are doing n iterations, on every iteration you check, can current Jedi win, or not. There is greedy strategy to check this. You can eliminating enemies in order of the number of incoming edges. The fewer edges lead to a Jedi, the earlier we should eliminate him Edited by author 11.11.2021 22:35 Edited by author 11.11.2021 22:35 Edited by author 11.11.2021 22:36 itskiller 2 details not mentioned [1] // Problem 1038. Spell Checker 11 Nov 2021 17:55 there are 2 details which are not mentioned in the document. 1. number(0-9) is also the splitor of word, so word can only contained characters,a-z. such as A0B is 2 words. 2. Next line starts one new word, but not always starts one new sentence, such as this is one sentence, but is splited to 2 lines. HelloWorld Re: 2 details not mentioned // Problem 1038. Spell Checker 11 Nov 2021 17:58 666,it's correct 6yxa/\bl Why wrong Answer on TEst NumbEr 3??????? hel me please! [1] // Problem 1038. Spell Checker 17 Mar 2007 14:10 Help me!!! fanzhengguang Re: Why wrong Answer on TEst NumbEr 3??????? hel me please! // Problem 1038. Spell Checker 11 Nov 2021 17:48 gun tqti for WA#3 and WA#10 [4] // Problem 1038. Spell Checker 20 Feb 2014 23:22 WA#3: new word start after '\n';(e.g. Abc'\n'new_word_here) WA#10 new word start after number; (e.g. 909090new_word_here) Myrcella Re: for WA#3 and WA#10 [3] // Problem 1038. Spell Checker 9 Sep 2018 19:39 Thank you very much! It helps me a lot! I WA#3 because of this :D feifei Re: for WA#3 and WA#10 [1] // Problem 1038. Spell Checker 9 Nov 2021 18:22 Thank you very much! It helps me a lot! I WA#3 because of this :D HelloWorld Re: for WA#3 and WA#10 // Problem 1038. Spell Checker 10 Nov 2021 06:23 666 feifei Re: for WA#3 and WA#10 // Problem 1038. Spell Checker 9 Nov 2021 18:22 Thank you very much! It helps me a lot! I WA#3 because of this :D andreyDagger`~ AC in 5 rows // Problem 1053. Pinocchio 8 Nov 2021 21:00 5 rows of code to solve this
|