ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1886. Trip 2

Admin! test is weak! (Look the reply)
Posted by Radi Muhammad Reza 30 Mar 2012 20:39
my simple dp solution got tle 17. after optimizing with bin_search and map (for searching if a range of edges already visited) but surprisingly this got me wa 17. please, help. some useful test cases or hint would be really appreciated.
Thanks in advance :)


Edited by author 30.03.2012 22:05
Re: help wa 17 (Admin! test is weak!)
Posted by Radi Muhammad Reza 30 Mar 2012 21:50
got AC but shouldn't have. i used map to keep mark upto what edges outgoing from a certain node we have already dp'ed. and return in log(n). but when i have to dp more then dp'ed and entered into map for that node. however, this gave wa 17. then i dp'ed some more node although already dp'ed. if this 'some more' is less than 9 then i get wa on (18~23) tests. but when it is >=9 i get AC. i dunno why my soln was WA, it seemed perfect. but even more surprising when i get AC like this. Portion of my code:-

#define WHATTHEHECK 9
...

map<int,double> optimize[MAX];
...

int lim1=arr[edgeno].dtime+arr[edgeno].dur,lim2=lim1+arr[edgeno].delay;
    int s1=v[to].size(),s2=s1;
    int lo=0,hi=s1-1,mid;
    while(lo<=hi){
        mid=(lo+hi)/2;
        if(lim1<=arr[v[to][mid]].dtime){
            hi=mid-1,s1=mid;
        }else lo=mid+1;
    }
    lo=0,hi=s2-1;
    while(lo<=hi){
        mid=(lo+hi)/2;
        if(lim2<=arr[v[to][mid]].dtime){
            hi=mid-1,s2=mid;
        }else lo=mid+1;
    }
    int i=-1;
    if(optimize[to].size()==0) i=v[to].size()-1;
    else i=min((*optimize[to].begin()).first+WHATTHEHECK,v[to].size()-1);
    if(i>=s1){
        for(;i>=s1;--i){
            optimize[to][i]=ret1=min(ret1,dp(v[to][i]));
        }
    }
    if(s1<v[to].size()) ret1=optimize[to][s1];
    if(s2<v[to].size()) ret2=optimize[to][s2];

ps: i would be really glad if someone explain me what i did wrong and what's going on here
:)
Re: Admin! test is weak! (Look the reply)
Posted by Maydell Anton 31 May 2023 00:11
I got WA17 when I wrongly (overwrite old mean) insert into segment tree flights with same departure airport and same departure time.