u/Vitthasl

The problem is from last Div 2 contest.

Problem: https://codeforces.com/contest/2257/problem/D#

Solution: https://codeforces.com/contest/2257/submission/387559313

I am getting TLE on test case 8.

Basically finding factors = sqrt(n)

The query loop should be = q * log(factors(n))

Can someone check and tell me which line is causing TLE?

EDIT:
I found the issue. I was using 'int i' while checking for factors instead of 'long long i'.

As a result i*i was never able to reach n for the given constraint

Last night I was taking the Gujarat mail, when I reached Kalupur junction, there was a bench on the bridge.

I was a bit tired so I sat there. After some time a person came up to me and said that the bench was specifically for railway staff.

I just avoided any conflict and went to my platform and boarded the train which was luckily open before 20 min of departure.

The thing is there was no such sign or anything which said that the bench was staff only. It was in the middle of the bridge.

I did not verify the person if he was actually the railway staff or not.(He had an ID card on his belt but I did not check)

I was too tired to have any confrontation so I ignored it.

The most weird thing was, no one else was over there, even the guy was not sitting on the bench.

Even if what he said was true, I was not denying any staff from sitting on the bench. There was a lot of space for two other people to sit other than me.

So is there any such thing as a bench reserved for the railway staff?

Was that guy just playing with me?

I have no idea, it did not matter in the end as I said my train had already arrived and was open to board and it was better to sit inside the AC compartment rather than the platform, but this thing just stayed in my mind. That's all.

​

Problem: https://codeforces.com/contest/2230/problem/D

Code: https://codeforces.com/contest/2230/submission/375257323

The code is stuck in queue forces so I cant do anything about it.

Basic approach find the longest possible reaching valid subarray starting from every (1,1) [1 iin both arrays at the same time]and store it in the precalc vector.

Then traversing the entire array and calculating the maximum possible subarray from that index.

If array from 0->5 is valid then it be same for lesser indices. 0->4,0->3,0->2,0->1,0->0.

The third problem from today's contest.

Link -> https://codeforces.com/contest/2226/problem/C

I think that I got the logic right. What is the issue?

Explanation:
Use binary search on the maximum possible mex.
In the binary search, basically I am keeping a curr array with size == mid.
basically this is used to check if all numbers for this particular mex can be obtained or not.

Initially if the number is less than mid then I am updating the curr

Afterwards I am checking if the remaining numbers are obtainable by using the operation.

Code:

#include <bits/stdc++.h>

using namespace std;

#define ll long long

#define rep(i, a, b) for(ll i = a; i < b; ++i)

typedef pair<ll,ll> pll;

typedef vector<ll> vll;

const ll mod = 1e9+7;

bool f(ll mid,ll n,vll &v){

vll curr(mid,0);

multiset<ll> q;

for(auto &i:v){

if((i<mid) && (!curr[i])){

curr[i]++;

}

else {

if(i&1)q.insert(i/2+1);

else q.insert(i/2-1);

}

}

for(int i=mid-1;i>=0;i--){

if(!curr[i]){

if(*q.rbegin()<i)return false;

auto it = q.end();

it = prev(it);

q.erase(it);

}

}

return true;

}

void check() {

ll n;cin>>n;

vll v(n);for(auto &i:v)cin>>i;

sort(v.begin(),v.end());

ll low=0,high=n;

ll ans = 0;

while(low<=high){

ll mid = low + (high-low)/2;

if(f(mid,n,v)){

ans= mid;

low = mid+1;

}

else high= mid-1;

}

cout<<ans<<"\n";

}

int main() {

ios_base::sync_with_stdio(false);

cin.tie(nullptr);

ll t=1;

cin >> t;

while(t--) {

check();

}

return 0;

}