| ENG RUS | Timus Online Judge |
Общий форумlxn range tree [11] // Задача 1896. Военные учения 2.1 9 июн 2016 16:15 Is there a solution without randge tree structure? Shen Yang Re: range tree [10] // Задача 1896. Военные учения 2.1 23 авг 2016 17:26 I use Fenwick Tree get AC,0.452 seconds xurshid_n Re: range tree [3] // Задача 1896. Военные учения 2.1 17 янв 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 (( xurshid_n Re: range tree // Задача 1896. Военные учения 2.1 17 янв 2017 20:57 I Got AC with segment tree!! uraaaaa. Felix_Mate Re: range tree [1] // Задача 1896. Военные учения 2.1 27 фев 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) 🙂 Nayami_[PermSU] Re: range tree // Задача 1896. Военные учения 2.1 22 ноя 2021 01:13 decomposition also works here, i've chosen amount of block about 300 Mahilewets Re: range tree [5] // Задача 1896. Военные учения 2.1 9 июл 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 Mahilewets Re: range tree [4] // Задача 1896. Военные учения 2.1 9 июл 2017 22:39 Finally, I understood how to get rid of initialization cycle. Still TLE the same test 37. Mahilewets Re: range tree [3] // Задача 1896. Военные учения 2.1 9 июл 2017 22:47 http://ideone.com/cUMY7U I have no idea what can be optimized. Mahilewets Re: range tree [2] // Задача 1896. Военные учения 2.1 9 июл 2017 22:57 Maybe bitwise operations are faster with UNSIGNED integers... Mahilewets Re: range tree [1] // Задача 1896. Военные учения 2.1 10 июл 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. Mahilewets Re: range tree // Задача 1896. Военные учения 2.1 6 авг 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)) >>> dp - O(m^2) // Задача 1303. Минимальное покрытие 21 ноя 2021 19:10 dp[i] - минимальное количество отрезков, если последний отрезок заканчивался в позиции i. ответ dp[m]. Mewtwo Some Test Cases ... [3] // Задача 1106. Две команды 20 июн 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] // Задача 1106. Две команды 21 сен 2016 17:32 My program passed all this tests but still I have WA7 Desserg Re: Some Test Cases ... [1] // Задача 1106. Две команды 27 ноя 2019 12:56 the same situation Лев Re: Some Test Cases ... // Задача 1106. Две команды 21 ноя 2021 18:34 same, but even WA 1 Maxim Afripov HINT If you get WA22 // Задача 2033. Девайсы 21 ноя 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 // Задача 1427. SMS 19 ноя 2021 13:31 Anton solution // Задача 1635. Мнемоника и палиндромы 19 ноя 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] // Задача 1042. Центральное отопление 15 фев 2002 03:21 Ivan Georgiev Re: [1] // Задача 1042. Центральное отопление 15 фев 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: // Задача 1042. Центральное отопление 7 мар 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] // Задача 1042. Центральное отопление 16 фев 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" // Задача 1042. Центральное отопление 17 июл 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" // Задача 1042. Центральное отопление 18 ноя 2021 20:39 3 1 -1 1 2 -1 2 -1 andreyDagger This is not mentioned in statement // Задача 1078. Отрезки 17 ноя 2021 23:48 Segments can be with zero length andreyDagger Small hint // Задача 1141. Взлом RSA 17 ноя 2021 13:58 (p-1)(q-1) is euler function value of n. Smilodon_am [Obninsk INPE] Some test cases [2] // Задача 2113. Пережить потоп 29 окт 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 // Задача 2113. Пережить потоп 8 апр 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 // Задача 2113. Пережить потоп 16 ноя 2021 18:14 Thank you! andreyDagger WA 4 // Задача 1651. Кратчайшая подцепь 16 ноя 2021 10:29 5 1 2 1 3 2 ans: 1 2 vnikulin You don't need to read the array into memory ;) // Задача 2141. Саша Вилкин 13 ноя 2021 12:49 It's strange that it has a tag "DP" as well. andreyDagger Small clarification // Задача 1121. Филиалы 13 ноя 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-...." // Задача 1302. Дельта-волна 13 ноя 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 // Задача 1073. Квадратная страна 13 ноя 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 // Задача 1218. Episode N-th: The Jedi Tournament 11 ноя 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] // Задача 1038. Проверка орфографии 11 ноя 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 // Задача 1038. Проверка орфографии 11 ноя 2021 17:58 666,it's correct 6yxa/\bl Why wrong Answer on TEst NumbEr 3??????? hel me please! [1] // Задача 1038. Проверка орфографии 17 мар 2007 14:10 Help me!!! fanzhengguang Re: Why wrong Answer on TEst NumbEr 3??????? hel me please! // Задача 1038. Проверка орфографии 11 ноя 2021 17:48 gun tqti for WA#3 and WA#10 [4] // Задача 1038. Проверка орфографии 20 фев 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] // Задача 1038. Проверка орфографии 9 сен 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] // Задача 1038. Проверка орфографии 9 ноя 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 // Задача 1038. Проверка орфографии 10 ноя 2021 06:23 666 feifei Re: for WA#3 and WA#10 // Задача 1038. Проверка орфографии 9 ноя 2021 18:22 Thank you very much! It helps me a lot! I WA#3 because of this :D andreyDagger AC in 5 rows // Задача 1053. Пиноккио 8 ноя 2021 21:00 5 rows of code to solve this
|