Блог пользователя slycelote

Автор slycelote, история, 8 лет назад, По-английски

I'm sure most of you know that all mainstream C++ compilers support inline assembly language. But did you know that you can actually embed Python in a similar way?

Here, for instance, I implemented gcd function in Python simply because it's easier and shorter. The rest of the code is in C++: 17084249. (By the way, kudos to Codeforces for correct highlighting of both Python and C++ parts!)

I'm not sure if it can be useful at all, but I thought that it's fun to share. Keep in mind it doesn't work in all compilers though!

Полный текст и комментарии »

  • Проголосовать: нравится
  • +530
  • Проголосовать: не нравится

Автор slycelote, 9 лет назад, По-английски

Like CHelper for Java, caide automates certain common tasks that you do during programming competitions: parsing, running and debugging problem tests, inlining library code. It currently supports C++ and C# programming languages. The list of supported online judges is here.

Download here. You can also install VS extension directly from Visual Studio.

Documentation:

Codelite and command line caide in Linux: (full size)

Codelite in Windows: (full size)

Visual Studio:

Полный текст и комментарии »

  • Проголосовать: нравится
  • +36
  • Проголосовать: не нравится

Автор slycelote, 9 лет назад, По-английски

tl;dr: Install VsCaide extension in extensions manager of Visual Studio 2013.

(NOTE: it's recommended to create caide project from scratch after update: use caide init from command line or "Create caide solution" button in Visual Studio.)

v1.2.1:

  • Fix Codeforces contest parser, GCJ, HackerRank
  • Support RCC contests, POJ
  • C++ inliner: don't remove used typedefs defined at class scope.

v1.2:

  • Fix Codeforces parser in russian interface
  • C++: Remove inactive preprocessor blocks, unused macros, unused typedefs
  • C# support in VS plugin
  • Compatibility with CHelper extension (command line only)
  • Support Google Code Jam, Russian Code Cup, HackerRank

Currently supported online judges: Codeforces, GCJ, CodeChef, Timus, HackerRank, POJ, RCC. (Topcoder is planned.) Currently supported IDEs: Visual Studio 2013, CodeLite. Currently supported programming languages: C++, C#.

caide automates certain common tasks that you do during programming competitions: parsing, running and debugging problem tests, inlining library code.

caide is inspired by such projects as chelper or jhelper. Its purpose is to automate the following tasks:

  • Parsing problem statement and extracting test cases
  • Generating solution scaffold
  • Inlining library code and preparing a single source file for submission
  • Running the tests on your solution
  • Debugging the tests

Unlike other projects, caide is designed to support multiple programming languages and IDEs/editors.

caide is split into the following projects:

  • libcaide is core command line application implementing all functionality. Windows and Linux are supported. Theoretically, it should also build on OS X, but I don't have access to a Mac.
  • VsCaide is caide frontend (extension) for Visual Studio; currently supports only C++ programming language.

Documentation, issue tracker and code: https://github.com/slycelote/caide

Полный текст и комментарии »

  • Проголосовать: нравится
  • +46
  • Проголосовать: не нравится

Автор slycelote, 10 лет назад, По-английски

Update: Turns out that both C# and Mono actually have the same problem as Java. I don't know C# though, so it would be great if someone reviewed the code of the benchmark (bottom of the post).

Recently I noticed that switching from HashSet to TreeSet in a Java program increased performance by several times. Since it didn't make any sense, I decided to investigate the issue, and here is what I found.

In my program I extracted an arbitrary member from a set in the following manner:

Integer elem = set.iterator().next();
set.remove(elem);

It turns out that implementation of HashSet.iterator() method in Java is poor: it always scans the bucket table from the very beginning. An excerpt from JDK code:

        HashIterator() {
            expectedModCount = modCount;
            if (size > 0) { // advance to first entry
                Entry[] t = table;
                while (index < t.length && (next = t[index++]) == null)
                    ;
            }
        }

In my situation the total number of buckets was 218, and each time a new element was extracted some part of the table had to be traversed to find the first non-empty bucket... you get the idea. As far as I understand, the implementation is the same in Java 6, 7 and 8.

I did benchmarks for C++ and C# as well.

  • Visual C++ 2012, Visual C# 2012 and Mono 2.10 all have the same problem.
  • g++ 4.6.3 doesn't. Looking at the code, they maintain the index of the first non-empty bucket. In certain situations (e.g. if we have a long sequence of insertions followed by a long sequence of removals) it guarantees that each bucket will be traversed only once.

The code of benchmarks is below. What puzzles me further about Java version is that if HashSet is tested after TreeSet, the performance is even worse than when tested in isolation. I'm using OpenJDK 1.7 if that matters.

import java.util.*;

public class TestSets {
    public static void main(String[] args) {
        testSet(new TreeSet<Integer>());
        testSet(new HashSet<Integer>());
    }

    static void testSet(Set<Integer> set) {
        long start = System.currentTimeMillis();

        final int N = 100000;
        for (int i = 0; i < N; ++i)
            set.add(i);
        for (int i = 0; i < N; ++i) {
            Integer elem = set.iterator().next();
            set.remove(elem);
        }

        long end = System.currentTimeMillis();
        double elapsed = (end - start) * 0.001;
        System.out.println("Elapsed time: " + elapsed + "s");
    }
}
#include <chrono>
#include <iostream>
#include <set>
#include <unordered_set>

template<typename Set>
void testSet() {
    auto start = std::chrono::system_clock::now();

    Set set;
    const int N = 600000;
    for (int i = 0; i < N; ++i)
        set.insert(i);

    for (int i = 0; i < N; ++i) {
        auto elem = *set.begin();
        set.erase(elem);
    }

    auto end = std::chrono::system_clock::now();
    std::chrono::duration<double> elapsed_seconds = end - start;
    std::cerr << "Elapsed time: " << elapsed_seconds.count() << "s\n";
}

int main() {
    testSet< std::set<int> >();
    testSet< std::unordered_set<int> >();
    return 0;
}
using System;
using System.Collections.Generic;

class TestSets
{
	static void testSet (ISet<int> set)
	{
		var start = System.DateTime.Now;
		
		const int N = 50000;
		for (int i = 0; i < N; ++i)
			set.Add (i);
		for (int i = 0; i < N; ++i) {
			var e = set.GetEnumerator();
			e.MoveNext();
			var elem = e.Current;
			set.Remove(elem);
		}
		
		var end = System.DateTime.Now;
		var elapsed = end - start;
		System.Console.Out.WriteLine ("Elapsed time: " + elapsed);
	}
	
	public static void Main (string[] args)
	{
		testSet (new SortedSet<int> ());
		testSet (new HashSet<int> ());
	}
}

Полный текст и комментарии »

  • Проголосовать: нравится
  • +35
  • Проголосовать: не нравится

Автор slycelote, 11 лет назад, По-английски

(I don't know whether there is an official bug tracker, so sorry for making it a blog post.)

Submission 3748858 is reported as runtime error, while it should be compilation error.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +7
  • Проголосовать: не нравится

Автор slycelote, 14 лет назад, перевод, По-русски

A. Почти простые числа

Это задача на реализацию: для каждого числа от 1 до n разложим его на простые множители и посчитаем количество различных простых делителей.

B. Правильная скобочная подпоследовательность

Будем читать строку слева направо и поддерживать на каждом шаге баланс скобок (т.е. разность между количеством выписанных открывающих и закрывающих скобок). Этот баланс должен быть всегда неотрицательным. Поэтому если он равен нулю и мы читаем закрывающую скобку, ее нужно пропустить и не выписывать. Ответ будет равен удвоенному количеству выписанных закрывающих скобок.

C. Паркет

Докажем несколько необходимых условий для существования паркета. Если какое-то из них не выполнено, ответ "IMPOSSIBLE".
1. m*n должно быть четным, т.к. это общая площадь паркета, а площадь каждой плитки четна.
2. Допустим, что m (количество столбцов) нечетно. Раскрасим гостиную в черный и белый цвета следующим образом: первый столбец черный, второй белый, третий черный, ..., последний черный. Число черных квадратов будет на n больше, чем число белых. Плитки 1x2 и 2x2 содержат равное число черных и белых квадратов, поэтому разность нужно компенсировать с помощью плиток 2x1, и их число должно быть хотя бы n/2. В этом случае мы можем замостить последнюю колонку этими плитками, уменьшить b на n/2 и уменьшить m на единицу.
3. Если n нечетно, то аналогично получаем a ≥ m / 2.
4. Теперь  m и n четны. Похожие рассуждения показывают, что число использованных плиток 1x2 и 2x1 должно быть четным. Поэтому если a нечетно, уменьшим его на 1, и то же самое с b.
5. Теперь должно быть mn ≤ 2a + 2b + 4c, иначе не хватит общей площади плиток.
6. Если все условия были выполнены, мы можем завершить замощение: разделим гостиную на квадраты 2x2 и заполним каждый либо одной плиткой 2x2, либо двумя плитками 1x2, либо двумя плитками 2x1.

D. Билеты

Если мы изобразим график числа доступных 10-евровых банкнот, это будет ломаная линия с началом в точке (0, k) и концом в точке (m+n, n+k-m). Ровно m звеньев идут вниз, остальные n звеньев — вверх. Поэтому общее число возможных графиков равно C(m + n, m) (биномиальный коэффициент). Нам нужно найти число графиков, которые не заходят под ось X. Мы посчитаем "дополнительное" значение: число графиков, которые заходят под ось X, то есть пересекают прямую y=-1.

Для этого мы используем "принцип отражений". Рассмотрим любой график, который пересекает прямую y=-1, и возьмем последнюю из точек пересечения. Отразим часть графика, начиная с этой точки, относительно прямой y=-1. Получится новый график, оканчивающийся в точке (m + n,  - 2 - n - k + m). Обратно, любой график, оканчивающийся в этой точке, пересекает прямую  y=-1, и мы можем применить к нему ту же операцию. Итак, число графиков, которые нас интересуют, равно числу графиков, начинающихся в точке (0, k) и заканчивающихся в точке (m + n,  - 2 - n - k + m). Пусть a и b — число звеньев в таком графе, идущих вверх и вниз соответственно. Тогда a + b = m + n, a - b + k =  - 2 - n - k + m. Отсюда a = m - k - 1, и число таких графиков равно C(m + n, m - k - 1).

Таким образом, вероятность того, что график зайдет под ось X, равна C(m + n, m - k - 1) / C(m + n, m) = (m!n!) / ((n + k + 1)!(m - k - 1)!) = (m(m - 1)... (m - k)) / ((n + 1)(n + 2)... (n + k + 1)). Ответ к задаче: 1 — (m(m - 1)... (m - k)) / ((n + 1)(n + 2)... (n + k + 1)).

E. Multithreading

Ясно, что w должно удовлетворять неравенствам . Если это так, покажем, как достигнуть такого результата в трех случаях:
1. N = 1, w = n1. Очевидно.
2. N ≥ 2, w ≥ 2. Для w = 2 схема такая: 1, все циклы процессов 3..N, n2 - 1 циклов второго процесса, 1, 2, n1 - 1 циклов первого процесса, 2. Для w > 2 нужно переместить несколько циклов из середины последовательности в конец.
3. N ≥ 2, w = 1, и существует i такое, что ni = 1. Схема такая: i, все циклы остальных процессов, i.

Теперь покажем, что в остальных случаях результат w недостижим. Случай N = 1, w ≠ n1 очевиден. Осталось разобрать ситуацию, когда N ≥ 2, w = 1, и ni > 1 для всех i. Допустим, что существует последовательность, для которой результат оказался равным y = 1. Рассмотрим последнюю операцию записи в этой последовательности, пусть ее провел процесс с номером i. Тогда соответствующая операция чтения должна была прочитать значение y=0. Это значит, что до нее не было произведено ни одной операции записи. Но это невозможно, т.к. ni > 1, и i-й процесс к этому моменту произвел ni - 1 циклов чтения/записи.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +24
  • Проголосовать: не нравится

Автор slycelote, 14 лет назад, По-русски
ВНЕЗАПНО вклад dAFTc0d3rа упал с over +20 до under -20, а brainail вырвался в топ лидеров.

Полный текст и комментарии »

  • Проголосовать: нравится
  • -4
  • Проголосовать: не нравится

Автор slycelote, 14 лет назад, По-русски

A. Дана строка...


Переберём все подстроки, начиная с самых длинных, и для каждой посчитаем, сколько раз она встречается. Сложность — O(L4) с маленькой константой.

Полный текст и комментарии »

Разбор задач Codeforces Beta Round 23
  • Проголосовать: нравится
  • +27
  • Проголосовать: не нравится

Автор slycelote, 14 лет назад, По-английски

(This FAQ may be outdated. Please refer to official help).

I'm sure we won't need this post after Codeforces comes out of beta, but meanwhile it could be useful :) Feel free to suggest what should be added here.

Competitions: general

Q. What are the rules of these contests?
A. Read this.

Q. What languages are supported? What are the compiler options and run command lines? What is the configuration of judge servers?
A. The judge machines are Core 2 Duo, 2.67 Ghz (E6750). The full list of supported languages and compiler options can be found in this post

Q. How do I hack other's solutions?
A. First lock your own solution in the main ('problems') tab. Then in your room double click or Ctrl+click the solution you want to hack. Check this post for complete rules concerning hacking.

Q. How is rating calculated?
A. The rating system is described in these two posts. Note that even for a joined contest the rating updates are calculated separately for the first and the second divisions. Therefore, a situation is possible, when a div2-coder performed worse than a div1-coder in the same contest, but gained more rating points.

Competitions: writing code


Q. How do I read/write 64bit integers in C/C++?
A. If you submit under "GNU C++" or "GNU C" option, use this:
   printf("%I64d\n",n);
but NOT this:
   printf("%lld\n",n);

If you submit under "MS C++" option, both variants should work.

And of course, with C++ you can always write
   std::cout << n << "\n";

Q. How can my program determine whether it runs in Codeforces server?
A. For most programming languages Codeforces environment defines the symbol ONLINE_JUDGE. Again, see this post for details.


Using the site


Q. How do I read other people's code?
A. After the contest is over, go to its page (for example, http://codeforces.com/contest/15 ) and click on this picture: . You will see a page with several submits (currently 100, I think). You can sort and filter the solutions there. To see the fastest solutions, you need to manually paste a URL like this: http://codeforces.com/contest/15/status/A?order=BY_ARRIVED_ASC
(currently there's no way to do this via UI)


Q. During the practice, can I see the test case that my program failed on?
A. No. YES! Go to 'My submissions' tab and click the link showing the ID of your submission.

Q. How can I find some useful information on this site?
A. Try google or this query: "http://codeforces.com/search?query=<what do you want>".

Q. Why are my comments / post empty?
A. If you used copy-paste, your comment may have some incorrect tags. Try to look at the HTML code of your message (button "< >") and erase all charset tags. If the system tells you "Rendering to html failed: ....", you used "\$" symbol. Codeforces supports

Unable to parse markup [type=CF_TEX]

formulas which are enabled by this symbol. Try to avoid it.

Q. Can I post a highlighted code sample?
A. Currently the best way is to submit the code to a service like codepad.org and post only links to the submit.

Miscellaneous


Q. I've found a bug! When I upvote a post, its rating increases by 2 points, but when I downvote a post, its rating decreases only by 1 point.
A. It's not a bug, it's a feature.






Полный текст и комментарии »

  • Проголосовать: нравится
  • +14
  • Проголосовать: не нравится

Автор slycelote, 14 лет назад, перевод, По-русски

A. Письмо

Чтобы найти наименьший прямоугольник, содержащий картинку, переберем все пары (i,j), для которых j-й символ в i-й строке равен '*', найдем минимальные и максимальные значения i и j среди этих пар. Искомый прямоугольник — [imin, imax] × [jmin, jmax].

Полный текст и комментарии »

Разбор задач Codeforces Beta Round 14 (Див. 2)
  • Проголосовать: нравится
  • +19
  • Проголосовать: не нравится

Автор slycelote, 14 лет назад, По-английски
Two parallels came into my mind:

1. Level of knowledge of a foreign language. Something like this:
Pre-intermediate -> Intermediate -> Upper-intermediate -> Advanced -> Fluent
There can be a 'preferred language' field in profiles, and then they will look this way:

Petr

  • User''s contest rating in Codeforces community Contest rating: 2046
  • Fluent in Java

2. Software release life cycle. It's pretty self-explanatory, I think:

Pre-alpha -> Alpha -> Beta -> Release Candidate -> Release
User's handle could look like this:
adamaxβ

Полный текст и комментарии »

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

Автор slycelote, 14 лет назад, перевод, По-русски

A. Бросок кубика

Пусть максимум из очков Якко и Вакко -- a. Тогда Дот выиграет, если выбросит не меньше a очков. Вероятность этого равна (6 - (a-1)) / 6. Поскольку a принимает всего 6 значений, ответы можно просто вычислить вручную.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +7
  • Проголосовать: не нравится