slycelote's blog

By slycelote, history, 9 years ago, In English

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!

Full text and comments »

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

By slycelote, 9 years ago, In English

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:

Full text and comments »

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

By slycelote, 10 years ago, In English

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

Full text and comments »

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

By slycelote, 11 years ago, In English

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> ());
	}
}

Full text and comments »

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

By slycelote, 11 years ago, In English

(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.

Full text and comments »

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

By slycelote, 14 years ago, In English

A. Almost Prime

This is a straightforward implementation problem: factor every number from 1 to n into product of primes and count the number of distinct prime divisors.

B. Regular Bracket Sequence

Read the string from left to right and calculate the balance of brackets at each step (i.e., the difference between the number of "(" and ")" characters written out). We need to keep this balance non-negative. Hence, every time when the balance equals 0 and we read the ")" character, we must omit it and not write it out. The answer to the problem is twice the number of ")" characters that we wrote out.

C. Parquet

We'll derive several necessary conditions for the parquet to be possible. If some of them is not fulfilled, the answer is "IMPOSSIBLE".
1. m*n must be even, because it equals the total area of the parquet, and the area of each plank is even.
2. Suppose m (the number of columns) is odd. Paint the living room in two colors — black and white — in the following way: the first column is black, the second one is white, the third one is black, ..., the last one is black. The number of black squares is n greater than the number of white squares. The planks 1x2 and 2x2 contain an equal number of black and white squares, so we must compensate the difference with 2x1 planks, and their number must be at least n/2. In this case we can parquet the last column with these planks, decrease b by n/2 and decrease m by one.
3. If n is odd, then by similar reasoning a ≥ m / 2.
4. Now m and n are even. A similar reasoning shows that the number of 1x2 planks used must be even, and the number of 2x1 planks used must be even. So, if a is odd, we decrease it by 1, and the same with b.
5. Now we must have mn ≤ 2a + 2b + 4c, because otherwise the total area of planks would not be enough.
6. If all the conditions were fulfilled, we can finish the parquet: divide it into 2x2 squares, and use one 2x2 plank, two 1x2 planks, or two 2x1 planks to cover each square.

D. Tickets

If we picture the graph of the number of 10-euro banknotes, it will be a broken line, starting at the point (0, k) and ending at the point (m+n, n+k-m). Exactly m segments on the line are 'going down', and other n segments are 'going up'. Hence the total number of possible graphs is C(m + n, m) (the binomial coefficient). We need to find out the number of graphs which don't go under the X axis. To do that, we'll calculate the complementary number: the number of graphs which go under the X axis, or, equivalently, intersect the line y=-1.

Here we'll use the so-called 'reflection principle'. Consider any graph that intersects the line y=-1, and take the last point of intersection. Reflect the part of the graph from this point to the end with respect to the line y=-1. We'll have a new graph, ending at the point (m + n,  - 2 - n - k + m). Conversely, any graph ending at this point will intersect the line y=-1, and we can apply the same operation to it. Hence, the number of graphs we're interested in equals the number of graphs starting at the point (0, k) and ending at the point (m + n,  - 2 - n - k + m). Let a and b be the number of segments in such a graph which go up and down, respectively. Then a + b = m + n, a - b + k =  - 2 - n - k + m. It follows that a = m - k - 1, and there are C(m + n, m - k - 1) such graphs.

So, the probability that the graph will go down the X axis is 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)). The answer to the problem is 1 - (m(m - 1)... (m - k)) / ((n + 1)(n + 2)... (n + k + 1)).

E. Multithreading

It's clear that we must have 1 ≤ w ≤ Σi ni. If this condition is true, we show how to achieve the desired result in the following cases:
1. N = 1, w = n1. Obvious.
2. N ≥ 2, w ≥ 2. For w = 2, the schedule is the following: 1, all loops of processes 3..N, n2 - 1 loops of the second process, 1, 2, n1 - 1 loops of the first process, 2. For w > 2, we just need to move several loops from the middle of the sequence to the end.
3. N ≥ 2, w = 1, and there exists an index i such that ni = 1. Then the schedule is the following: i, all loops of other processes, i.

Now we'll show that in any other case the result w is impossible. The case N = 1, w ≠ n1 is obvious. We have one more case left: N ≥ 2, w = 1, and ni > 1 for each i. Suppose that there exists a schedule which results in y = 1. Consider the last writing operation in this schedule; suppose it is executed by the process i. Then the corresponding reading operation should have read the value y=0. This means that there were no writing operations before. But this is impossible, since ni > 1, and this process executed ni - 1 read/write loops.

Full text and comments »

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

By slycelote, 14 years ago, translation, In English

A. You're given a string...


Iterate over all substrings, starting with the longest ones, and for each one count the number of appearances. The complexity is O(L4) with a small multiplicative constant.

Full text and comments »

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

By slycelote, 14 years ago, In English

(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.net/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.net/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.net/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.






Full text and comments »

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

By slycelote, 14 years ago, In English

A. Letter

To find the smallest rectangle containing the picture, iterate through the pairs (i,j) such that the j-th symbol in i-th line is '*'; find the minimum and maximum values of i and j from these pairs. The rectangle to output is [imin, imax] × [jmin, jmax].

Full text and comments »

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

By slycelote, 15 years ago, In English
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β

Full text and comments »

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

By slycelote, 15 years ago, In English

A. Die Roll

If the maximum of Yakko's and Wakko's points is a, then Dot will win, if she has not less than a points. So the probability of her win is (6 - (a-1)) / 6. Since there are only 6 values for a, you can simply hardcode the answers.

Full text and comments »

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