yeputons's blog

The revenge is mine after ten long years
By yeputons, history, 3 years ago, In English

At last!

The problem is 65A - Harry Potter and Three Spells, if you're curious.

Apparently, thinking before coding helps.

What is the longest it took you to upsolve a problem?

Full text and comments »

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

Is it legal to define global variable named "read" in C++?
By yeputons, history, 3 years ago, In English

I've bumped into this blog post by imtiyazrasool92 (unfortunately, it's already deleted due to downvotes). They've found out that simply declaring a global variable called read makes your program behave strangely on Codeforces: the outcome of 130645392 is RUNTIME_ERROR, Exit code is 2147483647, and here is the code:

#include <iostream>
int read;
int main(){
    std::ios_base::sync_with_stdio(false);
    std::cin >> read;
}

I was unable to minimize the example any further.

The original post was even more interesting: 130642683 is Accepted, but 130643108 is Runtime Error all of a sudden.

The compiler on Codeforces is G++17 9.2.0 (64 bit, msys2). However, I was able to reproduce the issue both on my local machine (g++ (Rev2, Built by MSYS2 project) 10.3.0) and the latest GCC on Godbolt as long as the -static key is used for compilation just like on Codeforces. Clang is also affected.

It looks like the read variable here replaces the standard Linux read function (which is emulated by msys2). Here is a symmetrical example:

#include <iostream>
int write;
int main(){
    std::ios_base::sync_with_stdio(false);
    std::cout << 10;
}

And here is one more (130646314), although now I at least get some warnings:

int malloc;
int main(){
}

a.cpp:1:5: warning: built-in function 'malloc' declared as non-function [-Wbuiltin-declaration-mismatch]
    1 | int malloc;
      |     ^~~~~~

My understanding is that all these examples invoke ODR violation, which makes the program ill-formed (invalid) without any requirements on the compiler to emit the error. However, I am not sure, so I asked on StackOverflow.

Any other ideas?

Full text and comments »

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

Debugging graphs with ease: experimental Visual Studio plugin
By yeputons, history, 6 years ago, In English

Hi everyone!

I'd like to present you a prototype of Visual Studio plugin which was developed by a student from my university as a coursework. Yielding floor to her:

GraphAlgorithmRenderer is an experimental Visual Studio extension for debugging and visualizing graph algorithms. It takes a description of graph nodes, edges and their properties, such as color and label, and renders a corresponding graph. The graph is refreshed automatically when you step in debugger. Graph config can be serialized to JSON and deserialized back.

Full text and comments »

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

Are Codeforces pages sometimes rendered blank during fast browsing with Firefox?
By yeputons, history, 8 years ago, translation, In English

In the last few weeks or even months I've noticed that my use scenario for Codeforces became broken. Here it is:

  1. Open the main page.
  2. Scan "Recent actions" for interesting posts.
  3. Open all of them in new tabs with mouse.
  4. Go and read posts and comments.

The problem is: approximately half of 5-10 opened tabs is rendered empty. Empty in the following sense: there is tab's title, one can see source HTML (e.g. the page is loaded), but the page itself is completely blank. DOM tree contains something (not too much), but <body>'s height is zero:

For comparison, here is the same page, rendered correctly (note that now we have several new scripts and a <div id="body">):

Steps to reproduce:

  1. Take Firefox on Windows. My version is 52.0.2 (32 bit). I was unable to reproduce the problem in Chrome.
  2. Take arbitrary ISP — I was able to reproduce the problem both directly and via encrypted proxy.
  3. You don't have to log in — I was able to reproduce the problem in a fresh Firefox session (firefox -P -no-remote and create a new profile; this guarantees no strange cookies on external websites). However, I was unable to reproduce the problem in "Private Browsing".
  4. Open the main Codeforces' page.
  5. Hold down Ctrl and click link to an arbitrary user's profile from "Top rated". Click it fast: 10-20 times during several seconds.
  6. Check all tabs one-by-one:
  • Expectation: after loading indicator stops spinning, page is rendered and I can see Codeforces' logo and user's profile.
  • Reality: some tabs, even after loading indicator disappears, remain completely blank.

I suspect that this is caused by some cookies set by either Codeforces or its analytics/like scripts (e.g. VK/Facebook).

Full text and comments »

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

Interning/working at Samsung?
By yeputons, history, 8 years ago, translation, In English

Hello everyone.

Is there anybody who interviewed/interned/worked at Samsung (Seoul or any other office) for software engineering-related positions? I think it's more probable to find such people among All-Siberian Open Olympiad in Programming participants, as Samsung sponsored it for some time.

If there is, would you mind sharing your experience or thoughts? Extra bonus points if you compare it with your European/American experience.

Full text and comments »

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

Online judge with IOI problem went public
By yeputons, 9 years ago, In English

Hello everyone.

Two years ago there was a post titled "Submitting IOI problems" and my comment there. I offered everyone to contact me via PM on Codeforces to get the access and be able to solve problems from past IOIs (starting with IOI 2003). What was important here is that PavelKunyavskiy and me took effort and made the system as similar to what was used on particular IOI as we could, including:

  1. Original tests from archives
  2. Tests grouping and correct subtasks scoring where applicable — you won't get 54 points if there are subtasks for 40 and 60 points — just like on IOI.
  3. Interactive problems with interactive I/O (say, "Aliens" from IOI 2007 or "Maintain" from IOI 2003)
  4. Partial scoring where you can get only a fraction of points per test, like "Reverse" from IOI 2003 or "Hotter Colder" from IOI 2010.
  5. "Encode-decode" problems, where your solution is executed several times in separate processes, like "Parrots" from IOI 2011.
  6. Open test problems where you submit answers only instead of solution, like "Forbidden subgraph" from IOI 2006 or "Maze" from IOI 2010.
  7. Graders like on IOI 2010 and further. Unfortunately, the "Black box" problem from IOI 2006 was also implemented as a problem with graders instead of running a real "black box" on our server which you can access remotely.
  8. "Odometer" problem from IOI 2012 where you had to submit a program on a specially invented language.

So far it was a closed judge available upon request only. As far as I remember, I've granted access to everyone who've asked — 150+ persons. Time flows and the judge eventually migrated to Yandex.Contest (the system used for Yandex.Algorithm) with help of lperovskaya. It still supports all of the above, but the registration is open for everyone and IOI 2015 is available there. Feel free to join!

Unfortunately, it's still a beta version and there are still some issues: no problem statements are visible in the interface, some labels may be in Russian only and graders for Pascal and Java may be non-working in some problems (C++ should work everywhere, though). Note that we use slightly different conventions for graders from what was on IOI (for the sake of consistency among all IOIs). You can download an archive with example solutions by clicking on the "Download" button right to the "Jury messages" link. If the button is not here, there is no archive with example solutions yet, but the format of graders should be very similar among all problems and we didn't change signatures of functions from IOI, so it should be fairly easy to "restore" the format.

I hope that will help all of you who are preparing for upcoming IOIs! By the way, if you have not advanced to IOI this year, I would highly recommend you to avoid reading several IOIs so you will have good problems preparing for IOI next year. It's hard to find good IOI-like problems.

Full text and comments »

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

What is the story behind your username?
By yeputons, 10 years ago, In English

I've just discovered this question on Quora: What is the story behind your username at CodeForces?. I guess it'd be pretty interesting to hear stories from top participants. For instance, my handle's history is already described there.

This blog is dedicated to everyone who don't have Quora account, so you can share your histories and comments here.

I personally would love to hear stories from tourist, rng_58 and YuukaKazami from current top-10.

Full text and comments »

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

APIO 2011 test data and reference solutions
By yeputons, 10 years ago, In English

Hello everyone.

Right now I'm settings up APIO 2011 contest for training purposes. It seems to me like test data (answers, to be precise) in problems 'Guess My Word' and 'Table Coloring' are broken. I have three solutions from three different people for the latter problem and they produce the same answers for tests 10, 12, 14, 16 and 18 — zero, while the reference answer is non-zero. For the 'Guess my Word' problem I have two solutions: one fast and one brute-force with memoization which I wrote by myself several minutes ago. These two solutions produce same output on tests 1-16, but they both produce 'No' on some test cases where official test data says 'Yes'.

Does anyone have information about validity of this test data or some solutions which I can test with too?

Thank you.

Full text and comments »

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

Testexe for testing systems: say 'no' to extra large static arrays!
By yeputons, 11 years ago, translation, In English

Everyone knows a problem with native executables on Windows: if it tries to allocate very large static arrays (or something similar that causes problems during the loading), then the testing system may mark the submission as 'it killed our system' and report nothing to the participant. Say, in Testsys it caused Failed To Test (and no feedback to the participant), on Codeforces it caused Denial of Judgement, and PCMS2 still has this problem. Example submission:

int data[(int)2.1e9 / sizeof(int)];
main() {}

If one is familiar with process creation on Windows, it's obvious what to do: try to run the solution right after compilation and report Compilation Error with report in case of invalid executable. It looks like noone except me have the time to do this and here is my utility, which already serves on Codeforces. If you have your own testing system, you're welcome to run this application after compilation to check an executable for validness (you can just copy-paste the code directly into your judging module, too). After that you will be able to report incidents to the user and drop hints about extra large arrays existance.

No user code is being running during the check: process is fully suspended by the OS after successfull loading and before any instructions are run (it's what the CREATE_SUSPENDED parameter is responsible for).

Full text and comments »

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

APIO 2012’s results
By yeputons, 13 years ago, In English

Does anyone know when the results of APIO 2012 will appear? Results of open contest were published several days ago, test data is available for two days already, but results are still 'TBA'.

Full text and comments »

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

Userscript for new comments walking in Codeforces' blog
By yeputons, 13 years ago, translation, In English
Hi everybody.
I'm tired for scrolling page to find a new comment and don't like "Recent actions". So, I wrote a userscript, which adds a "new comments navigate buttons" in the right of the window.
It works in Firefox (you need GreaseMonkey plugin) and Chrome. It also should work in Opera and some other browsers - I don't use any specific API.

You can install it here. If the only thing you see is javascript code it means that your browser doesn't support userscripts

You can report bugs, ideas and suggestions here.

UPD: now you can view parent comment if you hover over the "^" link. This link still works.

UPD2: repository on GitHub is available.

Full text and comments »

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

Tutorial for school regional team contest of Saratov
By yeputons, 13 years ago, translation, In English
You can leave your questions, suggestions and more beautiful in comments.

Problem A. Elevator


You can either check all four cases or notice, that if we consider front/back equal to 0/1 (b) and decrease a by 1, then a XOR b became the answer (0/1). Time and memory consumption - O(1).



Problem B. Quiz League


Just write one loop: while kth question has already been asked, increase k by one and if k > n let k = 1. Time and memory consumpiton - O(n).



Problem C. Winnie-the-Pooh and honey


One of the possible solutions is direct emulation. Winnie won't do more than 3n iterations (because he can use each jar more than three times). You can emulate each iteration in O(n) (just find maximum in array). Summary time - O(n2) ≈ 104 operations, memory consumption - O(n)

There is another shorter solution: let's notice that order of jars doesn't matter. Let's see how much honey from each jar will be eaten by Winnie and how much will be left to Piglet. If ai ≥ 3k then Winnie will leave ai - 3k kg of honey to Piglet. If ai < 3k then he'll leave only kg. Now solution is one loop. Time and memory consumption is O(n).

Full text and comments »

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