Update 2019/01/02: The problemset is finally uploaded to CF Gym. If you didn't participated before, this is a great chance to practice on one of Petr's best problem candidates. I hope you enjoy the contest. Happy New Year!

Division 1 Link

Division 2 Link .

.

.

OpenCup GP of Korea (third edition) is scheduled at 2018/10/14 Sunday, 11:00 MSK.

Both Div1 / Div2 problemset will feature Korean problems.

Problemsetters: ainta alex9801 Cauchy_Function Konijntje jh05013 ko_osaga OnionPringles jo_on .o.

Enjoy!

Hello Codeforces!

In 2018/05/26 21:30 Korea Standard Time (UTC+9) we will hold an online mirror of 2018 KAIST RUN Spring Contest. This is an annual individual contest held by KAIST's algorithm club RUN.

Problems are available in English, and you should individually solve 11 problems in 5 hours. The problems will be prepared in Gym, so this contest is unrated. Grading rules are ICPC-style. There are no prizes in this contest, but if any top scorers come to KAIST, we will bring you to our favorite restaurants or pubs ( ͡° ͜ʖ ͡°)

This online mirror might not reflect the onsite contest fully, due to some technical limits. For example, the grading rules in main contests were IOI-style, every problems were 100 points with subtasks and we had no penalties, but we had some difficulties implementing it on CF environment :/

Problems were prepared by ko_osaga, Konijntje, alex9801, etaehyun4, platinant. alex9801's rating is 2399, so he hopes to be called as "semi-red", not orange.

Special thanks to Konijntje, who hoped to upload this contest to gym (and actually worked on it), and MikeMirzayanov, who is the maintainer of this great community and system!

In the online mirror for Korean participants (including some famous red/nutella coders), nobody was able to solve all problems — I challenge you to beat them! :D

The contest is now finished! Congratulation to winners!

1. sunset
2. Reyna
3. Bedge
4. gamegame
5. the_art_of_war

Local open contest scoreboard

Tests, checkers, solutions (warning, over 400MB!)

Editorial

Problemsetters :

• Konijntje : P (Puyo Puyo), Y (Yut Nori)
• ko_osaga : Q (QueryreuQ), T (Touch The Sky), U (United States of Eurasia), V (Voronoi Diagram), W (Winter Olympic Games), Z (Zigzag)
• alex9801 : X (Xtreme NP-Hard Problem?!)
• platinant : R (Recipe)
• etaehyun4 : S (Segmentation)

Thanks to everyone who participated!

Update 2018.11.01: Rezwan.Arefin01 made a very cool webapp which contains identical problemset, but with more usability. Thank you very much! You can check it here.

Note: There was some updates in 2018.10.05. See here for changes!

Hello! APIO 2018 is near the end, and IOI 2018 is in this September. I hope you are preparing it well!

I'm here to present my OI problem checklist :

I used this to train myself in IOI 2015~2016, and to train Korean IOI 2017 Team (probably 2018 too). For long it was in the "beta" phase, but I think it's now good enough to share!

This problemset contains about 300 ~ 400 hard and interesting problems, with appropriate judge links given. (If there is problem in judging, maybe ojuz can help that..)

Google Docs Link

I hope this can help anyone preparing for future OIs, and a complete answer to the question "How to excel at IOI-style contests" :D

Hello!

According to the official site, BOI 2018 will be held in this weekend. Good luck to all participants!

I wonder if the organizers are planning any online contests. I actually found this Kattis site, but I think this is for official participants. Any ideas?

WHERE IS IT?

Edit : Ok because of the delay we are unable to participate :/

No threads, so I decided to make it.

Let's discuss!

World Codesprint 11 was held in May. They promised us to "expect 6~8 weeks" for prizes, and 7 months are passed. And I talked about this two times.

It's worth noticing that Bitcoin prices has become 5x from then.

Will I ever be able to receive their moneys someday? I don't want to participate in a contest where organizers don't keep up their promises.

In a n x m chessboard with cells labeled (i, j) for 1 ≤ i ≤ N, 1 ≤ j ≤ M, there is a stone at (1, 1). A and B is playing a game.

A starts first, and they alternately move stone to adjacent cell (north / west / south / east). It's okay to move stones to previously visited cells, but it's prohibited to move stones to previously visited "edges". For example, if someone wants to move stone from (1, 1) -> (1, 2), they shouldn't have a record of visiting (1, 1) / (1, 2) or (1, 2) / (1, 1) cells consecutively. Player unable to make a move loses.

Who is the winner? 1 ≤ n, m ≤ 10⁶

About 1 month ago, me and other guys tried to solve this problem but failed. I also googled about this problem, but wasn't able to find any resources about it :/ Here are some observations to share.

Could anyone help me to solve this?

I never thought Kuhn-Munkres would strike me that hard...

How to solve F L? And what was intended for H?

Round : https://www.facebook.com/hackercup/scoreboard/1799632126966939/

Time : https://www.timeanddate.com/worldclock/fixedtime.html?msg=2017%20Facebook%20Hacker%20Cup%20Finals&iso=20170614T1330&p1=234&ah=4

List of Participants : http://codeforces.net/blog/entry/50089

(Note that actual participants slightly differ from that list)

I'm pretty flattered for my first ever onsite competition (beside IOI) :D Good luck and have fun!

I'm not a native English speaker, so I mostly learn English by books or internet. When I look up Collins English Dictionary about the meaning of "Editorial" :

"An editorial is an article in a newspaper which gives the opinion of the editor or owner on a topic or item of news."

That's something we call as "사설" in Korean. In Korea, people write editorial about our recent president impeachment, thoughts on foreign policies, or the Chinese food restaurant nearby their office. If someone uses that phrase to describe solutions, it will be really awkward.

In Codeforces, when we say "Editorial" it mostly means "Solution" — that is, mathematical facts. So, according to dictionary, this post is more likely to be called as "Editorial" than the usual one we know.

Then, why does CP community uses the word "Editorial" for referring solution? Does it have some other meaning related to "solution"? If not, is there some history for using that phrase?

Hello!

Recently I learned about FFT algorithm, and I was confused because of it's precision errors.

Suppose that I want to multiply two polynomials A(x) and B(x) modulo 10^9 + 7. (max degree <= 10^6) Then I have two options :

• use NTT with modulo 119 * 2^23 + 1. With these I don't have to worry about precision errors, but I have to split the coefficients in something like (c0 + c1 * 32 + c2 * 32^2 + c3 * 32^3 .... c5 * 32^5). This is the best we can use, since if we use something over 32, (33-1) * (33-1) * 1000000 > modulo. So I have to split it into at least 6 pieces, which is horrible..

• use FFT with complex numbers : Well... we don't have modulos, so I have to guess here. I've experimented with 10^6-digit long integers with all digits in 9. (basically I calculated (10 ** 1000000 — 1) ** 2) In first try, I grouped two digits together (coeff < 100), and it worked fine. In second try, I grouped three digits together(coeff < 1000) , which had precision errors. So I can guess that it will be okay to split under 100. Now 5 pieces. Which is... eh, improvement, but still horrible.

Regarding problem F in here or this (spoiler alert), It's clear that there is a demand for big modulos. However, grouping into something like 30 or 100 is not only dumb, but very slow and constant-heavy, and it should be avoided.

I concluded that NTT won't help me in this problem, and arrived in following questions :

1. How can we estimate the precision error of FFT? (or, is there some kind of rule of thumb in here?)
2. What is the common way to avoid this situation? Isn't there any other way than grouping with number lesser than sqrt(mod), or karatsuba?

FYI, this is the code used in my experiment : https://gist.github.com/koosaga/ca557138cabe9923bdaacfacd9810cb1

After IOI, I was sorting out some APIO 2016 certificates for my schoolmates. But, umm... "Siver" medalist?

You should check if those kind of typo also happens to you :D

http://www.spoj.com/problems/FAILURE/

Problem is simple : N points are given in Euclidean plane. For each points, you should find the smallest distance between itself and other points, in respect of euclidean distance.

I had no idea on the solution of this problem (except Delaunay triangulation. I hope there's a simpler solution), so I googled for the solution : https://github.com/anurag-jain/spoj-1/blob/master/MLE.cpp but I still have no idea why it's O(NlgN).

Can someone help me with this problem? T.T

When I’m using main.edu.pl for solving problems, I found that there is no time limits specified for each problem. For POI problems I tried to find the official problemset pdf files, but seems like they don’t provide any of them T.T

At first I thought that the TL was 1 second for all problems, but with that assumption, lot’s of problems can’t be solved. So, if the problem has diverse complexities (especially those involving sqrts), I have to “guess” the time limit, or submit any solutions that compiles :(

So, here’s my question : Is there any way to find the official time limit of main.edu.pl problem, without actually submitting to it? I would appreciate for any help on it :)

(slightly unrelated, but I think that main.edu.pl will be a really great judge if it supports c++11 :p)

These are the codes for problem E by RNS_JKS and blackEarth from last IndiaHacks contest.

http://codeforces.net/contest/653/submission/16811842

http://codeforces.net/contest/653/submission/16815024

You can easily discover the simillarities between those competitor's code. Actually, It's more hard to find the difference.

• Struct names are different — one has "xvalue", other has "dat". but operator definition / initializators are all same.
• Function names are different — one has "doit", other has "foo". but, inside the function, everything is same — even the indentations / spaces are same, too!
• Several brackets / indentations are different in main function, but others are identical.

Another interesting thing is the submission from RNS_JKS one minute before AC — http://codeforces.net/contest/653/submission/16814808 This code is very different from the AC code. Then, how are these changes made in such a short time?

In usual competition, I don't go deeper to other's codes. But, when I discovered that my rating was right before IGM (2599), and reminded how I got red from 2199, I was really tempted to write this post! MikeMirzayanov, can you investigate into those issues?

I got a nice problem from Korean OI : https://www.acmicpc.net/problem/2300 .

Since deriving recurrence is not the point of this topic, I will give you the formula :

• N <= 10000

• 0 <= Xi <= X(i+1) <= 10^9, (1 <= i < N), 0 <= Yi <= 10^9 (1 <= i <= N)

• DP[i] = Min(DP[j] + Cost(j+1, i))for all j < i. when Cost(s, e) = Max(X[e] — X[s], Max(Y[s], Y[s+1] ... Y[e]))

The goal is to calculate DP[N] — and O(N^2) solution is quite straightforward.

However, I heard that there is a subquardatic solution to this problem! I tried various strategies to solve it, but failed.

Does anyone have a hint / idea to the subquadratic solution?

JOI 2016 online contest will be held at 2016/02/14 09:30 JST(+UTC 09:00)

http://cms.ioi-jp.org/joi-ho-2016/index.html

It is an OI-style competition with full feedback. There will be 5 problems for 4 hours, sorted in difficuity order.

The problems are in Japanese — If you can't speak Japanese (like me), you should use translator.

In my opinion, the problem's difficulty will be comparable to that of COCI. (maybe bit harder?) These are the problemsets from the past 3 years.

http://www.ioi-jp.org/joi/2012/2013-ho/2013-ho.pdf

http://www.ioi-jp.org/joi/2013/2014-ho/2014-ho.pdf

http://www.ioi-jp.org/joi/2014/2015-ho/2015-ho.pdf

The traditional implementation of union find tree (aka disjoint set) utilizes rank compression — this is the code with it.

int parent[1000], rank[1000];

int find(int x){
    return parent[x] = (parent[x] == x ? x : find(parent[x]));
}

void Union(int p, int q){
    p = find(p);
    q = find(q);
    if(rank[p] < rank[q]) parent[p] = q;
    else parent[q] = p;
    if(rank[p] == rank[q]) rank[p]++;
}

But in competitive programming, I found out that the rank compression was useless. Without rank compression, the code was shorter, and even the program ran faster. This is my implementation without rank compression.

int parent[1000];

void Union(int p, int q){ parent[find(p)] = find(q); }

and for some cases, I found implementing rank compression is quite hard (maybe impossible).

I will give you a sample problem : "Given a tree T, you should process Q queries — "paint the edge's value into x (>0) from path s to e".

I reversed the query, broke down the path s — e to s — LCA(s,e) — e, and used this algorithm to paint the tree. (root_val[s] : value of edge s — parent(s), dep[s] = depth of s. nxt[s] = parent(s))

int paint(int s, int e, int x){  
    if(dep[s] <= dep[e]) return s;  
    if(!root_val[s]) root_val[s] = x;  
    return nxt[s] = paint(nxt[s],e,x);  
}

All of those program ran very fast in practice, but I was curious about the worst-case runtime of such path compression without ranks, so I googled for a while but didn't find any answer. Here's my question:

1. Does the path compression runs in (amortized) sublinear time per query?
2. If it doesn't, is there any counterexamples for that?

I recently encountered this problem (from Balkan OI 2012)

https://www.acmicpc.net/problem/5250

..and I have absolutely no idea except the naive algorithm of O(nmlgm).

Any hints or solution for this problem? Is this problem utilizes some data structures that is less known?