yak_ex's blog

By yak_ex, 13 years ago, In English

This is my second user.js script for Codeforces. If you install this script (Updated: 1.6: 2015/05/05), you can see standings like as follows:

You need to wait for seconds until standings are colorized. The order and decoration are set by my arbitrary feeling. If you want to change them, please edit the script directly. It is quite easy. The latest code is also at github.

On my environment, the user.js script works with the following browser:

  • Firefox 3.6.17 with Greasemonkey 0.9.2
  • Opera 11.10
  • Chrome 12.0 (This is a development version but I think stable versions also work as well.)

Updated (0.02):

Now this script is applicable for division-specific standings and room standings. For room standings, I would be glad if you make some comments...

New feature is added. If you click a colored cell, tiny red triangles appear at the top-left corners of the cells colored in the same way. The following example is the case for clicking "Java". Clicking a marked cell, the marks disappears. It is not necessary to click cells in the top table. Cells in the actual standings table are also clickable. To clear mark, it is not necessary to click the same cell when marking. To click a marked cell is enough.

 

Updated (1.1):

Added OCaml and Scala support. This is just an updated thing. The reason why version jumps up is because Chrome recognizes version 0.0x as 1.0 and rejects update prior to 1.1.

Updated (1.2: 2012/06/05):

Record marked languages into cookie. So, they are persistent, at least, between reloads. The configuration is shared by all standings in a domain (e.g. www.codeforces.com). Thanks to suggestion by iTwin.

Updated (1.3: 2012/06/05):

I didn't notice the comments that Java 6, Java 7 and Perl are not highlighted. Now, they are highlighted.

Updated (1.4: 2013/05/07):

Add new languages (Python -> Python 2 and Python 3, C# -> Mono C# and MS C#, D, and Go).

Updated (1.5: 2014/06/01):

Add new languages (Java 8 and JavaScript).

Updated (1.6: 2015/05/05):

Add new languages (GNU C++11 (unified with GNU C++0x), GNU C11 and PyPy (unified with 2 and 3)).

Full text and comments »

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

By yak_ex, 13 years ago, In English

We can view friend standings and we can view rating history graph for individual. Did you want to view rating history graph with friends? At least, I wanted.

Rating history graph on Codeforces uses flot jQuery plug-in and the plug-in support multiple data sequences. Therefore such functionality can be easily implemented.  If many Codeforces users want, the functionality will be integrated by admin, hopefully.

So, I made user.js script (v1.3 2015/05/05) to show usefulness of the functionality. The latest code is also at github. [Updated: v0.02] Y-axis is adjusted when higher rating is shown, and message box appears when data can't be obtained properly. [Updated: v0.03] While you log-in, your rating graph appears in any profile page initially. [Updated: v1.2] Red dots for the highest ratings are kept and autocomplete for account names is added.

Please note that this is an experimental script and I am just a newbie for user.js script. On my environment, the user.js script works with the following browser:

  • Firefox 3.6.16 with Greasemonkey 0.9.2
  • Opera 11.01
  • Chrome 10.0
Usage is as follows:
  1. Install user.js script. This procedure depends on your environment. Please consult manual for your using software.
  2. Go to a profile page. It is not necessary to be yours. [Updated: v0.03] If you logged-in and go to a profile page other than yours, you can see a graph with your rating graph, like shown as 6,  without the following procedure. To be precise, an original graph is shown at first and updated after a while.
  3. Click legend part, then prompt is shown.

  4. Enter space-separated accounts you want to view with the account of the profile page, and click OK. [Updated: v1.2] If you type more than or equal to 3 characters, autocomplete is triggered like "Find user" feature.

  5. Wait seconds.
  6. Rating graph is updated. Note that the legend moves to bottom-right.

By clicking OK with empty value at prompt, rating graph goes back to original state.
[Updated: v0.03] If you logged-in, your account is entered as default value, except for your profile page. If you want to see an original graph, you need to clear the value and click OK.
Clicking cancel at prompt, rating graph is unchanged.


I hope you enjoy it!

Full text and comments »

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

By yak_ex, 13 years ago, In English

Updated: Add note for Cygwin environment.
Updated: Add result on FreeBSD 

In programming competition such as Codeforces, reading a large number of inputs is somtimes required, for example, 1500*1500 integers in Codeforces Beta Round #43 Problem E. I used iostream(cin) in the competition and got TLE. After the competition, I saw some comments that cin caused TLE. After I replaced cin with scanf, I got AC. So, it is said "For large input, use cstdio instead of iostream." However I believe C++ users want to use iostream. Can't we avoid the guideline?

Short answer:

I found one promising way. Unfortunately, it is applicable not to VC but to gcc. Call std::ios_base::sync_with_stdio(false) at the beginning of your code. Here is the graph to show performance comparison among iostream with the call, without the call and cstdio, in my local environments. [Updated: NOTE that File I/O on Cygwin is generally very slow. Therefore, the effect is overestimated in graph on Cygwin environment.]

X-axis shows the number of inputs and Y-axis shows seconds to read inputs. The scale of Y-axis is different between graphs.

The summary of my local environment is as follows:

  • Cygwin
    • CPU: Core2Duo T7600 2.3Ghz
    • RAM: 4GB
    • OS: Windows XP SP3
    • Compiler: gcc 4.3.4 on Cygwin 1.7.7
  • FreeBSD
    • CPU: PentiumM 1.3GHz
    • RAM: 1GB
    • OS: FreeBSD 8.1-STABLE
    • Compiler: gcc 4.2.1

Target source code is here (at codepad.org).

Though I don't know the precise effect in the judge environment, I can get AC with iostream, at least, for Codeforces Beta Round #43 Problem E. NOTE that the effect of the call depends on implementation of C++ standard library. For example, there is no significant difference for VC++.

Short explanation:

Calling sync_with_stdio(false) may improve performance. What is the actual effect of the call?

The standard (ISO/IEC 14882:2003) says:


27.4.2.4 ios_base static members
bool sync_with_stdio(bool sync = true);
Returns: true if the standard iostream objects (27.3) are synchronized and otherwise returns false.
The first time it is called, the function returns true.

Effects: If any input or output operation has occurred using the standard streams prior to the call, the effect is implementation-defined. Otherwise, called with a false argument, it allows the standard streams to operate independently of the standard C streams.


This means that synchronization with standard C stream is required without the call. In libstdc++ (C++ standard library used by g++), this flag switches iostream object's underlying buffer between stdio_filebuf and stdio_sync_filebuf. stdio_sync_filebuf has little buffering by itself and delegate almost all operation to cstdio. See also libstdc++ manual page.

For programming competition, there seems to be little use of mixture of cstdio and iostream. Thus, I recommend that you include the call in your code template. :p

Full text and comments »

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

By yak_ex, 13 years ago, In English

First, I am not good at statistics. Therefore, the following article may include incorrect description. OK?

In the comments for the previous article, rating system was mentioned:

Enhancements of Elo rating system is used by TopCoder and Codeforces. TopCoder uses normal distribution. On the other hand, Codeforces uses logistic distribution.

In Elo rating system, expected score, that is probability of winning plus half probability of drawing, is assumed. The expected score is described by ratings and this is (one of) the formula using different distribution between TopCoder and Codeforces. So, I am interested in the actual result.

This scatter chart shows rating difference of two participants and probability that the participant having higher rating gets higher score. It is calculated as follows:

  1. For all not-team contests, any pair of participants is chosen.
  2. For all pairs, difference of ratings before the contest is calculated, ranks in the contest is compared and the result of comparison is classified to win, draw or lose.

"Logistic" is calculated by the formula (RB-RA means negative of rating difference and EA means expected score):

 

"Normal" is calculated by the formula:

 
μ is 0 and σ is adjusted to pass through the point (x, EA) = (400, 10/11).

According to the chart, it seems that both of distribution does not fully capture the characteristics of the actual curve and that normal distribution is near form the actual curve though it is little difference..


Full text and comments »

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

By yak_ex, 13 years ago, In English

I created 3 charts regarding rating distribution in Codeforces.

[Updated] Slightly change chart 2 and 3 to show rating colors.

  1. Rating distribution in Codeforces

    This chart is rating distribution in Codeforcers similar as one shown in TopCoder profile.
    Purple markers and lines show cumulative rate.

  2. Coderforces vs TopCoder in Japanese participants

    This scatter chart shows Codeforces ratings and TopCoder ratings of who met the following conditions:

    - has the same handle name both in Codeforces and TopCoder.
    - is listed in Japanese TopCoders
    - participates more than or equal to 5 times both in Coderforces and TopCoder

    There are 56 samples. Correlation coefficient is 0.87.
    Of course, even though they have the same handle names, they could be different person. There should be who uses different handle name between Codeforces and TopCoder. So, this chart is far from complete. However, it could show rough image.

  3. Codeforces vs TopCoder

    This scatter chart shows Codeforces ratings and TopCoder ratings of who met the following conditions:

    - has the same handle name both in Codeforces and TopCoder.
    - participates more than or equal to 5 times both in Coderforces and TopCoder

    There are 427 samples. Correlation coefficient is 0.82.
    The note for 2nd chart is also applicable to this chart.

Full text and comments »

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