Madiyar's blog

By Madiyar, history, 4 years ago, In English,

Small brainteaser. Do you know that function below doesn't work in some cases.
Try to attack it.

#include <iostream>

using namespace std;

void swap(int &a, int &b){ 
	a = a + b; 
	b = a - b; 
	a = a - b;
}

Read more »

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

By Madiyar, 5 years ago, In English,

Hope this will helpful for someone.

Never repeat my mistake. Never start name of global variable with an underscore.

For example Accepted code in Codechef.

The same code gives Runtime error with addition:#define where _end, i.e by renaming where variable to _end.

Again, the same code gives Wrong Answer with addition: #define size _end, i.e by renaming another variable "size" to _end.

In my point of view, variables beginning with an underscore are reserved in the global namespaces.

Can somebody better explain what is happening here? I tried in some problems in Codeforces, but couldn't trigger it.

Read more »

Tags c++
 
 
 
 
  • Vote: I like it
  • +43
  • Vote: I do not like it

By Madiyar, 5 years ago, In English,

My another blog hopefully will help to prevent from bugs.

Try to guess the output without using compiler or IDE. Please hide your answers to not spoil.

1.

#include <iostream>
using namespace std;

int main() {
    int a = 020;
    short b = 2;
    cout << a - b << endl;
    return 0;
}

2.

#include <iostream>
using namespace std;

int main() {
    bool ok = true;
    // Try to guess with if condition  \
    if (!ok && true) 
        cout << "I am ok" << endl;
    return 0;
}

3.

#include <iostream>
using namespace std;

int main() {
    unsigned a = 0;
    int b = 2;
    if (a + b >= -2) 
        cout << a + b << ">=" << -2 << endl;
    else
        cout << a + b << "<" << -2 << endl;
    return 0;
}

4.

#include <iostream>
using namespace std;

int main() {
    int  a = 0, b = 1;
    if (a&b==0) {
        cout << (a&b) << "=" << 0 << endl;
    } else {
        cout << (a&b) << "!=" << 0 << endl;
    }
    return 0;
}

Read more »

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

By Madiyar, 5 years ago, In English,

I use python a lot. So, by accidentally I can type this code and compiler won't give me a error:

#include <iostream>
using namespace std;

int main() {
	cout << (1 <= 2 <= 1);
}

In python, and some other languages, the expression a <= b <= c is equivalent to a <= b and b <= c. But in c++, this code produces 1 (true).

Why it compiles successfully? And why it prints 1?

Hope this blog will prevent someone from possible future mistakes.

Read more »

Tags c++
 
 
 
 
  • Vote: I like it
  • +73
  • Vote: I do not like it

By Madiyar, 5 years ago, In English,

Single Round Match 630 will be held at 05:00 Fri Moscow time.

Let's discuss here problems after the contest.

Read more »

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

By Madiyar, 5 years ago, In English,

I hope this post will be helpful for someone :).

I use a lot standard c++ gcd function (__gcd(x, y)).
But today, I learnt that on some compiler __gcd(0, 0) gives exception. (Maybe because 0 is divisible by any number?! )

Note for myself and everybody: While using __gcd we must carefully handle (0, 0) case or write own gcd.

upd: AlexDmitriev noted below that we must be careful also with case __gcd(x, 0).

Read more »

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

By Madiyar, 5 years ago, In English,

Hello

I am trying to solve this problem from hackerrank.

In short, there is a tournament graph, which is directed complete graph, i.e for every (u, v), where u < v there is an edge either from u to v, or from v to u.
We know scores of each player (i.e out degrees of each vertex), but some scores might be erased. Instead of erased scores we can put any scores, so that for these scores should exist a tournament graph. How many possible variants exists?

My thoughts (which can help to solve this problem):

To check (s[1], s[2], .., s[n]) sequence is out degrees of tournament graph, must hold:

if we sort sequence, so that s[1] <= s[2] <= .. <= s[n]

1.

2., for every k = 1 .. n-1

I though to solve this problem using dynamic problem and these properties, but it is wrong.

So How to solve this problem?

upd: Solved

Read more »

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

By Madiyar, 5 years ago, In English,

While solving Andrew Stankevich Contest 32, Problem K, I noticed that __builtin_popcount for long long doesn't work properly, I spent a lot of time to find my mistake, but when I wrote __builtin_popcount by myself it accepted.

__builtin_popcount defined only for int?

Read more »

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

By Madiyar, 5 years ago, translation, In English,

In my Facebook page I noticed e-maxx.ru in advertisement section,

e-maxx

Who else have e-maxx in advertisement section?

Read more »

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

By Madiyar, 6 years ago, translation, In English,

Hello

I solved this task, but I have a question.

First of all I submitted this code

TL : 0.04 Memory : 1672

Then I resubmitted this code but without #include <iostream>

TL: 0.04 but Memory : 1088

Question: For what spends memory in iostream?

Read more »

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

By Madiyar, 8 years ago, translation, In English,

http://acm.sgu.ru/problem.php?contest=0&problem=206


please , Help to solve this task

I reduced this task to linear programming, and linear programming to dual 

w[j] >= w[i] (where  j = n .. m  and i = 1 .. n-1 ) this is the least condition for minimality

and We must find x[i] (where i = 1..m) ,such that x[1] + x[2] + .. + x[m] is minimal

and conditions  are: 
w[j]+x[j] >= w[i] - x[i]

This equation is linear programming,  and dual form of this equation is the optimal match problem

so we can find sum of x[1]+x[2]+...+x[m], and how to find x[i] ?


 

Read more »

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