McDic's blog

By McDic, 13 months ago, In English

Hello.

After getting prize on ICPC 2020 Seoul Regional and writing Round #633, I almost stopped solving CP problems and entered quant industry. Now I have no job so I am not busy until I get next job, so I often describe my thoughts on online websites. This article is one of those. In this post, I am going to write about some common CP code practices which I think would be better changed. Before enumerating practices, I want to specify that this post is mostly focused to:

  1. Who wants to get dev jobs
  2. Who wants to create their practices from CP to productions without switching code style too much (i.e. Not having too different mindset for coding styles in CP and real applications)

If you just don't care, it's ok. I am not saying writing CP-style codes is bad, unless you believe you can use same practices on productions. Now let's dive in.

using namespace std;

What happens if you include big header files like bits/stdc++.h and do this? Bunch of functions, classes, constant variables will be loaded to the global namespace.

using_namespace_std

You never do this in production. How about CP? Does it boost runtime performance that makes you get AC without writing optimized algorithms? The only benefit of this code is you can access specific function or classes in std namespace with slightly less typing. You cannot define the variable or function with same signature, and there are way too many pre-defined signatures(and probably macros, but I don't know much) in std namespace. If you really want to make a shortcut for some frequently accessed types or functions, just use typedef or make a function pointer for that.

Abusing macros

Let's consider following code contains some macros;

#include <utility>

#define f1 first
#define f2 second

#define N 100005

int main(void)
{
    std::pair<int, double> x;
    auto x1 = x.f1;
    auto x2 = x.f2;
    int array[N];
    return 0;
}

There are two points. The first one is I don't really understand why shorthand for methods like first is needed. Nowadays many modern IDEs provide good intellisense that helps you to auto-complete the methods, types, variables, macros, and more. The second one is it's just better to use constexpr var_type var_name = var_value; for constants. The biggest reason for two points is, macro is basically a inplace string(code) conversion that happens before main compliation process. For more information about pre-processing, please refer here. Because of how macro works, sometimes the unexpected bug will happen by misuse of macros. I've even seen stupid macros like #define int long long, which overrides the primitive type name. Following code is the minimal example;

#include <iostream>

#define triple(x) x * 3

int main(void)
{
    std::cout << triple(5 + 1) << std::endl;
}

Above code outputs $$$8$$$ ($$$5 + 1 \times 3 = 8$$$), not $$$18$$$. But what if you still wants to make your own shortcut or constant variables? I suggest following examples using pointers to members and constexpr (Refer here for Microsoft tutorial about pointer to members and constexpr);

#include <utility>

constexpr int N = 100005;
const auto f1 = &std::pair<int, double>::first;
const auto f2 = &std::pair<int, double>::second;

int main(void)
{
    std::pair<int, double> x;
    auto x1 = x.*f1;
    auto x2 = x.*f2;
    int array[N];
    return 0;
}

Especially constexpr is very powerful, that directs your compiler to do "compile-time calculation" for possible cases.

constexpr_fib

Using library internal functions or compiler-specific extension features

Since gcc is one of the mostly used C++ compilers in many CP platforms, you can easily see the code using features that only works under gcc. Example builtins here. Of course, even in productions, sometimes you need exceptional performance so the company uses the same version of OS, languages, compilers and other 3rd party softwares. But if you depends on too specific version of external stuffs that is not guaranteed to work but subject to change, it's dangerous, because sometimes the software will yield different values on same codes, just by using different compilers(even just different minor versions). Some internal functions are guaranteed to work on specific major version, and maybe that's ok. But not all functions or macros are like that.

If I notice any more cases, will add here. Thanks for reading this, and happy coding.

Full text and comments »

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

By McDic, history, 5 years ago, In English

Hello! I hope all of you enjoyed my contest!

Tutorial is loading...

Behind story of A:

  • I tried to make the easiest Div2A ever. Will it work? :)
Tutorial is loading...

Behind story of B:

  • I tried to block various heuristics. There were some critical heuristics which could pass so many cases. Fortunately I blocked them during testing period, so I hope there won't be much FST this time.
Tutorial is loading...

Behind story of D2C/D1A:

  • Originally, there was a different problem for this position. But it used XOR. As I made new D2E/D1C problem, I threw old D2C/D1A away and put this.
Tutorial is loading...

Behind story of D2D/D1B:

  • This problem is the most popular problem among testers. I also like this problem a lot.
Tutorial is loading...

Behind story of D2E/D1C:

  • Feedback for this problem was too different by testers.
  • I made this problem by modifying Number Discovery, which is one of my previous problems.
  • If you OEIS this, then you may find you can use Nimber Arithmetic to solve this.
Tutorial is loading...

Behind story of D1D:

  • This problem was supposed to be D2E at first. But all LGM testers failed this problem during VC, so we thought that this problem's difficulty is high. Meanwhile, I found that old D1D problem can be easily googled, so we removed that problem, push this problem to be D1D, and made another D1C problem. I will share old D1D later.
Tutorial is loading...

Behind story of D1E:

  • Thanks tzuyu_chou for writing this problem. She is genius in both singing and problemsolving.

Full text and comments »

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

By McDic, history, 5 years ago, In English

내가 돌아왔다! (Hello, Codeforces!)

I am thrilled to introduce you to Codeforces Round #633. Followings are basic information:

  • This contest will take place on Apr/12/2020 17:05 (Moscow time).
  • The round is rated for all participants who can understand this announcement. There will be two divisions.
  • There are 5 problems in each division and you will have 2 hours to solve it.
  • Score distribution will be announced later.

Followings are contributors:

Followings are some fun things:

  • antontrygubO_o is the most intense coordinator I have ever met. He rejected lots of my problems. Some example of rejection comments are below:
    • This problem is too standard.
    • Don't ask people about theorem and formula.
    • This problem is appeared in recent ptz camp with higher constraints.
    • I don't like it.
    • Rock Scissor Paper makes statement messy, because some people don't know about it.
    • D2A should be easier than this one.
    • I've found generalized version of this problem in POI.
    • Isn't this obvious?
    • Your proof is wrong.
    • This problem is not very interesting.
    • This is too (censored).
  • After lots of rejections, I tried my best to make problems to be interesting. I hope you like at least some of my problems.
  • This round was originally supposed to be rated for Div.2 only. However, after we completed Phase 1 testing, we found that my round is too hard for Div.2, so we added more problems and made this round to be Div.1.
  • In this round, statements will be even shorter than last contest.
  • Even for some of problems which my coordinator approved, there were critical issues that made problems to be excluded. I will introduce some of my rejected problems which won't be used anymore in another post, after this contest ends.

I hope everyone can enjoy my third contest. Thanks in advance!

Followings are updates:

  1. Score Distribution:
    • Div.1: 500 1000 1500 2000 2750
    • Div.2: 500 750 1250 1750 2250
  2. I am sorry for such Div2C/Div1A statement issue. We fixed that immediately after few minutes to the round, but we should have announced it.
  3. Editorial is posted: https://codeforces.net/blog/entry/75913
  4. I opened new mashup for excluded problems. These problems are originally approved by antontrygubO_o but excluded for some reasons.
    1. Binomial Determinant is old Div1D. We found this problem on google so we removed this.
    2. Divisible Xor is old Div1A. But since we made 3 xor problems, we removed this one.

Followings are winners:

<Div.1>

  1. tourist
  2. Radewoosh
  3. TLEwpdus
  4. ecnerwala
  5. gisp_zjz
  6. Maksim1744
  7. scott_wu
  8. Petr
  9. jiangly
  10. maroonrk

<Div.2>

  1. Nachia
  2. MyAngelBakapiano
  3. 0.142857
  4. kekekeke228
  5. LeierKing
  6. Ka_ng_Hyeon
  7. Anithas_love_for_tries
  8. confeito
  9. TOPCYBERFLOWER
  10. wattaihei

Full text and comments »

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

By McDic, history, 5 years ago, In English

Introduction

Hello. I would like to share some nice stuff, called Sherman-Morrison formula. If you know this formula, it's easier to understand how BFGS update works in convex optimization and machine learning. But in this topic, we will just simply focus on this formula and learn how to calculate inverse matrix of rank-$$$1$$$ updated invertible matrix faster.

The motivation of this post is that my problem using Sherman Morrison formula is rejected by multiple coordinators.

Definition

You have invertible $$$\mathbb{R}^{n \times n}$$$ matrix $$$A$$$, and $$$\mathbb{R}^{n}$$$ vectors $$$u$$$ and $$$v$$$. Then $$$ (A + uv^{T})^{-1} = A^{-1} - \frac{A^{-1}uv^{T}A^{-1}}{v^{T}A^{-1}u + 1}$$$. If $$$v^{T}A^{-1}u = -1$$$, then $$$A + uv^{T}$$$ is non-invertible.

Time complexity

You can calculate Sherman Morrison formula in $$$O(n^2)$$$, because $$$A^{-1}u$$$, $$$v^{T}A^{-1}$$$ are vector.

Normally you need $$$O(n^3)$$$ time complexity to calculate inverse matrix except for some special matrix(diagonal matrix etc). But, since you can calculate Sherman-Morrison formula in $$$O(n^2)$$$, if you find some matrix can be represented as rank-$$$1$$$ updated matrix of special matrix, you can calculate inverse of that matrix in $$$O(n^2)$$$.

Generalization

There is a generalization of this formula called Woodbury Matrix Identity.

Sample problem

This problem is that rejected problem.

You have matrix $$$A = \begin{bmatrix} 1 & 2 & \cdots & n \\ n+1 & n+2 & \cdots & 2n \\ \cdots & \cdots & \cdots & \cdots \\ n^{2}-n+1 & n^{2}-n+2 & \cdots & n^{2} \end{bmatrix} + diag(c_{1}, c_{2}, \ldots, c_{n})$$$.

In $$$i$$$-th query, you will select any row or column of $$$A$$$ and multiply this by $$$x_{i}$$$. Compute $$$A^{-1}$$$ if $$$A$$$ is invertible after each query.

Constraints: $$$2 \le n \le 200$$$, $$$1 \le q \le 200$$$, $$$0 \lt c_{i}$$$, $$$x_{i} \neq 0$$$.

Full text and comments »

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

By McDic, history, 5 years ago, In English

What the hell is going on?

img1

img2

Someone is making intended rating inflation with hundreds of alts.

Please ban those accounts, and make some policy to save rating atmosphere from abusers.

So far, I found at least 200 dummy accounts in today round's registrants list.

Full text and comments »

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

By McDic, history, 5 years ago, In English

Hello, I hope all of you enjoyed my contest!

Tutorial is loading...

[Behind story of A]

Tutorial is loading...

[Behind story of B]

Tutorial is loading...

[Behind story of C]

  • Initial version of C statement consists of tons of mathematical formula. CF team and testers requested me to reduce amount of mathematical formula.
  • This problem was added before a week to the round. If there was no such C, the balance would be bad.
  • Thanks for dorijanlendvaj , he improved test data for C a lot!
  • My code: https://codeforces.net/contest/1228/submission/61578856
Tutorial is loading...

[Behind story of D]

Tutorial is loading...

[Behind story of E]

Tutorial is loading...

[Behind story of F]

  • This problem was the hardest to prepare data. We considered more than 10 types of trees to block various kind of WA solutions.
  • I intended top-down error-toleration based case handling approach for this contest, but seems other approaches are also ok.
  • Also thanks for dorijanlendvaj here, he is real MVP tester.
  • My code: https://codeforces.net/contest/1228/submission/61578884

[Behind story of G (removed problem)]

  • Nobody(including red testers) solved this problem for a week. This problem is saved as spare problem for another Div.1 contest.
  • I love this beautiful problem than any other problems I ever made.

Thanks in advance!

Full text and comments »

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

By McDic, history, 5 years ago, In English

다시 만나서 반가워요, 코드포스! (Nice to see you again, Codeforces!)

I'm again happy to introduce you to Codeforces Round #589 (Div. 2). Please look at following information for details:

  • This contest will take place on Sep/29/2019 16:05 (Moscow time).
  • The round will be rated for all Division 2 participants.
  • There are 6 problems and you will have 2 hours to solve them. Score distribution will be announced later.

The listed handles below are contributors. Thank you for all who listed!

For this contest, I tried to improve following things:

  • Reasonable difficulty: At my last contest, less than 200 official participants managed to solve at least one of DEF. Especially, 1182D's problem difficulty rating is 2500 and 1182F's problem difficulty rating is 2900(no official solvers!). This is not good for Div.2 participants. In other words, my first contest was hell. So this time, I tried to make my second contest to have more reasonable difficulty than my first contest.
  • Stronger data: There were 300+ successful hacks and almost 2000 sysfails at 1182B. At this time, I splitted testing phase into early phase and late phase. I'm bit worried, but I believe data will be stronger than my last contest.
  • Compact statement: I remember many people complained about 1182C's super complex statement. I made very compact statements for this round. There is no problem with more than 10 lines of statement(except I/O section) in this contest.

I hope everyone can enjoy my second contest. Thanks in advance!

UPDATES:

  1. If you want to discuss problems in chat after contest ends, come https://discordapp.com/invite/algorithms and you can enjoy discussion.
  2. I have deleted my last problem(G) from this contest during testing period. I really wanted to include that beautiful problem in my contest, but nobody solved that problem for a week. That problem will be appeared in another Div.1 contest.
  3. Scoring distribution is 500(A)-1000(B)-1250(C)-1750(D)-2250(E)-2750(F).
  4. Editorial: https://codeforces.net/blog/entry/70162
  5. Congratulation for winners!

WINNERS (updated):

  1. PositionZero
  2. supy_2
  3. hitman623
  4. lzqaq
  5. cwise
  6. LittleBeetle
  7. Tsypkokokokoko
  8. i_love_gnar
  9. 8-_-8 (handle mentioning is not working on his handle)
  10. wdk1745

Full text and comments »

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

By McDic, history, 5 years ago, In English

Hello.

I am interested in making contest and I have bunch of problem proposals. My problems are classified as below:

  • Used for past(already approved) contests like Round 566
  • Used for future contest proposals
  • Excluded from contest proposals due to pivoting or something else
  • Abandoned

I want to make some problems to private, but for now I can make my contest proposals to private only. Please make some functions that users can make problem proposals to private again!

Thank you for reading this.

Full text and comments »

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

By McDic, history, 5 years ago, In English

Sorry for such difficulty balance. Here is the editorial.

Tutorial is loading...

Solution Code for A

Behind story of B: Original B was harder. None of 2100+ rated testers solved original B, so it got downgraded. Also there was more than 15 pretests before.

Tutorial is loading...
Solution Code for B

Behind story of C: C is created before few days to contest. If there was no current C, the contest would have hell balances.

Tutorial is loading...
Solution Code for C

Behind story of D: Honestly I predicted D as hell hard problem. But other high rated people said it's not that hard.

Tutorial is loading...
Solution Code for D

Behind story of E: I didn't expected such well-known problem. My solution for E is more complicated.

Tutorial is loading...
Solution Code for E

Behind story of F: This problem was located at D originally.

Tutorial is loading...
Solution Code for F

Full text and comments »

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

By McDic, history, 5 years ago, In English

안녕하세요, 코드포스! (Hello, Codeforces!)

I'm super happy to introduce you to Codeforces Round #566 (Div. 2), which will take place on Jun/11/2019 16:05 (Moscow time).

The round will be rated for all Division 2 participants, yet any Division 1 participants are welcome to join us out of competition.

You will be given 6 problems and 2 hours to solve them. Score distribution will be announced later.

The listed handles below are contributors. Thank you for all who listed!

This is my first Codeforces contest ever. I hope everyone who will join this contest enjoy. Thank you!

WINNERS:

  1. Castor
  2. thecodinglizard
  3. puyu_liao
  4. UoA_Kanade
  5. abandonedw1
  6. average_frog_enjoyer
  7. orz_liuwei
  8. emengdeath
  9. ashutosh450
  10. hyfzbtrs

UPDATES:

  1. Let me spread the meme from McDic Minecraft Telegram group — Ggungah.
  2. Score distribution is 500-750-1250-2000-2250-2750.
  3. Editorial is available.
  4. Congratulations for the winners!
  5. I am sorry for weak systests for B and F. Sorry again.

Full text and comments »

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

By McDic, 6 years ago, In English

Recently I made a problem that requires calculating 20~30 digits of precision. (Calculating high precision is not a main idea, it's just required to solve this problem easily. This approach can be avoided and solvable by only big integers, but it needs very unusual mathematical observation.)

One of my friends said this problem should not be opened for Competitive Programming participants. He said this problem is bad because this requires hard work to self-implement high precision data structures or use built-in structures are not in C++ like Python's decimal.Decimal or Java's java.math.BigDecimal.

Why this feature makes this problem bad as competitive programming problem? I can see many problems in Codeforces force users to use either fast languages like C++ or very weird usage of system calls like I/O operations. Also, some data structures like Red-Black tree are not built in some languages like Python 3. Why not for this case?

Can anyone explain? Thanks in advance.

I removed that problem from my current proposal list. If I succeed to deal with constraints to make avoid BigDecimal/BigInteger easily, I will add it. Other problems are not forcing you to use such data structures. Thank you for all feedbacks.

Full text and comments »

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

By McDic, history, 6 years ago, In English

Hello.

I am wondering why Codeforces uses separated problems for subtask instead of separated test cases. Polygon is already supporting to have multiple testsets to act similar as subtasks, also Checker from testlib.h supports _pc (Partially Correct), which is intended to give partial score. So I think there is no reason to make separated problems such like R542 Div1 A1. It will be better if Codeforces just give participants partial score instead. Anyone have opinion about it?

Thanks for reading this.

Full text and comments »

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

By McDic, history, 6 years ago, In English

Hello.

Just started to participate contests to fill 25 participation in codeforces, now I even created my github repository to store my implementation :)

The link is here: https://github.com/McDic/MyImplementations/

Just wanted to show public, you can freely see or criticize my code anytime.

<2019-08-23> Now I have following my own implementations:

  • Trie and Aho Corasick
  • Segment Tree and Lazy Propagation
  • Shortest path algorithms such as Dijkstra and Floyd Warshall
  • Disjoint Set Union
  • Eratosthenes Sieve (both and O(n))
  • Convex Hull (both Graham Scan and Monotone)
  • KMP and Polynomial String Hashing
  • Matrix (but no advanced operations yet)
  • LCA
  • and some other uncompleted stuffs

My further future implementation goal is:

  • Minimum Spanning Tree (I don't know why I don't have this in my repository. This is easier, I will implement this asap)
  • Heavy Light Decomposition (What the heck this is too hard to implement myself)
  • Fast prime decomposition and primality test (like Pollard Rho's, Miller-Rabin primality test)
  • Optimized Matrix stuffs (Gaussian elimination, Determinant, etc)
  • Big Integers and Fractions with basic arithmetic and comparison operators
  • Strongly Connected Components

Thank you for reading this.

Full text and comments »

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

By McDic, 6 years ago, In English

I don't even know if my message is reached to Codeforces coordinator correctly. If there is a spreadsheet or document(Google spreadsheet might be the good choice.) to show current Codeforces Round Proposal queue status, people can check if their message is arrived correctly and estimate their email's response time. I hope they will make it someday.

Added 1: It seems GlebsHP is offline for almost 2 months and I sent the proposal email to him. Are he still one of the contributors? If not which coordinator should I resend my proposal email?

Full text and comments »

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

By McDic, 6 years ago, In English

Hello. I am using Polygon to prepare problems.

This is my generator below:

#include <iostream>
#include "testlib.h"

long long int max2(long long int a, long long int b){
	return a>b ? a : b;
}

long long int ten(int x){
	long long int s=1;
	for(int i=0; i<x; i++) s *= 10;
	return s;
}

int main(int argc, char* argv[]){
	registerGen(argc, argv, 1);
	
	std::cout << rnd.next(1LL, atoll(argv[1])) << " ";
	std::cout << rnd.next(1LL, atoll(argv[2])) << " ";
	std::cout << rnd.next(1LL, atoll(argv[3])) << " ";
	std::cout << rnd.next(max2(1, atoll(argv[4])/10), max2(100, atoll(argv[4]))) << std::endl;
}

Is there any wrong thing? It always verdict FL in invocation and tests. Thank you for reading this.

EDIT 1 This is the log occurs when I try to generate inputs. ERROR: Unexpected verdict Can't prepare input file 'C:\Contesters\Work\invoker-prod\work\polygon2\34b2efc622c48530be13ce1989b01907\check-bc2d7412ca16433314f5a03914c1d409\run\input.fd0138e687.txt'.FAILED. Input:

Full text and comments »

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