Perhaps today and/or tomorrow due to a power outage there may be disruptions in the work of Codeforces and Polygon. Please do not plan any important events during this time. If there are details or the exact time, we will definitely publish them. Estimated time of maintenance: from 2 Aug, 16:00 (UTC) to 2 Aug, 20:00 (UTC). ×

 
 
 
 

You can use several words in query to find by all of them at the same time. In addition, if you are lucky search understands word forms and some synonyms. It supports search by title and author. Examples:

  • 305 — search for 305, most probably it will find blogs about the Round 305
  • andrew stankevich contests — search for words "andrew", "stankevich" and "contests" at the same time
  • user:mikemirzayanov title:testlib — search containing "testlib" in title by MikeMirzayanov
  • "vk cup" — use quotes to find phrase as is
  • title:educational — search in title

Results

 
 
 
 
1.

optimization

Last visit:  5 years ago
Registered:  5 years ago
 
 
 
 
2.
By parveen1981, history, 2 months ago, In English
I compiled a list of almost all useful blogs ever published on Codeforces [update: till 09.06.2021] <h3 style="color:red">If there are any blogs that I have missed, please tell in the comment section. Thank you.</h3> # Mathematics Stuff - [Number Theory in Competitive Programming [Tutorial]](https://codeforces.com/blog/entry/46620) - [Number of points on Convex hull with lattice points](https://codeforces.com/blog/entry/62183) - [FFT, big modulos, precision errors.](https://codeforces.com/blog/entry/48465) - [Number of ways between two vertices](https://codeforces.com/blog/entry/19078) - [Mathematics For Competitive Programming](https://codeforces.com/blog/entry/76938) - [FFT and NTT](https://codeforces.com/blog/entry/19862) - [Burnside Lemma](https://codeforces.com/blog/entry/51272) - [Number of positive integral solutions of equation 1/x+1/y=1/n!](https://codeforces.com/blog/entry/76836) - [On burnside (again)](https://codeforces.com/blog/entry/64860) - [Simple but often unknown theorems/lemmas/formula? Do you know?](https://codeforces.com/blog/entry/55912) - [Probabili...

Read more »

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

 
 
 
 
3.
By indy256, 8 years ago, In English
Dynamic Programming Optimizations Several recent problems on Codeforces concerned dynamic programming optimization techniques. The following table summarizes methods known to me. <table> <tr> <th>Name</th> <th>Original Recurrence</th> <th>Sufficient Condition of Applicability</th> <th>Original Complexity</th> <th>Optimized Complexity</th> <th>Links</th> </tr> <tr> <td><small>Convex Hull Optimization1</small></td> <td nowrap><small>$dp[i] = min_{j<i}\{dp[j]+b[j] \star a[i]\}$</small></td> <td nowrap>$b[j] \geq b[j+1]$<br/><small><s>optionally</s>&nbsp;$a[i] \leq a[i+1]$</small></td> <td nowrap>$O(n^2)$</td> <td nowrap>$O(n)$</td> <td nowrap><small>[1](https://web.archive.org/web/20181030143808/http://wcipeg.com/wiki/Convex_hull_trick) [2](https://cp-algorithms.com/geometry/convex_hull_trick.html) [3](https://codeforces.com/blog/entry/63823)<br/>[p1](/contest/319/problem/C)</small></td> </tr> <tr> <td><small>Convex Hull Optimization2</small></td> <td nowrap><small>$dp[i][j] = min_{k<j}{dp[i-1][k]+b...
. - It looks like **Convex Hull Optimization2** is a special case of **Divide and ConquerOptimization, 1. Are there any other optimization techniques? 2. What, >Divide and Conquer Optimization $dp[i][j] = min_{k, Several recent problems on Codeforces concerned dynamic programming optimization techniques

Read more »

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

 
 
 
 
4.
By ATSTNG, history, 23 months ago, In English
[Tutorial] Matroid intersection in simple words **[This article is also available in [Russian](https://codeforces.com/blog/entry/69287?locale=ru)]** Hello, CodeForces. I think that matroids are beautiful and powerful concept, however, not really well known in competitive programming. I’ve discovered matroids at 2019 Petrozavodsk Winter Training Camp. There was a problem that clearly cannot be solved using usual techniques I knew, editorial for this problem was just these three words “just matroid intersection”. Back then it took me more than 2 days of upsolving to find all the information and details I need and implement solution that gets Accepted on this. And it took way longer to actually understand why does it work and exactly how does it work. (I still hesitate in some details.) Of course, it is not hard to google up all the definitions and some related articles, but in my opinion they all are focused more on mathematical part of theory, strict proofs in some not really obvious but short ways, and observing only ke...
intersection, also it’s running time and Cunningham optimization. Includes additional information, space is $\mathbb{Z}_2^m$ we can apply bitset optimization achieving $\mathcal{O}(\frac{r^2 \cdot m, But algorithm-specific oracles is not the only possible optimization here., Turns out this optimization actually improves complexity. In total we need $\mathcal{O}(\sqrt{r

Read more »

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

 
 
 
 
5.
By khatribiru, history, 5 years ago, In English
Dynamic Programming Optimizations ( Problems ) This Blog is Just the List of Problems for Dynamic Programming Optimizations.Before start read [This](http://codeforces.com/blog/entry/8219) blog. #### **1.Knuth Optimization** Read [This](https://www.quora.com/What-is-Knuths-optimization-in-dynamic-programming) article before solving Knuth optimization problems. [Problem 1](https://uva.onlinejudge.org/external/100/10003.pdf) [Problem 2](https://uva.onlinejudge.org/external/103/10304.pdf) [Problem 3](http://codeforces.com/gym/100212/attachments/download/1727/20042005-winter-petrozavodsk-camp-andrew-stankevich-contest-10-en.pdf) ( **C** ) [Problem 4](http://www.spoj.com/problems/BRKSTRNG/) [Problem 5](https://uva.onlinejudge.org/external/120/12057.pdf) [Problem 6](https://uva.onlinejudge.org/external/128/12836.pdf) #### **2. Divide and Conquer Optimization** Read [This](https://www.quora.com/What-is-divide-and-conquer-optimization-in-dynamic-programming) article before solving Divide and Conquer Optimization problems...
[This](http://codeforces.com/blog/entry/8219) blog. #### **1.Knuth Optimization ** Read, #### **1.Knuth Optimization**, #### **2. Divide and Conquer Optimization**, **Note:-** Some problems from Divide and conquer optimization section can also be solved using CHT., Read [This](https://www.quora.com/What-is-Knuths-optimization -in-dynamic-programming) article, Read [This](https://www.quora.com/What-is-divide-and-conquer-optimization -in-dynamic-programming

Read more »

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

 
 
 
 
6.
By bukefala, history, 4 years ago, In English
Top 10 optimizations 2017- (collectors edition) Hello friends. The year is almost over so I have prepared the top 10 optimizations of 2017 for your viewing pleasure. Without forthor ado, let us begin. 1. OPTIMIZATION OF FLOYD VARŠAL ALGORITHM TO RUN IN N^2: simply instead of going from 1 to N in third loop we willuse bitset which will visit the remaining nodes automatically 2. SEGMENT TREE OPTIMIZATION TO RUN IN O(NlogMlogQ) complexity. We will simply use bitset to fetch our data between nodes instead of every time having to calculate hashes in nodes all over again. 3. OPTIMIZATION OF FENWICK TO ACCEPT QUERIES OF TYPE: EXPAND INTERVAL BY CONSTANT C We will simply use bitset which will store every expansion in every possible moment in time. You will say this is obviously too slow. But it can be easily optimized. We will simply make another bitset map for these changes. 4. USING LCA AS A TOOL TO OPTIMIZE TRIE You maybe thinking that LCA has nothing to do with trie. but-witg SIMPLE usage of little thing called bitset...
viewing pleasure. Without forthor ado, let us begin. 1. OPTIMIZATION OF FLOYD VARŠAL ALGORITHM, 1. OPTIMIZATION OF FLOYD VARŠAL ALGORITHM TO RUN IN N^2: simply instead of going from 1 to N, 10. REVOLUTIONARY OPTIMIZATION OF BLOCK CHAIN The circular implementation of a new hashing, 2. SEGMENT TREE OPTIMIZATION TO RUN IN O(NlogMlogQ) complexity. We will simply use bitset to fetch, 3. OPTIMIZATION OF FENWICK TO ACCEPT QUERIES OF TYPE: EXPAND INTERVAL BY CONSTANT C We will simply, 8. CONCAVE HULL TRICK Ok. You ssy concave hull can not be used for quad tree optimization trick

Read more »

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

 
 
 
 
7.
By grhkm, history, 10 months ago, In English
[TUTORIAL] Basic Lagrange Interpolation Lagrange Interpolation by grhkm ===================================================================== No polynomial stuff because I don't know $O(n\log{n})$ polynomial multiplication :( Main results: ------------- Given $f(x_1)=y_1, f(x_2)=y_2, ..., f(x_n)=y_n$ we can calculate $f(X)$ where $f$ is the unique $(n-1)$-degree polynomial For general {$x_i$} we can do so in $O(n^2)$ For consecutive {$x_i$} i.e. $x_j=x_1+(j-1)$, we can do so in $O(n)$ excluding binary exponentiation Why useful? ------------------- Calculate $1^n+2^n+...+X^n$ in $O(n)$ DP optimization With polynomials you can do cool things but not gonna cover this blog Let's get started :) Assume all polynomials below are $(n-1)$ degree unless specified. <spoiler summary="disclaimer"> Sorry if it's a bit messy, this is my first time writing blog lol please give feedback~ </spoiler> <spoiler summary="Why (n-1) degree?"> We can write polynomial as $c_0+c_1x+c_2x^2+\cdots +c_kx^k$ wher...
DP optimization, Optimization: -------------------

Read more »

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

 
 
 
 
8.
By wrg0ababd, history, 3 years ago, In English
New powerful optimization technique In this blog I will tell you about recently invented powerful optimization technique, which can be applied to almost any problem and lets you solve it easily. Further I assume that you're already familiar with finding maximum flow in networks. If not, there're many tutorials avaible on Internet. For example, you can read [this](https://www.topcoder.com/community/data-science/data-science-tutorials/maximum-flow-section-1/) fabulous article on Topcoder. It's based on [Goldberg-Rao algorithm](http://www.cs.princeton.edu/courses/archive/fall06/cos528/handouts/Goldberg-Rao.pdf) for finding maximum flow. Its time complexity is $O(\min(m^{\frac{1}{2}}, n^{\frac{2}{3}}) \cdot m \log \frac{n^2}{m} \log U)$, where $U$ is maximum capacity in network. Consider any network with $m$ edges and $n$ vertices. Any reasonable programmer would merge parallel edges to one edge, summing their capacities, because it obviously reduces running time of algorithm. However, to reduce running time even more,...
New powerful optimization technique, In this blog I will tell you about recently invented powerful optimization technique, which can, Now there're some applications of this optimization.

Read more »

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

 
 
 
 
9.
By bicsi, history, 14 months ago, In English
Autotest: Creating test cases by optimization ### https://github.com/bicsi/autotest Hello! For the last two days I have been working on an idea of mine that I had for quite some time but haven't had the time to implement until now. It is a framework for automatic test generation using optimization methods. ### The main point I want to help people that are into problem-setting but might have problems writing generators (or might have little time to do so). I was thinking that, instead of coming up with complicated generators, one might be able to reuse some generic parametric generators for given structures (partitions, graphs, polygons, etc.) and generate tests by focusing on designing a "fitness" function for a given input case. Not only that, but many times while preparing problems I found that I was writing some generators by giving them some free parameters and trying to optimize something for the test, while keeping some randomness (for example, making the output answer as big as possible s.t. the constraints...
Autotest: Creating test cases by optimization, Also, I think it's also useful to have some generic framework for easy hyperparameteroptimization, I've recently learned about automatic hyperparameter optimization using techniques suitable, optimization methods.

Read more »

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

 
 
 
 
10.
By andreyv, 7 years ago, translation, In English
Catching silly mistakes with GCC As you know, the C++ language assumes that the programmer is always correct. Therefore C++ compilers don't add additional checks to the program, such as checks for null pointer dereference or out-of-bounds array access. This is good, because C++ programs run as fast as possible, and this is bad, because sometimes we may spend a long time debugging some silly mistake. We would want that the compiler can find such mistakes automatically. And many compilers can! In this post I will show various GCC options that do this. Previously [user:zakharvoit,2015-01-02] already wrote about this [here](/blog/entry/13875). All options that will follow should be added to the GCC command line. In various IDEs you can do it in IDE or compiler settings. Many of the options can also be used with Clang (for example, in Xcode). For MSVC++, I think, there is nothing better than Debug mode and `/W4`. [cut]   GCC warnings ------------------ Of course, the first step to debugging is to enable compi...
warnings are only enabled together with optimization. Below I will list some useful options, `. The last option is needed because some warnings are only enabled together withoptimization. Below I

Read more »

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

 
 
 
 
11.
By linkret, history, 5 years ago, In English
Incredibly beautiful DP optimization from N^3 to N log^2 N The task I want to discuss is [problem:739E]. While the official solution is a greedy algorithm sped up enough to pass the time limit, I recently came upon another solution. The main idea is to speed up the obvious dp approach, where we define dp[i][x][y] as the maximum expected number of caught pokemon in the prefix of first i pokemon, if we throw at most x A-pokeballs and at most y B-pokeballs. The computation of each state is O(1), so the complexity of this solution is O(n^3). [cut] There is no obvious way to speed up this dp, because the transition of states is already done in O(1), and that's where dp optimization techniques usually cut the complexity. It's also useless to use some other definition of dp, since they will all take O(n^3) time to compute. But what we can do is to use the same trick used to solve the task Alien, from IOI 2016, or [problem:674C] in O(n log k) as [user:Radewoosh,2017-01-11] had described on his blog, and completely kick out a dimension from our dp! ...
Incredibly beautiful DP optimization from N^3 to N log^2 N, ), and that's where dp optimization techniques usually cut the complexity. It's also useless to use some

Read more »

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

 
 
 
 
12.
By art-hack, history, 18 months ago, In English
Matrix Exponentiation Optimization Hey Everyone, So I saw this problem in one of the contests on Codechef([link](https://www.codechef.com/problems/CARR)) Problem Statement You are given two integers N and M. Find the number of sequences A1, A2,…,AN, where each element is an integer between 1 and M (inclusive) and no three consecutive elements are equal. Since this number could be very large, compute it modulo 109+7. So I used my general code for Matrix Exponentiation but got a TLE. <spoiler summary="My submission"> ~~~~~ /* Code by __ __ __ /\ \__ /\ \ /\ \ __ _ __\ \ ,_\ \ \ \___ __ ___\ \ \/'\ /'__`\ /\`'__\ \ \/ \ \ _ `\ /'__`\ /'___\ \ , < /\ \L\.\_\ \ \/ \ \ \_ \ \ \ \ \/\ \L\.\_/\ \__/\ \ \`\ \ \__/.\_\ \_\ \ \__\ \ \_\ \_\ \__/.\_\ \____\ \_\ \_\ \/__/\/_/ \/_/ \/__/ _______\/_/\/_/\/__/\/_/\/____/ \/_/\/_/ ...
Matrix Exponentiation Optimization

Read more »

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

 
 
 
 
13.
By tourist, history, 4 years ago, translation, In English
VK Cup 2017 Round 3 + Codeforces Round #412 -- Tutorial Here is the tutorial of VK Cup 2017 Round 3 and Codeforces Round #412. Enjoy! <spoiler summary="Is it rated?"> [tutorial:807A] <spoiler summary="Code"> ~~~~~ n = int(input()) results = [] for i in range(n): results.append(list(map(int, input().split()))) for r in results: if r[0] != r[1]: print("rated") exit() for i in range(n): for j in range(i): if results[i][0] > results[j][0]: print("unrated") exit() print("maybe") ~~~~~ </spoiler> </spoiler> <spoiler summary="T-Shirt Hunt"> [tutorial:807B] <spoiler summary="More efficient code"> ~~~~~ #include <bits/stdc++.h> using namespace std; int main() { int p, x, y; cin >> p >> x >> y; for (int s = y; ; s++) { if (s % 50 != x % 50) { continue; } bool me = false; int i = s / 50 % 475; for (int j = 0; j < 25; j++) { i = (i * 96 + 42) % 475; if (i + 26 == p) { me = true; ...
~~~~~ n = int(input()) a = sorted(list(map

Read more »

Tutorial of VK Cup 2017 - Round 3
 
 
 
 
  • Vote: I like it
  • +570
  • Vote: I do not like it

 
 
 
 
14.
By ujzwt4it, history, 4 years ago, In English
Dot Product Optimization I have been trying to solve this problem on SPOJ-- (http://www.spoj.com/problems/DPMAX/) <br/> After 6hrs of trying and 16 wrong submissions, I have finally decided to seek some help. <br/> **Brief Overview**<br/> We are given n vectors. The problem asks us to calculate the maximum dot product of every vector with any other vector including itself. The absolute value of x and y coordinates is less than equal to 10^5. And there are 2*10^5 vectors to process.<br/> **My approach**<br/> 1.Take these vectors as points. Find their convex hull.<br/> 2. The answer for all vectors will be the dot product with another vector with its end as a point of convex hull found <br/> 3.Hypothesis--The maximum dot product for a vector lying in first quadrant should be with a vector which forms the upper right hull of the convex hull, similarly for a second quadrant vector it should be with a vector which forms the upper left hull and so on.<br/> 4.So vectors in the four different quadrants are...
Dot Product Optimization

Read more »

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

 
 
 
 
15.
By Dart-Xeyter, history, 9 months ago, In English
Some easy but useful optimization in Python. I have a few friends who write rounds in `Python`, and I noticed that they don't use some very simple optimizations, and the program ends up getting `TL`. Meanwhile, if you use these constructions, in half or more cases `TL` is removed. I will show everything using the example code of my friend [user:I_am_Drew,2020-10-31] from a [problem:1413B]. This code received `TL` (worked longer than $1$ second). ~~~~~ for __ in range(int(input())): n, m = list(map(int, input().split())) kek = [] for i in range(n): el = list(map(int, input().split())) el.append(0) kek.append(el) stolb = list(map(int, input().split())) ind = 0 for i in range(m): if kek[0][i] in stolb: ind = i break for i in range(n): kek[i][m] = stolb.index(kek[i][ind]) for j in range(m-1): stolb = list(map(int, input().split())) kek.sort(key=lambda x: x[m]) for elem in kek: elem...
Some easy but useful optimization in Python., or output $1$ number, optimization of fast input-output becomes useless. However, it comes in handy, , optimization of fast input-output becomes useless. However, it comes in handy in many tasks.

Read more »

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

 
 
 
 
16.
By SPyofgame, history, 5 months ago, In English
Knapsack the tutorial -------------------- -------------------- <a name="TOC"></a> > **Teleporter:** **[**[Previous](#status)**]** | | | **[**[Next](#statement)**]** ### <strong> <center style="color:red;"> Table of content </center> </strong> > This blog isnt the best but worth spending time to read it | Teleporter | Description | | :--------------------------------------------------------------- | :-------------------------------------------------------------------------------------------- | | [I. STATEMENT](#statement) | Taking about the problem | | [II. EXAMPLE](#example) | To understand the problem better | | [III. Solution for small number ...

Read more »

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

 
 
 
 
17.
By NiceClock, 8 months ago, In English
Array size optimization Hello codeforces! Some days ago, I solved task which was to optimize $O(N^3)$, where $N \leq 2000$. There was a matrix $2000 \times 2000$. After all optimizations, the following happened: 1) a[2000][2000] got TL 2) a[2048][2048] got TL 3) a[2048][2000] got AC I understand, that sizes like $2^k$ are <s>faster</s> slower because of cache and all that jazz. But I can't compare knowledge with the obtained result. Does anyone know why this is happening? P.S. Explained to me by the Great and Powerful 'Xellos'. P.S.S Half of my knowledge of optimizations is [The Lord of the Chairs who wished to stay behind the scenes], I am grateful to him for that. And for the following optimization fact: If the task requires XOR, then instead of int it is faster to use unsigned int. Why? If the number is positive, then it is stored in int with a bit equal to 1. We all know that 1 XOR 1 = 0. That is, in fact, in the XOR operation code between two ints, we will change this bit s...
Array size optimization, for that. And for the following optimization fact: If the task requires XOR, then instead of int it is faster to use unsigned, the scenes], I am grateful to him for that. And for the following optimization fact:

Read more »

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

 
 
 
 
18.
By Nisiyama_Suzune, 4 years ago, In English
[Tutorial] Math note — Dirichlet convolution Originating from [Project Euler](https://projecteuler.net/), Dirichlet convolution saw its use in optimizing the problem to compute the partial sum of some specific multiplicative function. This article is aimed to introduce the exact technique applied. Prequisite ================== This tutorial can be viewed as an extension of [the previous tutorial](http://codeforces.com/blog/entry/53925), so I recommend to take a look at that one first. Dirichlet convolution ================== [Dirichlet convolution](https://en.wikipedia.org/wiki/Dirichlet_convolution) is a way to generate a new function from two functions. Specifically, the Dirichlet convolution of two functions $f(x)$ and $g(x)$ is: $$ \displaystyle f*g(x)=\sum_{d|x}f(d)g(\frac{x}{d}) $$ We already know that one property of such convolution is that if $f(x)$ and $g(x)$ are all multiplicative, $f*g(x)$ is multiplicative as well. Based on the property of the Möbius inversion $\sum_{d|n}\mu(d)=\epsilon(n)=[n=1]...
Optimization technique ======================, We just apply the optimization technique exactly the same as above.

Read more »

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

 
 
 
 
19.
By MVernik, history, 9 months ago, In English
Disney Optimization <spoiler summary="Good Morning"> Good morning!<br> Working as a Software Engineer in the Disney/MediaPRO Team and recently I've got a problem, which I solved but It's extremely slow. </spoiler> #### Problem You're given a set of hotel rooms, each room has it's own priority and each room has a client. You have to **minimize** the number of repeating clients in the hotel rooms, according to the rules:<br> - You can only swap clients with the same **priority**.<br> - You are not allowed to swap rooms.<br> - You are not allowed to swap priorities.<br> **Limitations:**<br> 0 < Rooms < 1000 <br> 0 < Priority < 10^9 <br> 'A' < Client < 'Z' <br> #### Example <br>Input:<br> ![image](https://user-images.githubusercontent.com/41151124/99181917-2ce93700-273a-11eb-8ca8-e2be689bbcac.png) <br>Output:<br> ![image](https://user-images.githubusercontent.com/41151124/99181925-34a8db80-273a-11eb-857c-87c9ff606580.png) <br> _The following example shows:_ <br> ...
Disney Optimization

Read more »

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

 
 
 
 
20.
By Karan2116, history, 5 years ago, In English
Everything About Dynamic Programming **I decided to gather some good material on the web related to DP and found some good explanation by svg on topcoder forums..Hence wrote this blog.Will format it when i get time.** ![ ](http://codeforces.com/predownloaded/2c/af/2caf058ab9cf6db0f875c573fb0d6e73de572122.png) **Problem:** About 25% of all SRM problems have the "Dynamic Programming" category tag. The DP problems are popular among problemsetters because each DP problem is original in some sense and you have to think hard to invent the solution for it. Since dynamic programming is so popular, it is perhaps the most important method to master in algorithm competitions. The easiest way to learn the DP principle is by examples. The current recipe contains a few DP examples, but unexperienced reader is advised to refer to other DP tutorials to make the understanding easier. You can find a lot of DP examples and explanations in an excellent tutorial Dynamic Programming: From novice to advanced by Dumitru. The purpose ...
**Optimization DP problem**, **Recovering the best solution for optimization problems**, **Rotate the optimization problem**

Read more »

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

 
 
 
 
21.
By twoslow, history, 2 years ago, In English
Memory Optimization I have a tuple T, consisting of 1. An integer $id$ in range $[1, 70 \times 10^6]$ 2. A double $score_1$ in range $[0.0, 1.0]$ 3. A double $score_2$ in range $[0.0, 1.0]$ 4. An integer $x$ in range $[0, 2]$ What can be the most efficient way to store such tuple $T = <id, score_1, score_2, x>$ given that only $5$ digits after the decimal are sufficient for $score_1$ and $score_2$. --- Currently, I am storing this tuple as a long which takes 8 bytes of memory. $27$ bits for $id$, $17$ bits for $score_1$, $17$ bits for $score_2$ (considering values upto 5 decimal digits), and $2$ bits for $x$, Overall $63$ bits. I'm trying to optimize the memory usage as there are millions of such tuples in an array. Also, If your way can store digits more than 5 decimal places, please tell me. **Is there a way, by which we can store the tuple T using float or some other data type?** given that if the tuple is hashed to float, I should be able to get back $id, x$ accurately and $scor...
Memory Optimization

Read more »

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

 
 
 
 
22.
By andreyv, 9 years ago, translation, In English
Yet again on C++ input/output Hello! I wish to continue the discussion on C++ input/output performance, which was [started](http://codeforces.com/blog/entry/562) by [user:freopen,2012-09-05] long ago. [user:freopen,2012-09-05] compared the speed of the two common input/output methods in C++: the stdio library, inherited from C (`<stdio>`), and the newer iostreams library (`<iostream>`/…). However, these tests did not account for the fact that there are several important iostreams optimizations which can be used. They have been mentioned more than once on Codeforces ([first](http://codeforces.com/blog/entry/10), [second](http://codeforces.com/blog/entry/4006), [third](http://codeforces.com/blog/entry/4669)). I have written [a program](https://bitbucket.org/andreyv/cppiotest/src/tip/iotest.cpp) that compares performance of the stdio and iostreams libraries with these optimizations turned on. [cut]   **UPD1**: Added information on `_CRT_DISABLE_PERFCRIT_LOCKS`.<br/> **UPD2**: Added `printf()`/`scanf()` ca...
The second optimization is about untying `cin` from `cout`:

Read more »

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

 
 
 
 
23.
By overACer, history, 18 months ago, In English
A DP optimization Problem: 1D dp speedup: (http://dmoj.ca/problem/cco19p4) This dp satisfies the property $dp[j]=max_{i<j} (dp[i]+C[i][j])$, where $C[i][j]$ satisfies quadrangle inequality. How can I optimize to O(n log n) or O(n)? Outline: since all queries are sorted in ascending order, I can do it with convex hull and binary search (if k=3). This gives O(n log n). How binary search is done: Fix $i<k<j$, we compare $dp[i]+C[i][j]$ with $dp[k]+C[k][j]$ Note $C[i][j]=(prefix[j]-prefix[i])^{\frac{k}{2}}$. It grows faster than $C[k][j]$. In fact, $(prefix[j]-prefix[i])-(prefix[j]-prefix[k])$ is an invariant, call $x$. Let $y=dp[k]-dp[i]$. Rewrite $C[k][j]=z, C[i][j]=z+x$. Consider $(a,b)$ such that $a^{\frac{3}{2}}-b^{\frac{3}{2}}=y$, and $a-b=x$. The precise solution would use sqrt, and would take O(log n) anyways (to an error of $10^{-6}$, might raise if TLE). (Am I wrong?) Note $a$ corresponds to $C[i][j]$ and $b$ corresponds to $C[k][j]$, even though they might never be equal to tho...
A DP optimization

Read more »

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

 
 
 
 
24.
By Romka, history, 3 years ago, translation, In English
Yandex.Algorithm — Optimization track, round 1 Hello everyone! My name is Roman Udovichenko and I am glad to inform you that the first optimization round of Yandex.Algorithm is in full swing! This time we offer you [to solve the problem](https://contest.yandex.com/algorithm2018/contest/7655) prepared by the Yandex self-driving cars team. ![ ] (/predownloaded/81/95/819594b31ccce01a6bfad4f78cac6e97051a43fc.jpg) We hope that driverless future is not too far, so we ask you to develop an algorithm for optimal management of the fleet of driverless taxis. Of course, the task is very simplified and real self-driving cars development is way more sophisticated, but the duration of our round is not too long either: you have only one week to solve it. Basic solution to this problem is pretty straightforward, but I believe there are many possible improvements. Will you be able to come up with some really interesting idea? It's all up to you and the remaining time is more than enough :) The authors of the top scoring solutions in th...
Yandex.Algorithm — Optimization track, round 1, My name is Roman Udovichenko and I am glad to inform you that the first optimization round, The authors of the top scoring solutions in the optimization track will receive a cash prize, optimization round of Yandex.Algorithm is in full swing! This time we offer you [to solve the problem](https

Read more »

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

 
 
 
 
25.
By lunchbox, 6 weeks ago, In English
Unofficial AtCoder DP Contest Editorial This post contains the editorials for all tasks contained in the [AtCoder DP Contest](https://atcoder.jp/contests/dp/tasks), since there is no official editorial. This is written by [user:nwatx,2021-06-25] and me. ## [A &mdash; Frog 1](https://atcoder.jp/contests/dp/tasks/dp_a) <spoiler summary="Analysis"> **Time Complexity:** $\mathcal{O}(N)$ Use dynamic programming and define $\texttt{dp}[i]$ as the minimum cost to reach stone $i$. Then, there are only two transitions: - Jump one stone: $$ \texttt{dp}[i + 1] = \min(\texttt{dp}[i + 1], \texttt{dp}[i] + |\texttt{A}[i] - \texttt{A}[i + 1]|) $$ - Jump two stones: $$ \texttt{dp}[i + 2] = \min_{0 \le i + j < N}(\texttt{dp}[i + 2], \texttt{dp}[i] + |\texttt{A}[i] - \texttt{A}[i + 2]|) $$ </spoiler> <spoiler summary="Code"> ```cpp #include <bits/stdc++.h> using namespace std; const int mx = 1e5+1; int A[mx], dp[mx]; int main() { cin.tie(0)->sync_with_stdio(0); int N; cin >>...
)$ with [Knuth's Optimization](https://jeffreyxiao.me/blog/knuths-optimization).

Read more »

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

 
 
 
 
26.
By Spheniscine, history, 21 month(s) ago, In English
Notes on using Kotlin for competitive programming I pretty much exclusively use Kotlin for competitive programming, mostly because it's the language I'm currently most comfortable with. Here are some scattered notes and tidbits about my experience which I think might be useful to others; if you have any tips/suggestions, feel free to let me know. ### Primer - Kotlin has an official [primer for competitive programming](https://kotlinlang.org/docs/tutorials/competitive-programming.html). However, the IO code suggested there is only so-so; it's definitely better than `Scanner`, but you definitely can save a lot of runtime in heavy input problems by using the classic Java combination of `BufferedReader` + `StringTokenizer` <spoiler summary="My current IO template"> ``` @JvmField val INPUT = System.`in` @JvmField val OUTPUT = System.out @JvmField val _reader = INPUT.bufferedReader() fun readLine(): String? = _reader.readLine() fun readLn() = _reader.readLine()!! @JvmField var _tokenizer: StringTokenizer = StringTokenizer(...
- `tailrec fun` – tail recursion optimization

Read more »

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

 
 
 
 
27.
By Sprdalo, history, 4 years ago, In English
Top Optimizations [2018][Works] Hello frends from CFS(CodeForces)! Hir are some of the bestest optimizations that will get your rating jump to th clouds!!1!! I use them every single time beliv me! 1) Use BFS aka BruteForce. First thing you need to do when you do some problem is use BFS!! Dat will save you from: Terminated signal 1e+27387282, WA, TLE, MLE, CE, RTE, BQE... 2) When you wait in queue for long time, just agressivly press Alt + F4 few times. There will be queue no more gut frend. You will be advantage, thank mi later babe. 3) Before the contest you **MUST** pray to MAJKAMirzayanov. MajkaMirzayanov is the mother of the almighty MikeMirzayanov! Note: Majka is read Mike &mdash; a in Serbian, Russian, etc... Thank to that godess we hav our savior MikeMirzayanov frends!!! Btw his worst enemy is bad gredaer. 4.41423568) If you want to know everything ju should watch those Indian guys/girls on YT(youtube) who intrduce themselves as 419NigerianPrince or PussyDestroyerIndia(Im nut talking about pus...

Read more »

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

 
 
 
 
28.
By Sammarize, 7 years ago, translation, In English
Way of problemsetter *The mystery of creating rounds unveiled by author of the 4 of them! The guide for preparing the round without horror-fiction and pastorals!* Thanks for [user:RodionGork,2014-06-13], who push me to writing this post and thanks for [user:lucAbalo,2014-06-13], who push [user:RodionGork,2014-06-13] to pushing me to writing this post. Also, many thanks to [user:RodionGork,2014-06-13] for the translation of this post to English. ##1. Inventing problems It's hard to advise anything on this point. There's no some standard way of creating problems &mdash; and if one have existed we'll have only "complicated algorithmic exercises" instead of "problems". People who participated in Russian Code Cup do know well the tasks of that sort. To cook good and interesting problem there should be some **idea!** which came to your mind (and later to minds of participants of the contest). Even the simplest problems of `A` level for the `Div2` should have some **idea**. So here is the war...
with bit optimization.

Read more »

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

 
 
 
 
29.
By Agnimandur, history, 5 weeks ago, In English
Codeforces Round 736 Editorial Problems A, B, C, D, E, F1, and F2 were all created by [user:Agnimandur,2021-07-06]. Problem G was created by [user:Benq,2021-07-06]. I hope that this hint-based editorial helps you, no matter what your rating is! Solution code is provided in both Java and C++. [problem:1549A] --------------------------- <spoiler summary="Hint 1"> Fix $a$ into a convenient constant. </spoiler> <spoiler summary="Solution"> Since $P \ge 5$ and is also a prime number, we know that $P-1$ is an even composite number. A even composite number is guaranteed to have at least 2 unique divisors greater than 1. Let two of these divisors be $a$ and $b$. It is guaranteed that $P\mod{a} = P\mod{b} = 1$, and thus this selection is valid. For example, we can simply pick $a=2$ and $b=P-1$, and we will get a correct solution. The time complexity is $\mathcal{O}(Q)$. </spoiler> <spoiler summary="C++ Code"> Written by [user:penguinhacker,2021-07-06] (Runtime: 15ms) ~~~~~ #include <bits/stdc++.h>...
optimization that is sufficient for AC is to only calculate $\frac{N^2}{2}$ GCDs instead of all $N^2$ (since

Read more »

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

 
 
 
 
30.
By Romka, history, 3 years ago, translation, In English
Second round of the Yandex.Algorithm Optimization track has been started! Hello everyone! :) In case you missed our e-mail, we inform you that the second round of the Yandex.Algorithm Optimization track has been started today at 10:00 UTC +3. Like the first round, it will last for 7 days. There is one task which does not have the complete solution that can be found in a few seconds, but you can try different approaches to score as many points as possible. According to the results of the two rounds (see section 3 in https://contest.yandex.com/algorithm2018/rules/ &mdash; rules of combining results are the same for algorithmic and optimization tracks) we will determine the winners of the Optimization track and 128 future owners of the t-shirts with the logo of the competition. We have prepared for you a task that simulates the web crawling performed by the search robot. We offer you to experience the complexity of indexing sites and try to optimize the crawling of the Internet &mdash; this is just one of the problems that software engineer solve at Ya...
Second round of the Yandex.Algorithm Optimization track has been started!, of the Yandex.Algorithm Optimization track has been started today at 10:00 UTC +3. Like the first round, Optimization track has been started today at 10:00 UTC +3. Like the first round, it will last for 7 days

Read more »

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

 
 
 
 
31.
By firegod_galactus, history, 9 months ago, In English
C++ Optimizations — Help! I am doing a task in which there are `300000`(3e5) queries, after using assertion, I came to know only `5000` queries are left. I want to know if there are any other some c++ optimizations to squeeze my solution to AC. I am currently using: <br> 1. `scanf` <br> 2. `printf` <br> 3. `#pragma GCC target ("avx2") #pragma GCC optimization ("O3") #pragma GCC optimization ("unroll-loops")` <br> 4. `Fast I/O`
GCC target ("avx2") #pragma GCC optimization ("O3") #pragma GCC optimization ("unroll-loops")`, ") #pragma GCC optimization ("O3") #pragma GCC optimization ("unroll-loops")` 4. `Fast I/O`

Read more »

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

 
 
 
 
32.
By proofbycontradiction, history, 3 years ago, In English
TLE with an O(n sqrt(n)) n <= 200000. C++ optimizations needed. I was solving this interesting [number-theory + trees problem](https://codeforces.com/contest/842/problem/C). And I came up with an $O(n\sqrt{n})$ solution where $n \leq 200000$. My idea is that the answer for every node will either be a factor of the root or be a factor of the number itself, and only these about $2 \sqrt{n}$ values need to be tested. However, [this submission am getting TLE with this idea](https://codeforces.com/contest/842/submission/46672103). The solution in the editorial is a slight optimization of my idea - (a) either the answer is a factor of the root (because root is NOT marked as $0$) (b) or it's the GCD of all the ancestors except the root (because the root IS marked as $0$). This has the complexity of $O(n * k)$ where $k = $ number of factors of the root value, and $k = O(\sqrt{n})$. Thus the editorial solution and my solution have the same (theoretical) complexity. Could you suggest was that are __C++ implementation optimizations__ t...
in the editorial is a slight optimization of my idea - (a) either the answer is a factor of the root, /submission/46672103). The solution in the editorial is a slight optimization of my idea - (a) either

Read more »

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

 
 
 
 
33.
By aajjbb, 8 years ago, In English
A* Optimization Hello, I'm trying to solve this problem [Link](http://br.spoj.com/problems/RAPREGUI/). The problem statement is available in [LiveArchive](https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=&problem=1653&mosmsg=Submission+received+with+ID+1253271) in English. In the Brazilian SPOJ, the time-limit is quite strict, as the problem resumes to a grid shortest path, I choose the A* algorithm, which generally is faster than Djikstra and it's heuristics fits perfectly in 2-dimensional grids, but my solution isn't fast enough. How can I optimize more the A* ? The current code is: ~~~~~ struct MyLess { bool operator () (int x, int y) { return f[x] > f[y]; } }; int func (void) { int i, j; dist[conv(RF,CF)] = 0; vis[conv(RF,CF)] = 0; priority_queue<int, vector<int>, MyLess> q; q.push(conv(RF, CF)); for ( ; !q.empty(); ) { int now = q.top(); q.pop(); if (vis[n...
A* Optimization

Read more »

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

 
 
 
 
34.
By witua, 9 years ago, In English
Codeforces Round #136 — Editorial ###[problem:221A] In this problems you should notice that the answer for the problem is always of the following form: $n$, 1, 2, 3, ..., $n$-1. In such case array will be always sorted after the end of the algorithm. ###[problem:221B] Here you just need to find all divisors of $n$. This can be done using standart algorithm with iterating from 1 to $sqrt(n)$. After that you need to write some function that checks whether two numbers has same digits. This also can be done using simple loops. ###[problem:220A] There are multiple possible solutions for this problem. For example, the following. Find the last index $x$ such that there exists some $y$ $(y < x)$ (minimal possible) that $A_x$ < $A_y$. Then you just need to try two possibilities --- either swap $A_x$ and $A_y$, or don't change anything. ###[problem:220B] This problem can be solve in simpler $O(NsqrtN)$ solution, but I will describe $O(NlogN)$ one. We will solve this problem in offline. For each $x$ $(0 \l...

Read more »

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

 
 
 
 
35.
By meooow, 3 years ago, In English
[Tutorial] Convex Hull Trick — Geometry being useful ### The problem Let us consider the problem where we need to quickly calculate the following over some set $S$ of $j$ for some value $x$. $$\max_{j \in S} \{m_j \cdot x + c_j\}$$ Additionally, insertion of new $j$ into $S$ must also be efficient. This will most likely be encountered with DP problems. For example, the recent problem [problem:1083E] from Round #526 has the following DP formulation after sorting the rectangles by $x$. $$f(i) = x_i \cdot y_i - a_i + \max_{1 \le j < i}\{-x_j \cdot y_i + f(j)\}$$ The problem requires quick calculation of the above define maximum for each index $i$. How can this be done? ### The idea Notice the special form of $m_j \cdot x + c_j$. This is identical to the equation of a straight line with slope $m_j$ and Y-intercept $c_j$. So the problem is equivalent to being given a set of lines and asked for the maximum $y$ value any of those lines can give at a particular $x$. If you draw a bunch of straight lines on a plane, you'll...
Optimization (YouTube)](https://www.youtube.com/watch?v=OrH2ah4ylv4) - [Dynamic Programming Optimizations

Read more »

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

 
 
 
 
36.
By pfctgeorge, 10 years ago, In English
Why the optimization of GNU C++ took me to Wrong Answer? <div>I tried to submit my code with GNU C++ Compiler for 126A, then I got Wrong Answer on test #31 sadly.</div><div><br /></div><div><br /></div><div><div>#include&lt;cstdio&gt;</div><div>#include&lt;cstdlib&gt;</div><div>#include&lt;cstring&gt;</div><div>#include&lt;algorithm&gt;</div><div>#include&lt;cmath&gt;</div><div>#include&lt;iostream&gt;</div><div>#include&lt;string&gt;</div><div>using namespace std;</div><div><br /></div><div>const double eps=1e-8;</div><div>int main()</div><div>{</div><div>&nbsp; &nbsp; long long t1,t2,t0,x1,x2;</div><div>&nbsp; &nbsp; cin&gt;&gt;t1&gt;&gt;t2&gt;&gt;x1&gt;&gt;x2&gt;&gt;t0;</div><div>&nbsp; &nbsp; if (t1==t2)</div><div>&nbsp; &nbsp; {</div><div>&nbsp; &nbsp; &nbsp; &nbsp; printf(&quot;%I64d %I64d\n&quot;,x1,x2);</div><div>&nbsp; &nbsp; &nbsp; &nbsp; return 0;</div><div>&nbsp; &nbsp; }</div><div>&nbsp; &nbsp; else if (t1==t0)</div><div>&nbsp; &nbsp; {</div><div>&nbsp; &nbsp; &nbsp; &nbsp; printf(&quot;%I64d 0\n&quot;,x1);</div><div>&nbsp; &nbs...
Why the optimization of GNU C++ took me to Wrong Answer?

Read more »

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

 
 
 
 
37.
By llbra9z, history, 2 years ago, In English
When can 'Ofast' optimization bring negative optimization We all know that this line in C++`#pragma GCC optimize("Ofast")` can optimize most programs. But specially, the accident(maybe?) happens on me. Today, I was solving the problem [problem:455D] with fhq-treap, And I submitted two submissions: [submission:58122597] and [submission:58123225], when first one got AC with no optimization, and the second with 'Ofast' optimization got TLE on test 25. So I just want to know what kind of programs the 'Ofast' optimization can bring negative optimization?
When can 'Ofast' optimization bring negative optimization, : [submission:58122597] and [submission:58123225], when first one got AC with no optimization, So I just want to know what kind of programs the 'Ofast' optimization can bring negative, ], when first one got AC with no optimization, and the second with 'Ofast' optimization got TLE on test

Read more »

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

 
 
 
 
38.
By ditoly, history, 3 years ago, In English
Codeforces Round #511 Editorial Hi, here is the editorial. Sorry for a long waiting. Have you enjoyed this round? I hope so. I know there are many things not so good and making some people unhappy :( I'm very sorry about that. Since this is my first round, I have many things not taken into consideration or done badly. I will try to improve them if I have my next round (I hope). Let's talk about the problems. The problems are mainly prepared by me, [user:ditoly,2018-09-22], which can be seen in D1D as "Little D". Also, my friends [user:ACMLCZH,2018-09-22] ("Little C") and [user:FallDream,2018-09-22] ("Mr. F", I don't know whether this name can explain Chinese word "F大爷" well, maybe "Master F" is better?) provided great helps. The statements are mainly written by me (with the help of [user:300iq,2018-09-22] and [user:cyand1317,2018-09-22] and some others, thanks!). My English is not so good, so it's frequent that I just understand the problem but other people get AC :( So I try to explain the problems in short st...
an interesting optimization.

Read more »

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

 
 
 
 
39.
By never_giveup, history, 3 weeks ago, translation, In English
Lambda optimization certificate 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!
Lambda optimization certificate, . Lagrange) dp optimization for non-strict convex functions. Any help is highly appreciated!

Read more »

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

 
 
 
 
40.
By nishu271, 8 years ago, In English
SPOJ MCHAOS -- TLE with BIT + STL and WA after optimisation Hi all, I was trying to solve http://www.spoj.com/problems/MCHAOS/. I think my solution is correct with the given constraints. I got TLE with BIT and STL maps initially in the 10th test case. Then I tried to optimize by converting strings into longs (preserving their order) and sorting long long[] instead of vector\<string\>. This gave WA. I believe there is some problem in the hash() function but I was not able to find it. Can someone help or suggest some other optimization? Here are the two versions of the code... ~~~~~ #include <stdio.h> #include <string> #include <map> #include <string.h> #include <iostream> #include <algorithm> #include <vector> using namespace std; typedef long long int ll; const int NMAX = 100000+5; ll BIT[NMAX]; int LIM = 0; map<ll, int> dict; char vs[NMAX][11]; vector<string> vecs, seq; ll read (int v) { ll sum = 0; while (v) { sum += BIT[v]; v -= v &-v; } return sum; } void update (int v...
After the optimization ...

Read more »

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