Bugman's blog

By Bugman, history, 10 months ago, ,

We have n points (xi, yi). Let both x and y be different and from [1, n].

Initially, all points have zero value.

Two types of queries:

1) add X — adding +1 to all points with xi ≤ X

2) sum Y — calculate sum of values of points with yi ≤ Y

What is best known solution? (Problem not from running contest).

• +49

By Bugman, history, 21 month(s) ago, ,

I've heard more about how vector<bool> is slow, and we need to dodge him or use vector<char>.

But today I ran some tests in "Codeforces custom test" with GNU G++.

First simple erato sieve

//N = 3e7
for(int i=2;i<N;++i) if(!u[i]) for(int j=i*2;j<N;j+=i) u[j] = 1;
int cnt = 0;
for(int i=0;i<N;++i) if(u[i]) ++cnt;
cout<<cnt<<endl;


Depends on u:

bool u[N] : 420 ms, 31204 KB

vector<bool> u(N): 218 ms, 5484 KB

vector<char> u(N): 451 ms, 31164 KB

You can say like "memory constant speed up this code"

Second.

//N = 1e4
double total = 0;
for(int it=0;it<N;++it){
for(int i=0;i<N;++i){
int x = rand()%N;
u[x] = 1;
}
for(int i=0;i<N;++i){
int x = rand()%N;
u[x] = 0;
}
for(int i=0;i<N;++i){
total+=u[i];
u[i] = 0;
}
}
cout<<total/N<<endl;


bool u[N] : 2683 ms, 1860 KB

vector<bool> u(N): 2667 ms, 1832 KB

vector<char> u(N): 2620 ms, 1868 KB

We see its equal!

So maybe its not so bad? Or you have examples where vector<bool> is really slower than alternatives?

• +57

By Bugman, history, 2 years ago, ,

For given number 2 ≤ n ≤ 1018 check prime or not it is.

Limits are: 1 second TL, 16Mb ML.

And we have solution:

bool isprime(LL n){
if(n<2) return false;
for(LL i=2;i*i*i<=n;++i) if(n%i==0) return false;
for(int it=0;it<1e5;++it){
LL i = rand()%(n-1)+1;
if(__gcd(i,n)!=1) return false;
if(mpow(i,n-1,n)!=1) return false;
}
return true;
}


where rand() returns 64-bit random integer and mpow(a,b,m) is ab modulo m.

Can you challenge this solution?

• +42

By Bugman, history, 4 years ago, ,

Hi people! I interested in problems with template name "Count of subrectangles" or "Best subrectangle" in rectangle. For example some well-known problems:

In given matrix of zeros and ones find subrectangle that contains only zeros and has largest area. It can be solved in O(n2).

In given matrix of integers find subrectangle with largest sum. It can be solved in O(n3).

Can you give me links or just statements on similar problems?

Here problems that i remembered:

• +38

By Bugman, 4 years ago, ,

Хотелось бы узнать, как проводится подготовка и проведение четвертей в разных регионах. Точно интересуют следующие вопросы:

• Как готовятся задачи (полигон, папка на компе, папка в облаке и т.д.);

• В чём проводится тур (известная система, или нет, название);

• Кем прорешиваются задачи (коллектив авторов, или есть вообще деление на авторов — подготовителей — прорешивающих);

• Условия задач на английском или на русском?

Интересна любая информация с разных регионов.

• +83

By Bugman, 5 years ago, ,

Всем привет!
Многим известны соревнования Google Code Jam, Facebook Hackercup, IPSC, ch24, deadline24 и т.п. Их объединяет то, что в задаче даётся инпут с мультитестом внутри, на который нужно посчитать ответ у себя локально. Мне стало интересно, пользуетесь ли вы распараллеливанием? Современные машины позволяют дать ощутимый прирост, например, чтобы избежать таких ситуаций.

А прошедший deadline24 мы писали так

Я решил написать свой вариант шаблона, и вот что у меня получилось: code.
Вот ещё другой подход от Kormyshov: code.

Кто может предложить другие варианты, желательно на с++? А может на других языках это делается проще? А может у кого-то есть инструменты, позволяющие параллелить инпут на несколько машин (кроме рук и флешки:)? Интересны любые ответы и замечания по теме.

• +41

By Bugman, 5 years ago, translation, ,

485A - Factory

Production will stops iff exists integer K ≥ 0 such a·2K is divisible by m. From this fact follows that K maximum will be about O(log2(m)). So if we modeling some, for example, 20 days and production does not stop, then it will never stop and answer is "No". Otherwise answer is "Yes".

485B - Valuable Resources

Let us find minimum length needed to cover points by Ox. It is Maximum(xi) - Minumum(xi). The same in OyMaximum(yi) - Minumum(yi). Since we need a square city to cover all the mines, then we need to set length of this square to the maximum from those two values.

484A - Bits

Let us define function f(L, R), that gives answer to the query. It looks follows:

• if L = R then f(L, R) = L;

• else if 2b ≤ L, where b — maximum integer such 2b ≤ R, then f(L, R) = f(L - 2b, R - 2b) + 2b;

• else if 2b + 1 - 1 ≤ R then f(L, R) = 2b + 1 - 1;

• else f(L, R) = 2b - 1.

Total complexity is O(logR) per query.

484B - Maximum Value

Let us iterate over all different aj. Since we need to maximize , then iterate all integer x (such x divisible by aj) in range from 2aj to M, where M — doubled maximum value of the sequence. For each such x we need to find maximum ai, such ai < x. Limits for numbers allow to do this in time O(1) with an array. After that, update answer by value . Total time complexity is O(nlogn + MlogM).

484C - Strange Sorting

Note, that d-sorting is just a permutation (call it P), because it does not depends on characters in string. Look at shuffling operation in different way: instead of going to the next substring and sort it, we will shift string to one character left. It remains to understand that shift of string the permutation too (call it C). Now its clear, we need to calculate S·P·C·P·C... = S·(P·C)n - k + 1. And after that shift string for k - 1 character to the left for making answer to the shuffling operation. Here we use the multiplication of permutations. Since they are associative, that we can use binary algorithm to calculate (P·C)n - k + 1. Total time complexity is O(nmlogn).

484D - Kindergarten

Let us note, that in optimal answer any segment that making a group contains their minimum and maximum values on borders. Otherwise it will be better to split this segment to two other segments. Another note that is every segment in optimal solution is strictly monotonic (increasing or decreasing). Paying attention to the interesting points in sequence which making local maximums (i. e. ai - 1 < ai > ai + 1), local minimums (ai - 1 > ai < ai + 1), and point adjacent to them. Solve the problem by dynamic programming: Di is the answer in the prefix i. To calculate Di we need to look at no more than three previous interesting points and to previous Di - 1. Total time complexity is O(n).

484E - Sign on Fence

Let us note that we can use binary search to find answer to the one query. Suppose at some moment was fixed height h and need to know will fit the rectangle with width w and height h to the segment of fence from l-th to r-th panel. Let us build data structure that can answer to this question. This will be persistent segment tree with unusual function inside: maximum number of consecutive ones in segment (maxOnes). In leaves of segment tree will be only numbers 0 and 1. To calculate this function need to know some other values, specifically:

len — length of the segment in vertex of segment tree, prefOnes — length of prefix that consists only of ones, sufOnes — length of the suffix consist only of ones.

These functions are computed as follows:

maxOnes is equal to max(maxOnes(Left), maxOnes(Right), sufOnes(Left) + prefOnes(Right));

prefOnes equals prefOnes(Right) + len(Left) in case of len(Left) = prefOnes(Left), and prefOnes(Left) otherwise;

sufOnes equals sufOnes(Left) + len(Right) in case of len(Right) = sufOnes(Right), and sufOnes(Right) otherwise;

len = len(left) + len(Right);

Left и Right — it is left and right sons of vertex in segment tree.

As mentioned above, tree must be persistent, and it must be built as follows. First, builded empty tree of zeros. Next in position of highest plank need to put 1. The same doing for planks in decreasing order. For example if fence described with sequence [2, 5, 5, 1, 3] then bottom of segment tree will changed as follows:

[0, 0, 0, 0, 0] -> [0, 1, 0, 0, 0] -> [0, 1, 1, 0, 0] -> [0, 1, 1, 0, 1] -> [1, 1, 1, 0, 1] -> [1, 1, 1, 1, 1].

And we need to remember for all hi their version of tree. Now to answer the question we need to make query in our segment tree (that corresponding to height h) on segment [l, r]. If maxOnes form this query less than w, then rectangle impossible to put (otherwise possible).

Building of tree will take O(nlogn) time and memory. Time complexity to the one query will take O(log2n) time.

• +66

By Bugman, 5 years ago, translation, ,

Hello everybody!

Today will be Codeforces Round #276, which take place in both divisions. Start time is 19:30 in moscow time (follow this link to see time in others zones). For preparing contest i say thanks to Zlobober, for translating to Delinur, and to MikeMirzayanov for project Codeforces.

Good luck to all, hope you will enjoy problems :)

UPD Score distribution will be dynamic (see more information here). Problems will be sorted in increasing order of difficulty, however, do not forget to read all problems before the end of the contest.

UPD The contest is over! Thanks to everyone who solved the problems despite everything. Analysis will be published later.

UPD Editorial can be found here.

• +276

By Bugman, 5 years ago, translation, ,

Hello, CodeForces community! I'm happy to tell you about upcoming 256-th round, which will be held for the participants from second division. Participants from first division can take part out of the competition.

I hope, for all this anniversary round. For me it is the first round in which I am the author, in this I will be glad to see everyone. Want to say thanks Gerald for help with preparing contest, Delinur for translating, and of course MikeMirzayanov for CodeForces project.

I am from Krasnoyarsk, and the hero of tasks will be our team talisman Bizon-the-Champion. Hope you like to spend time with him :) See you and good luck!

UPD. Few hours before the start. Score distribution will be dynamic (see more information here)

UPD. Round is over! You can find editorial here.

• +138

By Bugman, 5 years ago, translation, ,

448A - Rewards

Solution:7139559

Because rewards of one type can be on one shelf, lets calculate number of cups — a and number of medals — b. Minimum number of shelves that will be required for all cups can be found by formula (a + 5 - 1) / 5. The same with shelves with medals: (b + 10 - 1) / 10. If sum of this two values more than n then answer is "NO" and "YES" otherwise.

448B - Suffix Structures

Solution:7139584

Consider each case separately. If we use only suffix automaton then s transform to some of its subsequence. Checking that t is a subsequence of s can be performed in different ways. Easiest and fastest — well-known two pointers method. In case of using suffix array we can get every permutation of s. If it is not obvious for you, try to think. Thus, s and t must be anagrams. If we count number of each letter in each string, we can check this. If every letter appears in s the same times as in t then words are anagrams. In case of using both structures strategy is: remove some letters and shuffle the rest. It is possible if every letter appears in s not less times than in t. Otherwise it is impossible to make t from s. Total complexity O(|s| + |t| + 26).

448C - Painting Fence

Solution:7139610

To solve this problem we need to understand some little things. First, every horizontally stroke must be as widely as possible. Second, under every horizontally stroke should be only horizontally strokes. So, if bottom of fence painted by horizontally stroke then number of this strokes must at least min(a1, a2, ..., an). These strokes maybe divides fence into some unpainted disconnected parts. For all of these parts we need to sum they answers. Now its clearly that solution is recursive. It takes segment [l, r] and height of painted bottom h. But we must not forget about situation when all planks painted with vertically strokes. In this case answer must be limited by r - l + 1 (length of segment). With given constrains of n we can find minimum on segment by looking all the elements from segment. Complexity in this case will be O(n2). But if we use for example segment tree, we can achieve O(nlogn) complexity.

448D - Multiplication Table

Solution:7139620

Solution is binary search by answer. We need to find largest x such that amount of numbers from table, least than x, is strictly less than k. To calculate this count we sum counts from rows. In i th row there will be . Total complexity is O(nlog(nm)).

448E - Divisors

Solution:7139644

Learn how to transform Xi into Xi + 1. For this we need to concatenate lists of divisors for all elements of Xi. To do this efficiently, precalculate divisors of X (because for every i Xi consist of its divisors). It can be done by well-known method with complexity. How to calculate divisors of divisors? Need to know that for the given constrains for X maximum number of divisors D(X) will be 6720 (in the number 963761198400), so divisors of divisors can be calculated in O(D2(X)) time. With this lists we can transform Xi into Xi + 1 in O(N) time, were N = 105 — is the limit of numbers in output. Now learn how to transform Xi into X2i. What says Xi? Besides what would be X after i steps, it can tell where goes everyone divisor of X after i - 1 steps. Actually, Xi is concatenation of all Yi - 1, where Y is divisor of X. For example, 103 = [1, 1, 1, 2, 1, 1, 5, 1, 1, 2, 1, 5, 1, 2, 5, 10] = [1] + [1, 1, 2] + [1, 1, 5] + [1, 1, 2, 1, 5, 1, 2, 5, 10] = 12 + 22 + 52 + 102. How to know which segment corresponds for some Y? Lets pos(Y) be the first index of Y in Xi. Then needed segment starts from pos(prev(Y)) + 1 and ends in pos(Y), where prev(Y) is previous divisor before Y in sorted list of divisors. So, to make X2i from Xi we need to know where goes every element from Xi after i steps. We know all its divisors — it is one step, and for every divisor we know where it goes after i - 1 step. Thus, we again need to concatenate some segments in correct order. It also can be done in O(N) time. How to find now Xk for every k? The method is similar as fast exponentiation:

Xk = [X] when k = 0,

if k is odd then transform Xk - 1 to Xk,

if k is even then transform Xk / 2 to Xk.

This method takes O(logk) iterations. And one small trick: obviously that for X > 1 Xk starts from k ones, so k can be limited by N. Total complexity of solution is .

• +78

By Bugman, 7 years ago, ,

Здравствуй, сообщество CodeForces!

Пишу я задание для получения зачёта по проге и сталкиваюсь со следующей проблемой. В общем, имеется игра Реверси. Имеются несколько типов ботов, из них:

• жадный: ходит самым максимальным из доступных ходов (greedy)

• перебор minmax дерева игры глубиной до N (aiN)

• то же, что и выше, но написанное с ab-отсечением. (aiN_ab)

Имеется проблема:

Счёт за 300 игр:

• ai4 vs. greedy — 287:8 и это, я считаю, нормально

• ai4_ab vs. greedy — 250:47 и это не очень нормально.

Насколько я понимаю, аб-отсечения должны давать такой же результат, но быстрее. Собственно имеется вопрос: это не так или я делаю что-то не так? Исходники-примеры я брал отсюда, отсюда, отсюда и ещё с некоторых других источников (мой код). Результат везде одинаковый. Может у кого-то есть реальный пример какой-то игры, а не просто сатья-мануал? Ну или какие-то комментарии по этому поводу, буду очень признателен.