CodingKnight's blog

By CodingKnight, 3 days ago, In English

Hello Codeforces,

I found this hard practice problem H — Unpredictable Array at CodeChef which has 0 successful submissions!

The following is my C++ map-based solution which got TLE. I tried to run this solution using the Codeforces Custom Test with the maximum data size, and the Codeforces judge reported used time 1170 msec. which is within the 2 sec. time-limit of the problem.

I would be grateful for plausible explanation about this discrepancy.

Read more »

 
 
 
 
  • Vote: I like it
  • +2
  • Vote: I do not like it

By CodingKnight, 10 days ago, In English

Hello Codeforces Community,

Congratulations for the installation of C++20 automatic judge. A word of gratitude and appreciation is due to the Codeforces administration team for their endeavors to keep Codeforces up-to-date with the latest developments in C++.

The following program is an example for one of the new features introduced in C++20, __cpp_aggregate_paren_init.

Initializing aggregates from a parenthesized list of values

The following is the expected output of this program.

Output

This program produces a compilation error when compiled using GNU++17 9.2.0 compiler, but can be compiled successfully using GNU++20 11.2.0 compiler. The C++20 compiler translates that statement const FourDPoint p(1,2,3,4) into initializing the data members w, x, y, z of the constant object p to 1, 2, 3, and 4, respectively. Similarly, the compiler passes the initialization list {5,6,7,8} to the constructor of the base class array<int,4>, even though both classes FourDPoint and Array<int,4> do not have explicit class constructors.

Read more »

 
 
 
 
  • Vote: I like it
  • +10
  • Vote: I do not like it

By CodingKnight, 2 weeks ago, In English

Hello Codeforces,

It is sometimes required in competitive programming contests, specially in long-time challenges when there is enough time to trace the program execution behavior at run-time before submitting it to the automatic judge, to track the passed arguments and return value of some C++ function(s). This blog presents a simple C++ tracer class for such purpose.

The following is the class declaration and implementation.

Tracer code

If the macro TRACE is defined before this tracer code, the following trace operations are enabled using Variadic Macros and Variadic Function Templates.

  1. tr_begin(...) macro call increments the trace depth, and then prints the passed arguments.
  2. tr(...) macro call prints the passed arguments without updating the trace depth.
  3. tr_end(...) macro call prints the passed arguments, decrements the trace depth, and returns the first argument. This call can be used as the return value of the traced function.

Each traced function should have a tr_begin(...) macro call at the beginning of the function block, a tr_end(...) macro call at the end of the function block, and zero or more tr(...) macro call(s) inside the function block.

If the TRACE macro is undefined before the tracer code, the aforementioned trace operations are disabled.

The following is an example program to test the functionality of the tracer by tracking the execution of the recursive algorithm for computing the factorial function $$$n!$$$.

Example

The following is the standard output printed results of the example program when the TRACE macro is defined.

Output

Your constructive comments and feedback are evermore welcome.

Update

  • The following are interesting related blogs, shared thankfully by other Codeforces members.

    1. darkkcyan, My CP debugging template, shared by jalsol.
    2. rachitiitr, C++ Trick — Easy Debugging / Logging, shared by Manan_shah.
  • The trace macros trace_call(...) and trace_ret(...) were renamed to tr_begin(...) and tr_end(...), respectively, and a third macro tr(...) was added. The value of the built-in macro __LINE__ was also passed to each tracer object public member function call so as to identify the location of the trace point inside the traced function.

  • The macro db() by darkkcyan was adopted. If the macro TRACE is defined, then db(arg) produces string(arg)+" = "+tracer.stringify(arg). Any variadic argument of the macro calls tr_begin(...), tr(...), or tr_end(ans,...) can be passed as either arg or db(arg)

The following is the GitHub archive of the tracer code.

tracer@GitHub

Read more »

 
 
 
 
  • Vote: I like it
  • +40
  • Vote: I do not like it

By CodingKnight, 4 weeks ago, In English

Hello Codeforces,

I am a 56-year old life-long learner and computer-programming lover with PhD degree in Electronics and Electrical Communications Engineering from Cairo University, Egypt, and with research interest in VLSI CAD algorithms, computer architecture, digital signal and image processing. I joined Codeforces five years ago to encourage my son during his first year in college, and I participate almost regularly in long-time competitive programming challenges as time permits.

I participated last week in HackerEarth September Circuits '21 Long-Time Contest that ended yesterday, and I reached the 4th rank on the Leaderboard of the Contest. The approximate problem in the Contest was a variant to the well-known Traveling Salesman Problem (TSP). To my surprise, the first runner-up commented about four days ago that the checker program of this problem was broken and it accepted invalid solutions. As such, only two contestants managed to write wrong solutions that exploited the incorrectness of the checker in getting the highest possible score, while other contestants including me who wrote correct solutions assuming that the checker program would reject invalid solutions did not reach 1% of the score of the wrong solutions.

I am writing this blog to urge the HackerEarth team whose members announce in Codeforces invitations to regular HackerEarth Contests to review thoroughly the checker programs of the problems posted in its regular contests. The issue of broken checker took place several times in the past few months Circuits long-time Contests without any apology and without any announcement that corrective procedure would be pursued to be more sure that future contests do not include broken checker programs.

Thanks in advance for the constructive feedback and response.

Read more »

 
 
 
 
  • Vote: I like it
  • +72
  • Vote: I do not like it

By CodingKnight, 5 weeks ago, In English

Hello Codeforces,

This is an update to an old blog I wrote 15 months ago about measuring elapsed time between two events in C++ programs on real-time scale such as milliseconds using the std::chrono library classes and functions.

The following is the class declaration and implementation.

class Timer

The template has two parameters: clock and units corresponding to the used std::chrono clock and time units of the timer interval, respectively. The value passed to clock should be high_resolution_clock, system_clock, or steady_clock. The default value for units is milliseconds. Other possible values for units include nanoseconds, microseconds, etc. check chrono::duration for more details.

The class has three public member functions:

Timer(const units interval);
units elapsed_time() const;
bool expired();

The first public member function Timer(const units interval) is the class constructor used to create a timer object. The second function elapsed_time() returns the elapsed time since the creation of the object. The third function expired() returns false if such elapsed time has not reached interval yet; otherwise, the function returns true.

The following is an example program to test the functionality of the class by creating a timer object with 1.5 sec interval.

Example

The following is the stdout printed results of the example program.

Output

Your constructive comments and feedback are welcome.

Update: The third parameter value_t was removed from the template to make the class declaration more compact.

Read more »

 
 
 
 
  • Vote: I like it
  • +72
  • Vote: I do not like it

By CodingKnight, 6 weeks ago, In English

Hello Codeforces,

I got the following compilation error

Cannot compile file:
In file included from C:/Programs/msys2-mingw64-9/include/c++/9.2.0/pstl/parallel_backend.h:14,
                 from C:/Programs/msys2-mingw64-9/include/c++/9.2.0/pstl/algorithm_impl.h:25,
                 from C:/Programs/msys2-mingw64-9/include/c++/9.2.0/pstl/glue_execution_defs.h:52,
                 from C:/Programs/msys2-mingw64-9/include/c++/9.2.0/execution:32,
                 from program.cpp:2:
C:/Programs/msys2-mingw64-9/include/c++/9.2.0/pstl/parallel_backend_tbb.h:19:10: fatal error: tbb/blocked_range.h: No such file or directory
   19 | #include <tbb/blocked_range.h>

when I added the include command #include <execution> to use the execution::par constant.

128886532

The program compiles successfully on my local computer. Am I missing something that can fix this compilation error?

Read more »

 
 
 
 
  • Vote: I like it
  • -5
  • Vote: I do not like it

By CodingKnight, 7 weeks ago, In English

Hello Codeforces,

I posted this blog in CodeChef Discussion Forum few hours ago. I have just thought about posting it here for those interested in logic programming. CodeChef is distinguished in having Prolog among the available programming languages in its automatic judge system for competitive programming and problem solving.

I am a life-long lover for programming in Prolog, even though Prolog is not commonly used for competitive programming purposes. I noticed that the following sample solution for Prolog code does not identify explicitly the specific requirement for submitted Prolog code.

Prolog Sample Solution

In particular, the automatic judge requires that the entry point of the solution is predicate program/0. The following are sample accepted Prolog solutions.

1. ATM

2. Life, the Universe, and Everything

3. Factorial

Lines 3-22 in these accepted submissions include helper predicates for reading input data from the standard input stream.

CodeChef automatic judge uses presently version 7.2.3 of the free SWI-Prolog compiler, whose documentation is available online. The automatic judge returns a compilation error message if the submitted Prolog code does not include predicate program/0.

Learn Prolog Now is a good source for life-long learners who wish to learn about Prolog.

Read more »

 
 
 
 
  • Vote: I like it
  • -16
  • Vote: I do not like it

By CodingKnight, 16 months ago, In English

Hello Codeforces,

It is sometimes required in competetive programming problems to use fast data input/output and/or read and write problem data from and to data files. It is well known that the C++ standard libray functions std::ios_base::sync_with_stdio(), std::basic_io::tie(), and std::freopen() can be used to peform the sought input/output initializtion. The following is a C++ io_init class that simplifies this initialization by encapsulating it inside public class constructors.

#include <bits/stdc++.h>
using namespace std;

class io_init {
    struct fast { fast() { ios_base::sync_with_stdio(false), cin.tie(nullptr); } } io;
    void reopen(const string &file_name, const char *mode, FILE *stream) {
        if (freopen(file_name.c_str(),mode,stream) == nullptr) 
            throw runtime_error("freopen() failed: cannot open file "+file_name); }
public:
    io_init() {}
    io_init(const string &data) { reopen(data+".in","r",stdin), reopen(data+".out","w",stdout); } };
		    
int main() { 
     io_init(); // io_init("data"); 
    // solution
}

The first class constructor without parameter initializes fast input/output by creating the io instance of the private data structure fast. The second class constructor with string data paremeter performs the same operation, and then initializes the data input/output to read data from input file data+".in" and write results to output file data+".out". The private class member function reopen() throws a run-time error exception if the freopen() function call returns nullptr.

Your constructive comments and feedback are welcome and appreciated.

UPDATE

The following alternative to use a fuction call instead of using public class constructors is favored by Actium.

#include <bits/stdc++.h>
using namespace std;

void io_init(const string &data = "") { 
    const auto reopen = [data](const string &ext, const char *mode, FILE *stream) {
        const string file_name = data+"."+ext;
        if (freopen(file_name.c_str(),mode,stream) == nullptr)
            throw runtime_error("freopen() failed: cannot open file "+file_name); };
    if (ios_base::sync_with_stdio(false), cin.tie(nullptr), not data.empty())
        reopen("in","r",stdin), reopen("out","w",stdout); }
		    
int main() {
    io_init(); // io_init("data");
}

A third alterntative (favored by spookywooky) that does not require a function call to be included in the main() function is to declare io_init as a named lambda expression as follows.

#include <bits/stdc++.h>
using namespace std;
     
const auto io_init = [](const string &data = "") {
    const auto reopen = [data](const string &ext, const char *mode, FILE *stream) {
        const string file_name = data+"."+ext;
        if (freopen(file_name.c_str(),mode,stream) == nullptr)
            throw runtime_error("freopen() failed: cannot open file "+file_name); };
    if (ios_base::sync_with_stdio(false), cin.tie(nullptr), not data.empty())
        reopen("in","r",stdin), reopen("out","w",stdout); 
        return 0; } (); // ("data");
    
int main() {
    // solution
}

A fourth alterntative and perhaps the simplest way to initialize data input/output files for read/write is to create std::ifsteam and std::ofstream objects. Names other than cin and cout should be used for the created object if using namespace std; is part of the program so as to avoid name redeclaration errors.

#include <bits/stdc++.h>
using namespace std;
     
ifstream  i_data("data.in");
ofstream  o_data("data.out");

#define cin  i_data
#define cout o_data

int main() {
    
   int a, b; 

   cin >> a >> b;        // read (a) and (b) from file data.in

   cout << a+b << endl;  // write (a+b) to file data.out
}

Read more »

 
 
 
 
  • Vote: I like it
  • -23
  • Vote: I do not like it

By CodingKnight, 16 months ago, In English

Hello Codeforces,

It is sometimes required in competitive programming problems at run-time to measure elapsed time between two events on a real-time scale such as milliseconds. It is possible in C++ to do that using the std::chrono library classes and functions. The following is a C++ timer class that simplifies doing this operation.

#include <bits/stdc++.h>
using namespace std;
using namespace chrono;

class timer: high_resolution_clock {
    const time_point start_time;
public:
    timer(): start_time(now()) {}
    rep elapsed_time() const { return duration_cast<milliseconds>(now()-start_time).count(); } };

The timer class inherits the base class std::chrono::high_resolution_clock. A private std::chrono::time_point constant variable start_time is used to store the initial point of time at which the timer object was created using the class constructor function. The class features a constant public member function elapsed_time() whose call returns a non-negative integer which measures the elapsed time in milliseconds since the creation of the timer object.

The following is a sample example for using the timer class.

const int T = 1000;
timer t; // create a timer object

int main() {
    while (t.elapsed_time() < T) {
        // do something
    }
}

Your constructive comments and feedback are welcome and appreciated.

Read more »

 
 
 
 
  • Vote: I like it
  • +3
  • Vote: I do not like it

By CodingKnight, 18 months ago, In English

Hello Codeforces,

It is well-known that C++ Input/output manipulators such as fixed, setprecision, endl, etc. are helper functions that serve as user-friendly control commands to input/output streams.

An input-stream command that is necessary but not common in competitive programming is to discard all characters until and including the new-line character. An example for this issue is the following HackerEarth problem. Although the problem is very easy, its data-input invovles a trick that the input string in each line can include a space character as a part of the string.

Using the function call std::getline(cin,s) to read the line which includes space characters right after reading the number of test cases using the input command cin >> t causes the first call of std::getline(cin,s) to read an empty string, as the new-line character at the end of the first line which contains the number of test cases would have not been read yet.

It is possible to use an extra call to std::getline(cin,s) to solve this issue, but a more elegant solution is to declare and use a simple C++ input-stream manipulator whose purpose is to disard the new-line character using a call to the standard function std::istream::ignore.

The followng is the one-line code of the skip_endl input-stream manipulator.

#include <bits/stdc++.h>
using namespace std;

inline istream& skip_endl(istream &is) { return is.ignore(numeric_limits<streamsize>::max(),'\n'); }

And the following is a simple example for using it.

inline string solve(const string &s) {
    string t;
    // code to convert each character in string (s) into its equivalent character(s) 
    // in string (t) should be written here
    return t; }

int main() {
    int t; string s; 
    ios_base::sync_with_stdio(0), cin.tie(0), cin >> t >> skip_endl; 
    while (t--) 
        getline(cin,s), cout << solve(s) << '\n'; }

Your constructive comments and remarks are welcome.

Stay safe, and keep the good work going.

P.S. HackerRank default C++14 code in practice problems often includes the explicit command cin.ignore(numeric_limits<streamsize>::max(),'\n') for the same purpose.

Read more »

 
 
 
 
  • Vote: I like it
  • +26
  • Vote: I do not like it

By CodingKnight, 18 months ago, In English

Hello Codeforces,

I have just been practicing during final hour of the open-hacking phase of yesterday's Div. 4 round, when I noticed that someone has just successfully hacked his/her own solution submitted during the contest!

Is there any reasonable explanation for doing that?

Read more »

 
 
 
 
  • Vote: I like it
  • +12
  • Vote: I do not like it

By CodingKnight, history, 18 months ago, In English

Hello Codeforces,

Hope that you are all safe and physically distant enough to avoid COVID-19 infection.

Has anyone seen the strange Verdict of the following submission before?

79000718

Read more »

 
 
 
 
  • Vote: I like it
  • +23
  • Vote: I do not like it

By CodingKnight, 19 months ago, In English

Hello Math lovers,

The following is a C++ data structure whose constructor uses arithmetic difference equations of the form $$$f(n+1)-f(n)$$$ to generate all squared integers up to a given upper bound $$$N$$$ without multiplication.

struct squares: std::vector<int64_t> {
    squares(int64_t N) {
        for (int64_t f = 0, g = 1; f <= N; ++g)
            push_back(f), f += g++; } };

It is well known in arithmetics that if $$$f(n) = n^2$$$ and $$$g(n) = 2n+1$$$, then $$$f(n+1) = f(n)+g(n)$$$ and $$$g(n+1) = g(n)+2$$$. The initial state for the iterative algorithm is $$$f(0) = 0$$$ and $$$g(0) = 1$$$.

Alternatively, squared integers up to $$$N$$$ could have been generated using multiplication directly without using difference equations.

struct direct_squares: std::vector<int64_t> {
    direct_squares(int64_t N) {
        for (int64_t f, n = 0; f = n*n, f <= N; ++n)
            push_back(f); } };

The following is the C++ program written to compare the performance of both data structures.

using Clock = std::chrono::high_resolution_clock;
using Time  = std::chrono::time_point<Clock>;
inline Time Now() { return Clock::now(); }
template<class T> 
inline int64_t msec(T t) { 
    return std::chrono::duration_cast<std::chrono::milliseconds>(t).count(); }

inline std::string type_name(const std::string &s) {
    int i = 0; 
    while (isdigit(s[i]))
        ++i;
    return s.substr(i); }
    
template<class T>
void test() {
    const Time initial_time = Now(); 
    const T s(1e14); 
    const int64_t t = msec(Now()-initial_time); 
    const auto name = type_name(std::string(typeid(T).name())); 
    std::cout << "struct " << name << ": elapsed time " << t << " msec.\n"; }
    
int main() { 
    test<squares>(), 
    test<direct_squares>(); }

The following is the results of running the performance evaluation program.

A. Using G++14 6.4.0

struct squares: elapsed time 110 msec.
struct direct_squares: elapsed time 112 msec.

=====
Used: 218 ms, 197032 KB

B. Using G++17 7.3.0 (32-bit)

struct squares: elapsed time 121 msec.
struct direct_squares: elapsed time 93 msec.

=====
Used: 234 ms, 197040 KB

C. Using G++17 9.2.0 (64-bit)

struct squares: elapsed time 121 msec.
struct direct_squares: elapsed time 94 msec.

=====
Used: 218 ms, 198056 KB

Read more »

 
 
 
 
  • Vote: I like it
  • -74
  • Vote: I do not like it

By CodingKnight, 20 months ago, In English

Hello Codeforces,

I stopped using Code::Blocks IDE in my local computer recently due to some issue in compilation and debugging. I mostly use Ideone.com online compiler presently. I use the Secret option by default, which should make my code available only to those whom I choose to share the link. I also use the Custom Invocation option in Codeforces sometimes.

My question is: Should I trust that the Secret option in Ideone.com is secure enough to make sure that no one can get the code without permission? If not, what would be the most reliable secure online C++ compiler that you recommend?

Thanks in advance for sharing your knowledge and experience.

Read more »

 
 
 
 
  • Vote: I like it
  • +22
  • Vote: I do not like it

By CodingKnight, 3 years ago, In English

Hello C++ learners in Codeforces,

The following is a tutorial C++ class class tutorial_t: vector< T > that illustrates using the standard library function templates std::lower_bound and std::upper_bound.

Tutorial C++ Class

The C++ class inherits the base class vector< T > and generalizes the example given in

  1. www.cplusplus.com/reference/algorithm/lower_bound

  2. www.cplusplus.com/reference/algorithm/upper_bound

to demonstrate using both function templates for an arbitrary unsorted input array of size n, and an arbitrary value val. The item type T should be instantiated in line 5. For example, typedef double T; allows illustrating the result of searching for the lower-bound and upper-bound in a sorted array of floating-point numbers. Furthermore, standard assert( int expression ) C macro calls are used to illustrate invariant expressions that are guaranteed to be true for any test case.

UPDATE The data item typename parameter T has been removed from the class declaration so as to allow using a single member function example to illustrate both std::lower_bound and std::upper_bound functions. The corresponding function calls are passed to the example function as lambda expressions.

P.S. Downvoters are invited to share their constructive feedback fairly if they can express what they don't like about this blog, and they care to help others and have more time than the time spent to click the dislike voting button. They do not have to create other accounts in Codefores to do that.

Read more »

 
 
 
 
  • Vote: I like it
  • -29
  • Vote: I do not like it

By CodingKnight, 3 years ago, In English

In matrix theory, a lower-triangle/upper-triangle matrix is a special n × n square matrix where its items above/below the main diagonal are zeros, and therefore at most of its items are non-zeros. Formally, a lower-triangle matrix A satisfies the condition ai, j = 0 if i < j, and an upper-triangle matrix A satisfies the condition ai, j = 0 if i > j, where i is the row index, j is the column index, and 1 ≤ i, j ≤ n.

The following are simple and memory-efficient C++ templates for lower-triangle and upper-triangle matrices that allocate dynamically at run-time using the vector::resize() STL member function the size of each row to store only the non-zero items. This can be useful in saving about half the memory size of the full square matrix when n is large. Individual non-zero items are updated in both templates using set() member function, and the value of an individual zero/non-zero item is read using get() member function.

#include <bits/stdc++.h>

using namespace std;

template< typename T > struct lower_triangle: vector< vector< T > >
{
    lower_triangle( size_t n )
    {
        for( size_t row_size = 1; row_size <= n; row_size++ )
            this->emplace_back(), this->back().resize( row_size );
    }

    void set( size_t i, size_t j, T k )
    {
        assert( i >= j and i >= 1 ), this->at( i - 1 ).at( j - 1 ) = k;
    }

    T get( size_t i, size_t j ) const
    {
        return ( i >= j and i >= 1 ) ? this->at( i - 1 ).at( j - 1 ) : 0;
    }
};

template< typename T > struct upper_triangle: vector< vector< T > >
{
    upper_triangle( size_t n )
    {
        while( n > 0 )
            this->emplace_back(), this->back().resize( n-- );
    }

    void set( size_t i, size_t j, T k )
    {
        assert( j >= i and i >= 1 ), this->at( i - 1 ).at( j - i ) = k;
    }

    T get( size_t i, size_t j ) const
    {
        return ( j >= i and i >= 1 ) ? this->at( i - 1 ).at( j - i ) : 0;
    }
};

The following is a sample program that illustrates using these C++ templates.

int main()
{
    ios_base::sync_with_stdio( false ), cin.tie( nullptr ), cout.tie( nullptr );

    int n; cin >> n; lower_triangle< int > L( n ); upper_triangle< int > U( n );

    for( int i = 1; i <= n; i++ )
    {
        for( int j = 1, k = i; j <= i; j++, k++ )
            L.set( i, j, k );

        for( int j = i, k = 2 * i - 1; j <= n; j++, k++ )
            U.set( i, j, k );
    }

    for( int i = 1; i <= n; i++, cout << endl )
        for( int j = 1; j <= n; j++ )
            cout << L.get( i, j ) << ' ';

    cout << endl;

    for( int i = 1; i <= n; i++, cout << endl )
        for( int j = 1; j <= n; j++ )
            cout << U.get( i, j ) << ' ';
}

UPDATE

The following is an alternative approach for implementing the C++ templates using one-dimensional arrays based on the constructive comment from f2lk6wf90d. Performance analysis should compare the average execution time and memory requirements of both approaches. A word of gratitude is due to tryhard for recommending this modest blog.

inline size_t C2( size_t n ) { return n * ( n - 1 ) / 2; }

template< typename T > struct lower_triangle: vector< T >
{
    lower_triangle( size_t n )
    {
        this->resize( C2( n + 1 ) );
    }

    void set( size_t i, size_t j, T k )
    {
        assert( i >= j and i >= 1 ), this->at( C2( i ) + j - 1 ) = k;
    }

    T get( size_t i, size_t j ) const
    {
        return ( i >= j and i >= 1 ) ? this->at( C2( i ) + j - 1 ) : 0;
    }
};

template< typename T > struct upper_triangle: vector< T >
{
    size_t N, P;

    upper_triangle( size_t n ) : N( n ), P( n + 1 )
    {
        this->resize( C2( P ) );
    }

    void set( size_t i, size_t j, T k )
    {
        assert( j >= i and i >= 1 );  this->at( C2( P - i ) + N - j ) = k;
    }

    T get( size_t i, size_t j ) const
    {
        return ( j >= i and i >= 1 ) ? this->at( C2( P - i ) + N - j ) : 0;
    }
};

Read more »

 
 
 
 
  • Vote: I like it
  • +7
  • Vote: I do not like it

By CodingKnight, 3 years ago, In English

The following submission 52361614 contains a user-defind C++ class modulo for () modular arithmetic, where P is a prime number and all numbers are normalized to the interval [0, P - 1]. The modular division operation y / x is performed by means of multiplying the modulo number y times the modular multiplicative inverse of x computed using the modular power operator xp. The class includes another class modulo::factorial for computing modular factorials n! and modular binomial coefficients m-out-of-n.

The C++ class can be used by Codeforces as any other shared library in the public domain.

Thank you.

Read more »

 
 
 
 
  • Vote: I like it
  • -25
  • Vote: I do not like it

By CodingKnight, 3 years ago, In English

The following is C++17 data structure primes_t for the simple Sieve of Eratosthenes algorithm that features:

  1. Constructor primes_t( int M, int N ) that computes all prime numbers in the interval [M,N], and stores those ordered prime numbers in an inherited vector< int > base class.

  2. Member function bool exists( int x ) that uses binary search to find whether or not x exists among prime numbers in the specified interval.

  3. Inheriting all public member functions of vector< int > as public members functions of primes_t.

#include <bits/stdc++.h>

using namespace std;

struct primes_t: vector< int >
{
    primes_t( int M, int N )
    {
        int p = 3, x = 0, z = ( N - 1 ) / 2; bool composite_odd[ z ];

        for( int x1 = 0; x1 < z; x1++ )
            composite_odd[ x1 ] = false;

        if ( M <= 2 && N >= 2 )
            push_back( 2 );

        for( int q = sqrt( N ); p <= q; p += 2, x++ )
            if ( !composite_odd[ x ] )
            {
                if ( p >= M )
                  push_back( p );

                for( int x1 = p * x + 3 * ( x + 1 ), y1 = p * p; y1 <= N; x1 += p, y1 += 2 * p )
                    composite_odd[ x1 ] = true;
            }

        do
        {
            if ( !composite_odd[ x ] && p >= M )
                push_back( p );

             p += 2, x++;
        }
        while( p <= N );
    }

    bool exists( int x ) const 
    { 
        return binary_search( cbegin(), cend(), x ); 
    }
};

For example, the following program computes and prints the count of prime numbers in the interval [M,N].

int main()
{
    int M, N;

    cin >> M >> N;

    cout << primes_t( M, N ).size();
}

The data structure can be used by Codeforces as any other shared library in the public domain.

Thank you.

Read more »

 
 
 
 
  • Vote: I like it
  • -48
  • Vote: I do not like it

By CodingKnight, 4 years ago, In English

The following is the Prolog help page on the Kattis Problems Archive.

https://open.kattis.com/help/prolog

Kattis uses the free SWI-Prolog compiler to judge solutions implemented in Prolog. It may be useful that Codeforces team considers adopting this approach for including Prolog among the programming languages which can be used in Codeforces Rounds and Educational Contests.

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By CodingKnight, 4 years ago, In English

The ISO International Standard ISO/IEC 14882:2017(E) – Programming Language C++, known as C++17, is the result of excellent efforts by the ISO C++ Standard Foundation Committee to introduce new simple and elegant powerful features to C++.

Adrian D. Finlay, Software Engineer, summarized on Nov 17, 2017, the new C++17 language features that are helpful to competitive programming lovers as well as to professional software engineers and software developers as follows.

"The never-ending journey into learning C++ features….

New Language Features

  1. Addition of __has_include macro

  2. UTF 8 Character Literals

  3. Hexadecimal Floating Point Literals

  4. New rules for deduction of single member list using auto
  5. Update to __cplusplus value

  6. inline variables

  7. New Syntax for Nested Namespace definitions

  8. Initializers added to if/switch statements

  9. constexpr if

  10. New standard attributes fallthrough, maybe_unused &nodiscard ^

  11. Attributes for Enumerator & Namespaces

  12. Error message for static_assert now optional

  13. Structured binding declarations

  14. Keyword typename now allowed in lieu of class in a template’s template paramater

  15. Constant evaluation for non-type template arguments

  16. Class template argument deduction

  17. Extensions on over-aligned Memory Allocation

  18. Fold expressions

  19. List-style Initialization of Enumerations

  20. Specifying non-type template parameters with auto

  21. constexpr lambda expressions

  22. Lambda this by value (*this)

  23. Extending Aggregate Initialization to Base Types

  24. Unknown Attributes Required to be Ignored

  25. Pack Expansions legal in using declarations

  26. Generalization of Range-based for loop

  27. The byte data type ^^

  28. Using attribute namespaces without repetition

  29. Stricter Order of Evaluation Rules

  30. Exception Specifications are part of type definitions

  31. Template-Template Parameters match compatible arguments

  32. Guaranteed Copy Elision

  33. Changes to Specification on Inheriting Constructors

^These are three features grouped into one, which consequently when expanded would make the new feature list count 35.

^^This is implemented in std::byte () and is not a part of the actual language such as the other primitive data types. It is considered a basic type as much as std::string is considered a basic type.

C++17 also introduced a revision to Elementary string conversions".

The Complete Blog posted on Medium.com

Read more »

 
 
 
 
  • Vote: I like it
  • -20
  • Vote: I do not like it

By CodingKnight, history, 4 years ago, In English
 
 
 
 
  • Vote: I like it
  • -17
  • Vote: I do not like it

By CodingKnight, history, 4 years ago, In English

Please refer to the 6th question and its answer in the following Codeforces blog:

Frequently Asked Questions

Best wishes

Read more »

 
 
 
 
  • Vote: I like it
  • -4
  • Vote: I do not like it

By CodingKnight, history, 4 years ago, In English
 
 
 
 
  • Vote: I like it
  • -20
  • Vote: I do not like it

By CodingKnight, 4 years ago, In English

The following declares a C++ class template int_set< int From, int To > that uses bitset STL to compute operations on sets of integers using bitset STL bitwise operators. int_set< int From, int To > is a class of objects that represent subsets of universal domain U = [ From, To ].

Each object stores the membership function of the corresponding subset using a private bitset<N> member exists, where N = ( To - From + 1 ), and can be updated using set insertion/deletion operations.

The main advantage of int_set< int From, int To > is that the set insertion/deletion operations as well as the fundamental set union, intersection, complement, difference, and symmetric difference operations are implemented using the standard C++ bitset STL bitwise operators, unlike the corresponding set STL operations that require adding/deleting elements to/from the binary tree representation of the set, which improves the performance of those operations.

int_set.h and sample test program

Read more »

 
 
 
 
  • Vote: I like it
  • -28
  • Vote: I do not like it

By CodingKnight, 4 years ago, In English

The following are C++11 classes huge_unsigned and binomial_coefficient for computing huge Binomial coefficients C( n, k ), where n and k are positive integers.

The class implements the iterative multiplicative formula:

def binomialCoefficient(n, k):
    if k < 0 or k > n:
        return 0
    if k == 0 or k == n:
        return 1
    k = min(k, n - k) # take advantage of symmetry
    c = 1
    for i in range(k):
        c = c * (n - i) / (i + 1)
    return c

reported in Binomial coefficient without overflow, and without using the modulus arithmetic operator. Items of the STL base class vector< uint32_t > are used to store the successive digits of a base-4,294,967,296 representation of C( n, k ). C( 32000, 16000 ) has been computed using 1000 huge_unsigned digits in 1.873 sec. on Intel Core i3 processor with 3 GB RAM running at 2.4 GHz. Comments and votes (like or do not like) are thankfully and gratefully appreciated.


#include <bits/stdc++.h> using namespace std; struct huge_unsigned: public vector< uint32_t > { uint64_t carry; huge_unsigned() : carry( 0 ) {} huge_unsigned& operator *= ( uint32_t i ) { register uint64_t p, q, x = i; for( register size_t k = 0, l = size(); k < l; at( k++ ) = q, carry = ( q >> 32 ) ) { p = at( k ), q = p * x; if ( carry != 0 ) q += carry; } if ( carry != 0 ) push_back( carry ), carry = 0; return *this; } huge_unsigned& operator /= ( uint32_t j ) { register uint64_t p, q, x = j; for ( register size_t k = size(); k > 0; at( k ) = q, carry = p - q * x ) p = ( carry << 32 ) | at( --k ), q = p / x; while( size() > 0 && back() == 0 ) pop_back(); return *this; } void write() { for( register size_t k = size() - 1; k > 0; k-- ) printf( "%u ", at( k ) ); printf( "%u", at( 0 ) ); } }; struct binomial_coefficient: public huge_unsigned { binomial_coefficient( uint32_t n, uint32_t k ) { if ( k > n ) { push_back( 0 ); return; } register uint32_t p = n - k, q = min( k, p ); if ( q == 0 ) { push_back( 1 ); return; } push_back( n-- ); for( register uint32_t i = 2; i <= q; *this /= i++ ) *this *= n--; } }; int main() // A sample test program { uint32_t n, k; scanf( "%u %u", &n, &k ); clock_t start_time = clock(); binomial_coefficient c( n, k ); clock_t end_time = clock(); double elapsed_time = ( end_time - start_time ) * 1000.0 / CLOCKS_PER_SEC; printf( "Computed c( %u, %u ) = ", n, k ), c.write(), putchar( '\n' ), printf( "Using %u huge unsigned digits(s)\n", c.size() ), printf( "Elapsed time = %f msec.\n", elapsed_time ); }

Read more »

 
 
 
 
  • Vote: I like it
  • +3
  • Vote: I do not like it