Encoding february 2020

Can anyone share approach for this CodeChef: Practical coding for everyone

I try to find
if(k<hosp[left] then return diff btw leftmost hospital and k
similary for right one

if(k is hospital) then return 0;
else
search fro left most greater element
and right most less element

but not got accepted

my submission
https://www.codechef.com/viewsolution/29863909

1 Like

Anyone can tell me why I got TLE for my submission?
here is my submission for the problem ECFEB202: CodeChef: Practical coding for everyone
CodeChef: Practical coding for everyone
Please describe it.

Please anyone can tell me why the ranklist of Encoding february 2020 froze?

I didn’t see your approach,but i did it through hash table,
On first attempt,i simply used 2 loops and calculated the minimum absolute diff,but got TLE.
On 2nd try,i used hash table
My sol : CodeChef: Practical coding for everyone

Actually You can find a pattern in that sequence. No need to store or iterate through any data structure.

Its now unfrozen…actually this contest was a part of the tech fest that has been happening in our college…so the freezing part was for the sake of the onsite participants.

Maybe I’m reading this wrong, but you can just precompute for each city for O(n+q)

If n is even the last number will be odd, other wise the last number will be even.
The parity of abs(x-y) = x+y mod 2

1 Like

can you alloborate your approach using hashtable and idea behind storing in hashtable?
your submission is not visible at my end.

can you expalin more?

I execute my code in my IDE, and it worked properly. But I got a TLE after submitting it. Why I got this error and how can I resolve it?

@shahil_005 I can’t see your submission too.

Your code is O(n) where n can be as large 10^9

take two numbers 5 and 3.
abs(5-3) is 2. 5+3 is 8, both are even.
This is trivial to prove.
Let’s assume y\leq x without loss of generality.
The difference between x-y and x+y is 2y. A multiple of 2 doesn’t change parity.

@everule1 ok. But how can I resolve the TLE error in my solution?
CodeChef: Practical coding for everyone

for t in range(int(input())):
 if(int(input())%4==0 or int(input())%4==3):
  print("CHEF")
 else:
  print("CHEFU")

:slightly_smiling_face:

1 Like

also by finding sum of n natural number we can get the logic

@ifrunruhin @grg124
//shahil_005
// Some basic pre-written functions might have been copied from www.geeksforgeeks.org or Main Page - Algorithms for Competitive Programming

#include <bits/stdc++.h>

using namespace std;

#define endl ‘\n’
#define sync ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)

const int N = 1e5 + 5;
const long long MOD=(long long)(1e9+7);
const long long INIT=(long long)(1e6+1);

int32_t main()
{
int n,q,h;
cin >> n >> q >> h;

int a[q],b[h];
int t[100000] = {0};
for(int i=0;i<h;i++)
{
    cin >> b[i];
    t[b[i]]++;
}

for(int i=0;i<q;i++)
{
    cin >> a[i];
}

for(int i=0;i<q;i++)
{
    int l=1;
    int j=a[i],k=a[i];
    int ans=0;
    while(l>0)
    {

        if(t[j] == 1 && j>0)
        {
            ans = abs(a[i] - j);
            l=0;
        }
        else if(t[k] == 1 && k>0)
        {
            ans = abs(a[i] - k);
            l=0;
        }
        j--;
        k++;
    }
    cout << ans << endl;
}

return 0;

}

1 Like