In div-2 F / div-1 D

Can someone please tell me why java version gives TLE whereas c++ is getting accepted. (i am new to java)

Java version

C++ version

How to solve div-2 E ?

Problem F is a thing of beauty.

Can someone please help me figure out why this solution for D is resulting in a TLE. Thanks a lot in advance.

#include <iostream>
#include <vector>
#include <unordered_map>
#include <map>
#include <set>
#include <string>
#include <cstdio>
#include <algorithm>
#include <numeric>
#include <stack>
#include <cmath>
#define ll long long int
#define ull unsigned long long int

#define mod 1000000007
using namespace std;

set<ll> st;
multiset<ll> mst;
int n, q;
ll arr[100200];

void getAns() {
    if(n>=2) {
        ll ans = (*(--st.end())) - (*st.begin());
        multiset<ll> ::iterator it = mst.end();
        it--;
        cout << ans - (*it) << "\n";
    }
    else
    {
        cout << "0\n";
    }
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    st.clear();
    mst.clear();
    cin >> n >> q;
    for (int i = 0; i < n;i++) 
        cin >> arr[i];
    sort(arr, arr+n);
    for (int i = 0; i < n; i++)
        st.insert(arr[i]);
    for (int i = 1; i < n; i++)
        mst.insert(arr[i] - arr[i - 1]);
    getAns();
    for (int i = 0; i < q;i++) {
        int a, b;
        cin >> a >> b;
        if(a==1) {
            n++;
            if(n==1) {
                st.insert(b);
            } else if(n==2) {
                set<ll>::iterator it = st.begin();
                mst.insert(abs(b - (*it)));
                st.insert(b);
            }
            else
            {
                set<ll>::iterator it = st.lower_bound(b);
                if (it == st.begin())
                {
                    mst.insert(b - (*it));
                    st.insert(b);
                }
                else if (it==st.end())
                {
                    it--;
                    mst.insert(b - (*it));
                    st.insert(b);
                }
                else
                {
                    set<ll>::iterator it1 = it;
                    --it;
                    int diff = (*it1) - (*it);
                    multiset<ll>::iterator it2 = mst.find(diff);
                    mst.erase(it2);
                    st.insert(b);
                    mst.insert(b - (*it));
                    mst.insert((*it1) - b);
                }
            }
        }
        else
        {
            if (n==1) {
                st.erase(b);
            }
            else
            {
                set<ll>::iterator it = st.lower_bound(b), it1=it, it2=it;
                if (it1 == st.begin())
                {
                    it++;
                    mst.erase(mst.find((*it) - (*it1)));
                    st.erase(b);
                }
                else if (b == (*--st.end()))
                {
                    it--;
                    mst.erase(mst.find((*it1) - (*it)));
                    st.erase(b);
                }
                else
                {
                    --it;
                    ++it1;
                    mst.erase(mst.find((*it2) - (*it)));
                    mst.erase(mst.find((*it1) - (*it2)));
                    mst.insert((*it1) - (*it));
                    st.erase(b);
                }
            }
            n--;
        }
        getAns();
    }
    return 0;
}

Found it: Thanks a lot for the help.

Editorial for E is not visible, can you please fix it.

Editorial please, it seems to be taking forever.

Hope this helps https://mirror.codeforces.com/contest/1398/submission/89925922

Can you tell your approach please.

Can you please explain the approach.

I used 3d dp to solve it. Sort all the r, g, b arrays.

Now for state solve(i, j, k) => we can have 3 possibilities

1. solve(i-1, j-1, k) + r[i]*g[j]
2. solve(i, j-1, k-1) + g[j]*b[k]
3. solve(i-1, j, k-1) + r[i]*b[k]

Take max of all the three. You will have your answer.

Here is the link to code using above approach https://mirror.codeforces.com/contest/1398/submission/89925922

How to solve E? Can it be solved using set and priority_queue.

Why are not people discussing how to solve questions, i generally try to go through comments to find interesting approaches. Today i don't seem to find any.

Can someone please explain how to solve div-2 E ? Thanks in advance.

How to solve div-2 D in O(n root n). Thanks in advance.

Rescheduled

Me too

How to approach question D?

Thanks a ton for your help.

Thanks a ton for the help. I will remember this from now own.

Feels so good to to see it getting accepted.

Using you hint i tried to solve this with kadane's kind of approach, But its getting TLE on test — 9. Can you please help me figure out why is this getting TLE ? https://mirror.codeforces.com/contest/1373/submission/85147824

Thanks in advance for the help.

Can anyone please help me figure out why is this O(n) solution for F getting TLE on case — 9 https://mirror.codeforces.com/contest/1373/submission/85147824

Thanks in advance for the help.

Right my mistake.

It is 150.

It took me more time to figure out correct solution for C than D.

Hint kadane's algorithm.

For me today B < A and D < C.

How to solve E?

How to solve D for n <= 10^18 without matrix multiplication?

Thank you

Can you please provide link to his blog? It would be really helpful to learn from his blog.

How to solve D?

Problem E is very interesting. Can someone please help me figure out the best possible solution for problem E if condition b[i] < b[i+1] was not in place.

How to solve Question D? Couldn't come up with a strategy.

Couldn't solve it, but i changed my code for this testcase

n = 6

[9, 1, -9, 2, 2, 2]

How to solve D?

How to solve E?

Thanks, understood the mistake I was making.

How to solve Div-2 D. Will greedy work here ?

I can never understand how this down voting thing works here and I know I will be getting many more downvotes on this , but I just asked a doubt, that sometimes feels like a curse. I thought the whole idea of codeforces is to make people better at algorithms.

I have same doubt, Can someone please explain this in detail?

Thanks go it , i assumed lcm to be divisble by x, which was a stupidity.

I kind of used the same logic, if possible can you please tell why is this solution failing. http://mirror.codeforces.com/contest/992/submission/39386988

How to solve div-2 B?

One hell of system testing, Seeing such dynamics in system testing after a long time.

How to solve div2-E?

Thanks

I had to read the statement 10 times to understand it. For me it was very confusing.

yes.

How to solve div2 -c ?

Oh, i thought that was stated in first statement of the problem.

I took it for equal number of elements.

Thanks for clarifying.

But in the statement its given that

"There shouldn't be equal elements in the subsets."

In this case both the subsets have 2 elements.

For ques B

Is this a valid test case ?

4
1 10 
2 6
3 5
4 2
4
1 1
2 2
3 7
4 8

If yes

what is the answer for this test case

Can someone translate problem D

Thanks for giving me another problem which can be solved with trie.

No i solved it without segment tree.

How to solve div2-B ?

Thanks for such a nice solution.

Can someone give more detailed explanation of problem D ?

Thanks

will this work in 1sec ?? . Complexcity of your approach will be (300*300*300)*log10^7 .

I did that but got a wa at 3 pretest case.

How to solve Div-2 D

Am I the only one waiting for score distribution ??

fight for being in div-1 got more interesting .

i used bfs

thnx .

System Testing is over . why cant we submit in practice.

In prob -B what is the ans of 7 -1 3 1 2 1 1 1 4 4 2 4 3 5 5

please explain how u arrived at this formula .. thnx

i know a n*k solution using dp but that will time out .

Can anybody tell how to solve div-2 E ??

thanks got it ....

how to solve E??

thnx missed it completely ....and got hacked :(

what was the hacking case in div-1 A

how to solve E

how to solve E .

how to solve div-1 d .

thnx got it .. did mistake in checking ... so stupid of me..

can u tell why my solution was hacked.... on your test case as well i am getting 1 2 as the ans . http://mirror.codeforces.com/contest/480/submission/8311510

i will try to explain my approach . first find if any of x or y exists or not . if they both exist than output 0 if only one exist than output the other one if none exist than starting from every point find arr[i]-x,arr[i]+x,arr[i]-y,arr[i]+y keeping in mind about the overflow. if any of them occurs twice than output that coordinate else output given x and y. did i miss any case ??

can u tell how to do it ... my solution was n^3 dp .

thnx ..got it

missed it completely ...thnx

how to solve B -div1 ??

i used same kind of approach ... if possible can u tell whats wrong with my solution.... http://ideone.com/TWhSUX

what was the hacking case in div-1 B...my solution got hacked :(

how to solve D??

are the prefixes proper or any prefix ... i mean say have already typed "an" and one of my words contain "an" so will my 1 tab be wasted on this .

thnx a lot ...

can somebody explain the approach of K ... is it trie+dp ??

Thanks a lot ....it really helped

if possible please provide the code as well...

thanks..well explained

can anyone explain div1-B . I was trying something with trie ....but coludnt get it ...

oh i got to know it now .... even i missed it .. but the contest was awesome .

can anyone provide me good editorial for dp with bitmask .

what was to be done in div-2 C ....

i am getting 4 as the output ... is it right??

can anybody please tell whats wrong with my approch in C ... please help .. http://mirror.codeforces.com/contest/448/submission/7138159

can anybody please explain how to solve D.. thanks

can anybody explain me how to solve div-2 D . thnx

yeah ...and hope federer wins this one