| Show all threads Hide all threads Show all messages Hide all messages |
| wa9 | Лев | 1795. Husband in a Shop | 25 Nov 2021 23:39 | 1 |
wa9 Лев 25 Nov 2021 23:39 the store had the product, but sold it = the store did not have the product
if (!Products.count(name) || !Products[name]) Purchases.erase(Purchases.begin() + i); |
| If you get WA9 | Mescheryakov_Kirill [SESC17] | 1795. Husband in a Shop | 25 Nov 2021 23:18 | 2 |
Test:
1
10 of gg
3
1 of ff
10 of gg
9 of gg
Correct Answer: 3
Edited by author 25.11.2021 23:40 |
| How to avoid overflow | andreyDagger | 1513. Lemon Tale | 24 Nov 2021 12:58 | 1 |
|
| Another easy approach | andreyDagger | 1229. Strong Brickwork | 24 Nov 2021 10:53 | 1 |
You can always fill 2 * m area |
| Why WA1? | Peshkov [57 lyceum tlt] | 1229. Strong Brickwork | 24 Nov 2021 10:50 | 2 |
Why WA1? Peshkov [57 lyceum tlt] 13 Jul 2020 12:15 My program got WA1 with answer
1 2 3 4
1 2 3 4
on example test
Why? |
| lol tle 42 | >>> | 1915. Titan Ruins: Reconstruction of Bygones | 24 Nov 2021 07:59 | 1 |
tle 42 -ios_base::sync_with_stdio(0);
but ios_base::sync_with_stdio(false); cin.tie(NULL); - ACCEPTED with 0.015) |
| range tree | lxn | 1896. War Games 2.1 | 22 Nov 2021 01:13 | 12 |
Is there a solution without randge tree structure? I use Fenwick Tree get AC,0.452 seconds 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 (( I Got AC with segment tree!! uraaaaa. 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) decomposition also works here, i've chosen amount of block about 300 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 Finally, I understood how to get rid of initialization cycle. Still TLE the same test 37. Maybe bitwise operations are faster with UNSIGNED integers... 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. 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. Minimal Coverage | 21 Nov 2021 19:10 | 1 |
dp[i] - минимальное количество отрезков, если последний отрезок заканчивался в позиции i. ответ dp[m]. |
| Some Test Cases ... | Mewtwo | 1106. Two Teams | 21 Nov 2021 18:34 | 4 |
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 My program passed all this tests but still I have WA7 |
| HINT If you get WA22 | Maxim Afripov | 2033. Devices | 21 Nov 2021 01:44 | 1 |
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) |
| Don't need DP, just greedy algo | andreyDagger | 1427. SMS | 19 Nov 2021 13:31 | 1 |
|
| solution | Anton | 1635. Mnemonics and Palindromes | 19 Nov 2021 02:17 | 1 |
might it is very complicated but i use hash and dp to solve this problem |
| Please give me a test with"No Solution" | Yrii | 1042. Central Heating | 18 Nov 2021 20:39 | 6 |
Re: Ivan Georgiev 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.
Re: Vinicius Fortuna 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. Ok
I understand that but i decided that there are bugs in my proof
so ... 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 |
| This is not mentioned in statement | andreyDagger | 1078. Segments | 17 Nov 2021 23:48 | 1 |
Segments can be with zero length |
| Small hint | andreyDagger | 1141. RSA Attack | 17 Nov 2021 13:58 | 1 |
(p-1)(q-1) is euler function value of n. |
| Some test cases | Smilodon_am [Obninsk INPE] | 2113. Survive the flood | 16 Nov 2021 18:14 | 3 |
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 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 |
| WA 4 | andreyDagger | 1651. Shortest Subchain | 16 Nov 2021 10:29 | 1 |
WA 4 andreyDagger 16 Nov 2021 10:29 |
| You don't need to read the array into memory ;) | vnikulin | 2141. Sasha Vilkin | 13 Nov 2021 12:49 | 1 |
It's strange that it has a tag "DP" as well. |
| Small clarification | andreyDagger | 1121. Branches | 13 Nov 2021 12:28 | 1 |
You don't need to sum the branches, you need to do binary OR "|" on them. |
| How to not write many "if-elif-...." | andreyDagger | 1302. Delta-wave | 13 Nov 2021 10:42 | 1 |
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 |
