question : https://www.codechef.com/LOGI2020/problems/AVGMED/

WA: https://www.codechef.com/viewsolution/38968939

@galencolin @ssrivastava990 @cubefreak777

Can anyone please help

question : https://www.codechef.com/LOGI2020/problems/AVGMED/

WA: https://www.codechef.com/viewsolution/38968939

@galencolin @ssrivastava990 @cubefreak777

Can anyone please help

Why should it even pass?, first off, your solution is O(nk) (looks like youâ€™re unaware of the fact that v.erase() is an O(n) operation in vectors). Secondly, your vector Sk might not always remain sorted thatâ€™s why median will not be the {(k-1)/2}^{th} element always.

2 Likes

ok. but I am using. ak vector to access the `(k-1)/2`

element to it should give an TLE and not an WA

Hey cube, i used the concept of minHeap and maxHeap used in â€ścalculate median of stream of integersâ€ť to calculate Median in a range , with the modification that minHeap and maxHeaps arenâ€™t actually Priority queues . They are taken as sets (one is ordered ascending, other is descending). I took sets because i can remove an element in logarithmic time , which is not possible in priority queues. Please have a look at my solution - https://ideone.com/gDi1po

No one is asking u bro.

10 3

16 11 14 6 1 1 6 16 10 12

10 2

6 19 10 3 17 20 12 8 5 8

10 4

6 18 2 13 19 6 13 5 12 7

10 4

10 19 16 12 18 13 5 20 13 18

There are a bunch of test cases where your solution fails, learn to stress test your solution.

thanks

why will this happen any intuation??

See for odd n it is clear that ans is not possible because n-2 is always odd and u cannot place 2*1 tiles to cover them.

For even n, I checked with pen on paper for any cell which cells could be removed and came up with this. The problem seemed more adhoc than provable to me, and so, no, I cannot prove my solution to u.

2 Likes

ok i got it thanks for the helpâ€¦ I saw some of the solution in dp â€¦ if u have any ideaâ€¦ how can we do it with dpâ€¦ just asking for curosity : - ) link of DP solution -

Sorry but Iâ€™m not sure about how to solve this problem by min or max heap, I solved this one with policy based data structures.

Hereâ€™s my AC code for anyone interested

```
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ar array
#define int long long
template<class T> using oset =tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update> ;
bool ok(int n){
for(int d=2;d*d<=n;d++)
if(n%d==0)
return 1 ;
return 0 ;
}
void solve(){
int n,k,ans=0;
cin >> n >> k ;
vector<int>a(n);
for(int &x:a)
cin >> x ;
oset<ar<int,2>>s ;
int S=0 ;
for(int i=0;i<k;i++)
s.insert({a[i],i}),S+=a[i] ;
auto md = [&](){
return (*s.find_by_order((k-1)/2))[0] ;
} ;
auto av = [&](){
return S/k;
};
if(av()>=md() && ok(av())==ok(md()))
++ans ;
for(int i=k;i<n;i++){
S-=a[i-k];S+=a[i] ;
s.erase({a[i-k],i-k}) ;
s.insert({a[i],i}) ;
ans+= (av()>=md() && ok(av())==ok(md())) ;
}
cout << ans << '\n' ;
}
signed main() {
int t ;
cin >> t ;
while(t--)
solve() ;
}
```

1 Like

I have already seen your submission . Among all the code that got accepted , only one of them didnt use pbds.

Start with thinking about multisource BFS.

With Multisource BFS, we can calculate the minimum distances of all the nodes other than given D nodes.

Now we just have to sort all the nodes first in increasing order of their distances and then in decreasing order of number of soldiers.

See My Solution

2 Likes

Thanks got it.

1 Like

If n is odd -> n * n is odd -> n * n - 2 is also odd -> which can never be covered by any amount of 2 * 1 tiles

If n is even ->

Consider the below figure for 4*4

0 1 0 1

1 0 1 0

0 1 0 1

1 0 1 0

Out of all possible pairs, one with same type (either 1 or 0) can never be valid.

So from the remaining oneâ€™s, just count the pairs with different type of colour.

See My Solution for implementation details

2 Likes