When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

never_giveup's blog

By never_giveup, history, 8 months ago, In English

Our team of isaf27, Maksim1744 and me had prepared a contest for Petrozavodsk camp some time ago.

Contest link

We hoped to use this contest for some open competition, like opencup or universal cup, but it seems like it already became well known in China.

The difficulty of the contest is higher than average, and we hope that strong teams like USA1 and japan02 can enjoy it too (if they have spare time).

We thank

  • pinely for supporting our efforts
  • snarknews for his help in growing and improving ICPC community
  • universal cup team for continuing these efforts
  • MikeMirzayanov for an opportunity for self improvement for many people, by providing great platforms Codeforces and Polygon

Full text and comments »

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

By never_giveup, history, 2 years ago, In English

I'm trying to find some article or at least a name of some type of bipartite graph, description follows.

  • Left part contains exactly $$$n$$$ nodes, numbered $$$1$$$ through $$$n$$$.

  • Right part contains $$$m$$$ nodes, each node is associated with a segment $$$[l; r]$$$, where $$$1 \le l \le r \le n$$$.

  • There is an edge $$$(i, j)$$$ iff $$$l_j \le i \le r_j$$$.

It seems natural to call such graph as a bipartite line graph, but there is another (apparently more popular) graph called line graph, which has nothing to do with mine.

One thing to mention is that this graph is considered by me in terms of flows, so probably it is considered in such context in science too.

If someone knows it's name, or even saw an article mentioning it, I would be very grateful to that person for sharing this information!

Full text and comments »

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

By never_giveup, history, 3 years ago, translation, In English

I'm unable to find any resources(with some proofs) on how to find certificate for lambda(a.k.a. Lagrange) dp optimization for non-strict convex functions. Any help is highly appreciated!

Full text and comments »

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

By never_giveup, history, 6 years ago, In English

Hello, I was solving golf from JOI 2017 Open. I tested in polygon with author's solution. My solution got WA, then I decided to change C++17 to C++14 and magically I've got AC. Can someone tell me how is that possible. Also I submitted it to oj.uz where compiler is under Ubuntu and it also gives wrong answer code test

Full text and comments »

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

By never_giveup, 6 years ago, translation, In English

You are given 4 integer arrays A, P and B, Q of size N and M queries. Initially, elements of A and B are 0, and elements of P and Q are sorted in non-decreasing order and have constraints 0 ≤ x ≤ 109.

There are 3 types of queries:

  • 0 ≤ x ≤ 109; 1 ≤ i ≤ N; Ai = x
  • 0 ≤ x ≤ 109; 1 ≤ i ≤ N; Bi = x
  • 0 ≤ x ≤ 109; 1 ≤ y ≤ 1018; Find minimum i, such that

There is an easy solution with time complexity O(Nlog2N): store A and B in BIT, when you need to answer query, binary search by i, and check whether condition holds true. I'm looking for solution with time complexity O(NlogN). Any ideas about that?

Full text and comments »

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

By never_giveup, 7 years ago, In English

Hello Codeforces!

I’d like you to invite for CodeChef June Lunchtime that will start at 19:30 IST of 24-th June 2017 (check your time zone here) and will last 3 hours.

The author of problems is me, never_giveup, while Lewin is a tester and mareksom is the secondary Tester. The editorialist is pkacprzak. Translators: CherryTree (Russian), huzecong (Mandarin) and VNOI team (Vietnamese).

There is no registration required, anybody with a CodeChef handle can participate. Top school participants can win CodeChef laddus (details on the contest page).

You will be provided 4 problems with subtasks (IOI-style grading). Ties are broken by time of reaching your final score.

Remember about subtasks if you can't solve a problem for the full score, and read the editorial after the contest.

Full text and comments »

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