|
|
Show all threads Hide all threads Show all messages Hide all messages | I got accepted with a wrong program | georg | 2143. Victoria! | 10 Jun 2022 15:47 | 1 | Test: 99 10 ***|_|*** .*.|_|*** *.*|_|*** ***|_|*** .*.|_|*** *.*|_|*** and so on (block of 3 rows repeated 33 times). My program hangs out on this test (takes infinite time), but I got accepted. | WA10 | Михаил | 2143. Victoria! | 31 Jan 2022 09:50 | 4 | WA10 Михаил 3 Nov 2019 21:41 Tests? Edited by author 03.11.2019 21:42 Edited by author 03.11.2019 21:42 it costs my hours it was a silly mistake on my code. when i print("iA iC) or print("iD iF) i use k-- instead of k-=2; Test helped me: Input: 2 2 ***|_|.** **.|_|*** Output: POBEDA 2C 1D | WA5 | ✌.|•͡˘‿•͡˘|.✌ Alexandru Peticaru | 2143. Victoria! | 31 Jan 2022 09:42 | 3 | WA5 ✌.|•͡˘‿•͡˘|.✌ Alexandru Peticaru 5 Nov 2019 13:18 Can you give me a test, please? Re: WA5 👨💻Stepavly👨💻 [ITMO] 22 Nov 2019 04:08 2 2 .**|_|*** *.*|_|*** Ans: PORAZHENIE One more: Input: 1 5 ...|_|... Output: PORAZHENIE | Dynamic programming by profile? | sadovnik | 2143. Victoria! | 22 Mar 2021 13:27 | 3 | Is it dynamic programming on the profile? How to apply it? Yes, it is. Let dp[i][mask] be the maximal number of passengers we can sit on the first i rows such that none of them sit close to each other and the i'th row is occupied exactly as in the mask (0 <= mask <= 63, if the j'th bit in the mask is 1, then the seat (j + 1) is occupied, otherwise it is not). Now, to compute dp[i][mask] we need to iterate through all possible masks "prev" of the (i - 1)'st row. For each such valid mask prev ("valid" means that none of the passengers on the (i - 1)'st and i'th rows sit close to each other) we have to relax our answer by dp[i][mask] = max(dp[i][mask], dp[i - 1][prev] + (the number ones in the mask)). Additionally, we can maintain the previous mask pointer[i][mask] = prev for each dp[i][mask] which gives us the best answer. When done with computing dp, we have to run through all valid masks of the last row and check whether dp[n][mask] >= k. If there is no such mask, then the answer is impossible. Otherwise, remember this mask and easily restore the answer by using those pointers to "prev" masks. Edited by author 01.05.2020 17:30 Edited by author 01.05.2020 17:30 Simple recursion with set<string,int> memorisation also works May be tests are weak | Some test cases | Smilodon_am [Obninsk INPE] | 2143. Victoria! | 9 Nov 2019 01:18 | 1 | Below test cases helped me to check the program: 2 3 .**|_|**. **.|_|*** ans: [good test] POBEDA 1A 2C 1F 5 6 ...|_|*** ...|_|*** ...|_|*** ...|_|*** ...|_|*** ans: POBEDA 1A 1C 3A 3C 5A 5C 5 12 ...|_|... ...|_|... ...|_|... ...|_|... ...|_|... ans: POBEDA 1A 1C 3A 3C 5A 5C 1D 1F 3D 3F 5D 5F 6 6 *..|_|*** ...|_|*** ...|_|*** ...|_|*** *..|_|*** ..*|_|*** ans: POBEDA 1C 2A 3C 4A 5C 6A 6 6 *..|_|*** ..*|_|*** ...|_|*** ...|_|*** *..|_|*** ...|_|*** ans: POBEDA 1C 2A 3C 4A 5C 6A 6 6 *..|_|*** *.*|_|*** ...|_|*** ...|_|*** *..|_|*** ...|_|*** ans: PORAZHENIE |
|
|
|