Blog entries - Codeforces

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Mohammed-Shoaib's blog

Question: Rotated Digits

By Mohammed-Shoaib, history, 4 years ago, In English

I read the following question: LeetCode — 788. Rotated Digits. The same question is mentioned below.

Rotated Digits

X is a good number if after rotating each digit individually by 180 degrees, we get a valid number that is different from X. Each digit must be rotated — we cannot choose to leave it alone.

A number is valid if each digit remains a digit after rotation. 0, 1, and 8 rotate to themselves; 2 and 5 rotate to each other (on this case they are rotated in a different direction, in other words 2 or 5 gets mirrored); 6 and 9 rotate to each other, and the rest of the numbers do not rotate to any other number and become invalid.

Now given a positive number N, how many numbers X from 1 to N are good?

Example:

Input: 10
Output: 4
Explanation: 
There are four good numbers in the range [1, 10] : 2, 5, 6, 9.
Note that 1 and 10 are not good numbers, since they remain unchanged after rotating.

It's pretty easy to come up with a solution that works in O(N • log N) time:

int rotatedDigits(int N) {
	int cnt = 0;
	for (int i = 1; i <= N; i++)
		cnt += is_good(i);
	return cnt;
}

bool is_good(int num) {
	bool found = false;
	unordered_set<int> good = {2, 5, 6, 9};
	unordered_set<int> invalid = {3, 4, 7};
	
	while (num) {
		if (invalid.count(num % 10))
			return false;
		found |= good.count(num % 10);
		num /= 10;
	}
	
	return found;
}

But I am interested in knowing how to solve it faster, I think it can be done in O(log N) time. I believe you can do it faster using some Math, but it's hard for me to get the Math right.

Could someone please shed some light on how you could solve it faster? I have provided sample test cases at the end of this blog.

Thanks!

Sample Test Cases

Full text and comments »

Mohammed-Shoaib
4 years ago
1

Question: How do people generate test cases?

By Mohammed-Shoaib, history, 4 years ago, In English

I was working on a library called WhatsAlgo and needed 2 types of functionality:

generator: generates a bunch of test cases and creates one or more input files
validator: takes the solution file (could be in C++, Python, or other languages) and verifies it on each of the generated input files

This got me wondering, how do people generate test cases? I came across 2 popular platforms:

testlib by MikeMirzayanov
tokilib by fushar

Are these the platforms used by the testers on CodeForces?

What about other platforms like AtCoder, HackerRank, LeetCode, or even Google?

I'd appreciate it if someone shed some light on this as it would help me a lot. Thank you all for your help!

Full text and comments »

#testcase, #generator, #validator, #question

Mohammed-Shoaib
4 years ago
0

Question: Weird behaviour with max in C++

By Mohammed-Shoaib, history, 5 years ago, In English

I was trying out a problem (irrelevant) on LeetCode — 1372. Longest ZigZag Path in a Binary Tree. I posted this question on the forum but got no reply. Hence, I am asking the same question here.

I noticed some weird behaviour when using the max function. I took a max in two ways:

Solution 1: max(1 + a, 1 + b)

Solution 2: 1 + max(a, b)

Both of these do exactly the same task of getting the 1 + max. However:

Solution 1: — Runtime Error!
Solution 2: — Accepted

The full code is also given below:

Solution 1

class Solution {
public:
    int longestZigZag(TreeNode* root) {
        return zigzag(root)[2];
    }
    
    vector<int> zigzag(TreeNode* node) {
        if(!node)
            return {-1, -1, -1};
        vector<int> left, right;
        left = zigzag(node->left);
        right = zigzag(node->right);
        int h = max(max(1 + left[1], 1 + right[0]), max(left[2], right[2]));
        return {1 + left[1], 1 + right[0], h};
    }
};

Solution 2

class Solution {
public:
    int longestZigZag(TreeNode* root) {
        return zigzag(root)[2];
    }
    
    vector<int> zigzag(TreeNode* node) {
        if(!node)
            return {-1, -1, -1};
        vector<int> left, right;
        left = zigzag(node->left);
        right = zigzag(node->right);
        int h = max(1 + max(left[1], right[0]), max(left[2], right[2]));
        return {1 + left[1], 1 + right[0], h};
    }
};

The details for Solution 1 are given below:

Runtime Error Message: AddressSanitizer: stack-overflow on address 0x7ffee1685ab8 (pc 0x7f4840414c34 bp 0x7ffee1686300 sp 0x7ffee1685aa0 T0)
Failed Input

If you notice, the code for both of them is exactly the same except for line 13. Could someone please tell me why Solution 1 fails? It really makes no sense to me.

Thank you for all your help!

Full text and comments »

Mohammed-Shoaib
5 years ago
2

Question: Weird behaviour with deque in C++

By Mohammed-Shoaib, history, 5 years ago, In English

I was trying to solve the following problem (irrelevant): 1281C - Cut and Paste and I noticed something interesting. I inserted into the end of deque in two ways:

Solution 1:

n = d.size();
for (int k = 0; k < n; k++)
    d.push_back(d[k]);

Solution 2:

n = d.size();
d.insert(d.end(), d.begin(), d.begin() + n);

Both of these do exactly the same task of copying all the elements of the deque towards the end. However:

Solution 1 — Accepted
Solution 2 — Runtime Error!

Diagnostics for Solution 2

Diagnostics detected issues [cpp.g++17-drmemory]: ~~Dr.M~~ Dr. Memory version 1.11.0
~~Dr.M~~ Running "program.exe"

This application has requested the Runtime to terminate it in an unusual way.
Please contact the application's support team for more information.
C:/Programs/mingw-w64-7/lib/gcc/i686-w64-mingw32/7.3.0/include/c++/debug/deque:485:
Error: attempt to insert with an iterator range [__first, __last) from this 
container.

Objects involved in the operation:
    iterator "__first" @ 0x105BFE08 {
      type = __gnu_debug::_Safe_iterator<std::__cxx1998::_Deque_iterator<char, char&, char*>, std::__debug::deque<char, std::allocator<char> > > (mutable iterator);
      state = dereferenceable (start-of-sequence);
      references sequence with type 'std::__debug::deque<char, std::allocator<char> >' @ 0x105BFD6C
    }
    iterator "__last" @ 0x105BFDC8 {
      type = __gnu_debug::_Safe_iterator<std::__cxx1998::_Deque_iterator<char, char&, char*>, std::__debug::deque<char, std::allocator<char> > > (mutable iterator);
      state = past-the-end;
      references sequence with type 'std::__debug::deque<char, std::allocator<char> >' @ 0x105BFD6C
    }
    sequence "this" @ 0x105BFD6C {
      type = std::__debug::deque<char, std::allocator<char> >;
    }
~~Dr.M~~ 
~~Dr.M~~ Error #1: POSSIBLE LEAK 60 direct bytes 0x113500f8-0x11350134 + 0 indirect bytes
~~Dr.M~~ # 0 replace_malloc                    [d:\drmemory_package\common\alloc_replace.c:2576]
~~Dr.M~~ # 1 msvcrt.dll!strcpy_s              +0x5e     (0x7689f5d3 <msvcrt.dll+0xf5d3>)
~~Dr.M~~ # 2 msvcrt.dll!clearerr_s            +0x337    (0x768a9eed <msvcrt.dll+0x19eed>)
~~Dr.M~~ # 3 msvcrt.dll!clearerr_s            +0x27e    (0x768a9e34 <msvcrt.dll+0x19e34>)
~~Dr.M~~ # 4 pre_cpp_init
~~Dr.M~~ # 5 __tmainCRTStartup
~~Dr.M~~ # 6 KERNEL32.dll!BaseThreadInitThunk +0x11     (0x75d9343d <KERNEL32.dll+0x1343d>)
~~Dr.M~~ 
~~Dr.M~~ ERRORS FOUND:
~~Dr.M~~       0 unique,     0 total unaddressable access(es)
~~Dr.M~~       0 unique,     0 total uninitialized access(es)
~~Dr.M~~       0 unique,     0 total invalid heap argument(s)
~~Dr.M~~       0 unique,     0 total GDI usage error(s)
~~Dr.M~~       0 unique,     0 total handle leak(s)
~~Dr.M~~       0 unique,     0 total warning(s)
~~Dr.M~~       0 unique,     0 total,      0 byte(s) of leak(s)
~~Dr.M~~       1 unique,     1 total,     60 byte(s) of possible leak(s)
~~Dr.M~~ ERRORS IGNORED:
~~Dr.M~~       2 potential error(s) (suspected false positives)
~~Dr.M~~          (details: K:\invoker-prod\work\codeforces6\95dc81b8e4ab3564919231b09be345f6\check-9dfdf4cbd29474b4e0d899a6d68375b7\run\DrMemory-program.exe.3392.000\potential_errors.txt)
~~Dr.M~~      14 unique,    14 total,  24965 byte(s) of still-reachable allocation(s)
~~Dr.M~~          (re-run with "-show_reachable" for details)
~~Dr.M~~ Details: K:\invoker-prod\work\codeforces6\95dc81b8e4ab3564919231b09be345f6\check-9dfdf4cbd29474b4e0d899a6d68375b7\run\DrMemory-program.exe.3392.000\results.txt
~~Dr.M~~ Fetching 1 symbol files...
~~Dr.M~~ [1/1] Fetching symbols for C:\Windows\syswow64\msvcrt.dll
~~Dr.M~~ Fetched 1 symbol files successfully
~~Dr.M~~ WARNING: application exited with abnormal code 0x3

The code for both of them is exactly the same besides the above mentioned lines.

Could someone please tell me why Solution 2 fails? Is it because the time complexity of insert in deque is worse than push_back for all elements? Does this mean you should never use insert with deque?

Thank you for all your help.

Full text and comments »

#c++, #question, #deque, insert

Mohammed-Shoaib
5 years ago
3

Question: How much do function calls affect running time?

By Mohammed-Shoaib, 6 years ago, In English

I was trying to solve the following problem: 1106B - Lunar New Year and Food Ordering and I noticed something interesting. Below are two solutions:

Solution [1]

Submission Link: 49774574

Solution in plain text:

#include <bits/stdc++.h>

using namespace std;

typedef priority_queue< pair<int, int>, 
                        vector< pair<int, int> >, 
                        greater< pair<int, int> > > PQ;

int findCheapest(vector<int> a, PQ &pq) {
    while (!pq.empty() && a[pq.top().second] == 0)
        pq.pop();
    return (pq.empty()) ? 0 : pq.top().second;
}

void foodOrdering(int n, int m, vector<int> &a, vector<int> c) {
    int t, d, pos;
    long long cost;
    PQ pq;

    for (int i = 1; i <= n; i++)
        pq.push(make_pair(c[i], i));
    
    for (int i = 1; i <= m; i++) {
        scanf("%d %d", &t, &d);
        if (d <= a[t]) {
            a[t] -= d;
            cost = (long long) d * c[t];
            printf("%lld\n", cost);
        } else {
            d -= a[t];
            cost = (long long) a[t] * c[t];
            a[t] = 0;
            pos = findCheapest(a, pq);
            while (pos != 0 && d != 0) {
                if (d <= a[pos]) {
                    a[pos] -= d;
                    cost += (long long) d * c[pos];
                    d = 0;
                    printf("%lld\n", cost);
                } else {
                    d -= a[pos];
                    cost += (long long) a[pos] * c[pos];
                    a[pos] = 0;
                    pos = findCheapest(a, pq);
                }
            }
            if (d != 0)
                puts("0");
        }
    }
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    
    vector<int> a(n + 1), c(n + 1);
    vector<long long> cost;
    
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++)
        scanf("%d", &c[i]);
    
    foodOrdering(n, m, a, c);
    return 0;
}

Solution [2]

Submission Link: 49774627

Solution in plain text:

#include <bits/stdc++.h>

using namespace std;

typedef priority_queue< pair<int, int>, 
                        vector< pair<int, int> >, 
                        greater< pair<int, int> > > PQ;

int findCheapest(vector<int> a, PQ &pq) {
    while (!pq.empty() && a[pq.top().second] == 0)
        pq.pop();
    return (pq.empty()) ? 0 : pq.top().second;
}

void foodOrdering(int n, int m, vector<int> &a, vector<int> c) {
    int t, d, pos;
    long long cost;
    PQ pq;

    for (int i = 1; i <= n; i++)
        pq.push(make_pair(c[i], i));
    
    for (int i = 1; i <= m; i++) {
        scanf("%d %d", &t, &d);
        if (d <= a[t]) {
            a[t] -= d;
            cost = (long long) d * c[t];
            printf("%lld\n", cost);
        } else {
            d -= a[t];
            cost = (long long) a[t] * c[t];
            a[t] = 0;
            while (!pq.empty() && a[pq.top().second] == 0)
                pq.pop();
            pos = (pq.empty()) ? 0 : pq.top().second;
            while (pos != 0 && d != 0) {
                if (d <= a[pos]) {
                    a[pos] -= d;
                    cost += (long long) d * c[pos];
                    d = 0;
                    printf("%lld\n", cost);
                } else {
                    d -= a[pos];
                    cost += (long long) a[pos] * c[pos];
                    a[pos] = 0;
                    while (!pq.empty() && a[pq.top().second] == 0)
                        pq.pop();
                    pos = (pq.empty()) ? 0 : pq.top().second;
                }
            }
            if (d != 0)
                puts("0");
        }
    }
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    
    vector<int> a(n + 1), c(n + 1);
    vector<long long> cost;
    
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++)
        scanf("%d", &c[i]);
    
    foodOrdering(n, m, a, c);
    return 0;
}

Both the solutions are pretty much the same except Solution [1] uses a function call findCheapest and Solution [2] has the raw code replacing the function call. However, Solution [1] causes a TLE on test 9 taking 2000 ms whereas Solution [2] gets accepted and takes 140 ms. This means Solution [2] is atleast 14× faster than Solution [1].

At first I thought the priority_queue might be causing some issues. But I am passing the address as you can see, so the function should be modifying the same location.

I always thought function calls do not affect the running time much. Does this mean function calls play a big role in the running time? Could someone explain to me why this could have happened?

P.S. I am pretty much a noob so please feel free to correct anything and sorry for any stupid mistakes.

Full text and comments »

#c++, #question, #function calls, #running time

Mohammed-Shoaib
6 years ago
2