Help needed in Doctor Chef (WA in sample testcases)

this is a question from july long challenge.
Question Link - CodeChef: Practical coding for everyone

my solution link - CodeChef: Practical coding for everyone

i think there is some issue with while loop but i cannot find it, because of which i cannot even clear the sample testcases. Kindly Help !

A short gist of my logic -
Note 1 : IF a country gets cured then i remove that countryā€™s population from multiset.
Note 2 : if the multiset is empty, just print out the days.

if X is greater than or equal to most populated country then answer is number of countries present in my multiset.

else two conditions arise -

  1. if there is a value in multiset (each set element representing a countryā€™s population) which falls in the range [x,2x] inclusive then, we know that answer is days = days + current set.size (as from this day we will need only as many days as many countries are left to be cured)

  2. Else if no element of the set falls within the range [x,2x] then we will use two times of, cures used on previous day, to cure the country with the largest population currently present in multiset. and also update the x for next day
    i.e x = 2*x

Undefined Behaviour all over the place :slight_smile:

Read this, and compile with all the #defines mentioned there and run it with the sample testcase.

2 Likes

ok i will try this

is it actually integer overflow ?

Try it and see :slight_smile:

Compile with these flags:

-D_GLIBCXX_DEBUG    -fsanitize=undefined -ftrapv
3 Likes

what is this flag ? i have no idea what is this and from where to learn to use this. from where can i learn about this ? will that codeforces link guide me properly ?

1 Like

SIGABRT error is being returned in output console when i use
#pragma GCC optimize ā€œtrapvā€ on teh top of my code

with this flag i m getting something like this but i cannot figure out why ?

prog.cpp: In function ā€˜std::basic_ostream<_CharT, _Traits>& std::flush(std::basic_ostream<_CharT, _Traits>&) [with _CharT = char; _Traits = std::char_traits<char>]ā€™:
prog.cpp:150:1: internal compiler error: Segmentation fault
 }
 ^
Please submit a full bug report,
with preprocessed source if appropriate.
See <file:///usr/share/doc/gcc-6/README.Bugs> for instructions.

plz help me anyone

can you plz help ?? i donā€™t how to use these flags. PLz respond

Thereā€™s an example of using them here.

If youā€™re getting an internal compiler error, then thereā€™s not much I can recommend except ā€œupgrade your compilerā€ (GCC 6 is pretty old).

1 Like

canā€™t i do this on codechefā€™s or codeforcesā€™s compiler ?

You can, but youā€™ll get much less useful information about whatā€™s going on, and wonā€™t be able to use a debugger. I wouldnā€™t bother, personally: just sort out your local build environment and use that.

1 Like

Can you share some syntax on how to use these flags in a c++ code ?

And also if possible a small example of code along with with the output error message, so that i can learn how to use this.
Also i donā€™t know anything about pragma.

Passing a bunch of debug flags to g++:

[simon@simon-laptop][13:36:04]
[~/devel/hackerrank/otherpeoples]>g++ rudyiscrazy1-DRCHEF.cpp  -g3 -O3 -Wall -Wextra  -DONLINE_JUDGE -D_GLIBCXX_DEBUG    -fsanitize=undefined -ftrapv
rudyiscrazy1-DRCHEF.cpp: In function ā€˜int main()ā€™:
rudyiscrazy1-DRCHEF.cpp:41:14: warning: ignoring return value of ā€˜int scanf(const char*, ...)ā€™, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&N) ;
         ~~~~~^~~~~~~~~
rudyiscrazy1-DRCHEF.cpp:42:15: warning: ignoring return value of ā€˜int scanf(const char*, ...)ā€™, declared with attribute warn_unused_result [-Wunused-result]
         scanf ("%ld",&x) ;
         ~~~~~~^~~~~~~~~~
rudyiscrazy1-DRCHEF.cpp:53:19: warning: ignoring return value of ā€˜int scanf(const char*, ...)ā€™, declared with attribute warn_unused_result [-Wunused-result]
             scanf ("%ld",&val) ;
             ~~~~~~^~~~~~~~~~~~
[simon@simon-laptop][13:36:12]
[~/devel/hackerrank/otherpeoples]>echo "3
> 5 5
> 1 2 3 4 5
> 5 1
> 40 30 20 10 50
> 3 10
> 20 1 110" | ./a.out
rudyiscrazy1-DRCHEF.cpp:122:41: runtime error: signed integer overflow: -6148914691236495360 * 2 cannot be represented in type 'long int'
rudyiscrazy1-DRCHEF.cpp:14:27: runtime error: signed integer overflow: 5764607523034234880 * 2 cannot be represented in type 'long int'
/usr/include/c++/7/debug/safe_iterator.h:327:
Error: attempt to decrement a dereferenceable (start-of-sequence) iterator.

Objects involved in the operation:
    iterator "this" @ 0x0x7ffcb476d060 {
      type = __gnu_debug::_Safe_iterator<std::_Rb_tree_const_iterator<long>, std::__debug::multiset<long, std::less<long>, std::allocator<long> > > (mutable iterator);
      state = dereferenceable (start-of-sequence);
      references sequence with type 'std::__debug::multiset<long, std::less<long>, std::allocator<long> >' @ 0x0x7ffcb476d300
    }
Aborted (core dumped)

If you canā€™t do that, you can make sure the first two lines in your .cpp file are:

#define _GLIBCXX_DEBUG       // Iterator safety; out-of-bounds access for Containers, etc.
#pragma GCC optimize "trapv" // abort() on (signed) integer overflow.

(this doesnā€™t include the -fsanitize=undefined flag, alas - not sure how to do that), but as I mentioned, this seems to give much less useful information, so Iā€™d stick with compiling locally and passing the flags to gcc.

1 Like

hey i got few things cleared from your local compiling ! so there are two places where i am getting int overflow and at one place i m decrementing a iterator pointing to start of the container.

but there is new problem eating my head -
#pragma GCC optimize ā€œtrapvā€

does this give an error message similar to the fashion in which we get when we use #define _GLIBCXX_DEBUG

or it just tells us a SIGBART error

herre is what i get when i compiled my code with just #pragma GCC optimize ā€œtrapvā€

That just gives SIGABRT on signed integer overlow. Itā€™s mainly useful for deciding whether your WA is due to integer overflow or not; -fsanitize=undefined is probably better for local debugging.

1 Like

okay things are getting clearer, Thnx a lot !
By the way, what does this part means, " ignoring return value of ā€˜int scanf(const char*, ā€¦)ā€™, declared with attribute warn_unused_result [-Wunused-result] ", while you are compiling ??

scanf has a return value, but you are ignoring it (as do about 99% of C programmers in the world :))

2 Likes

so i started using VS code from today and set it up for debugging from
this official page : Get Started with C++ and Mingw-w64 in Visual Studio Code

and when i tried to locally compile a small code to check whether the flags are working i got this :

can you help me figure it out why ??