LogiCode Average Median Game WA!

help
1

question : CodeChef: Practical coding for everyone

WA: CodeChef: Practical coding for everyone
@galencolin @ssrivastava990 @cubefreak777
Can anyone please help

2

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
3

second last problem - how to approch this problem

4

ok. but I am using. ak vector to access the (k-1)/2 element to it should give an TLE and not an WA

5

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 - gDi1po - Online C++ Compiler & Debugging Tool - Ideone.com

7
8

No one is asking u bro.

9

we can select pairs if their index sums(i+j) are at odd diff from each other
check here

1 Like
10

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.

11

thanks

13

why will this happen any intuation??

14

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
15

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 -

16

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

AC_CODE 
#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
17

How to approach this problem

18

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

19

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
20

Thanks :+1: got it.

1 Like
21

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