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.com/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.com/contest/653/submission/16811842

http://codeforces.com/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.com/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?