By erdos, history, 3 days ago, In English,

HackerCup R1 starts in ~24h (July 21 12:00 PET).

Let's discuss the problems after the contest!

Read more »

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

By MikeMirzayanov, 42 hours ago, translation, In English,

Hello, Codeforces.

This is a short blog to introduce you recent updates in Testlib and Polygon.

Testlib

Generate a Permutation

Now, you can easily generate a permutation with codes like this:

Code Result
vector<int> p = rnd.perm(n); Generates 0-indexed permutation of size n
vector<int> p = rnd.perm(n, 1); Generates 1-indexed permutation of size n

Function println

Now, you can easily print space-separated lines in a generator. A println uses cout, thus prefer faster method if you print huge data.

Some examples:

Code Result
println(5); Print 5 and line break
println(1, 2, 3); Print 1 2 3 (three space separated integers) and line break
println("one", "more", 5.5); Print one more 5.5 (three space separated items) and line break
vector<int> a; ...; println(a); Print vector a (separate elements with spaces) and line break
vector<int> a; ...; println(a.begin(), a.end()); Exactly the same as above
string b[5]; ...; println(b, b + 5); Print array b (separate elements with spaces) and line break

Here is the example of a generator to print a permutation:

#include "testlib.h"

using namespace std;

int main(int argc, char* argv[]) {
    registerGen(argc, argv, 1);
    
    int n = atoi(argv[1]);
    println(n);
    println(rnd.perm(n, 1));
}

Function readInts and similar

Just as a reminder. Use functions readInts/readLongs/readStrictDoubles or readTokens/readLines in a validator to read and validate a sequence of values. To read a size of an array and array itself, use:

int n = inf.readInt(1, 200000, "n");
inf.readEoln();
inf.readInts(n, 1, 1000000, "a");
inf.readEoln();
inf.readEof();

Polygon

Example Problems

I've introduced three example problems. Each Polygon user has READ-access to them. Please, use them as examples how to write a problem in Polygon. They are:

  • example-a-plus-b: simple A+B problem
  • example-almost-upper-bound: simple problem to illustrate non-standard checker (always consider to use readAnswer function like in the example), generators and stress tests
  • example-interactive-binary-search: simple interactive problem on a binary search

Other Small Fixes

  • Allow to upload files (for example, images) as a contest property/file to use them in the statements.ftl. File names should start with 'statements-'.
  • API has been improved to support general description, general tutorial, tags, test groups and points.
  • Show problem ID on the summary box (on the righmost top block).
  • Replace UTF-8 typographic characters to their ASCII equivalent (for example, replace em dash — with ---).
  • Caching issue has been fixed. Previously, it could show RJ on tests even if the reason has been fixed.

Thanks to fcspartakm for implementing most features in Polygon.

Read more »

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

By Chilli, history, 3 days ago, In English,

TL;DR

The Policy Hash Table has 3-6x faster insertion/deletion and 4-10x increase for writes/reads. As far as I can tell, there are no downsides. The policy hash table (specifically the open-addressing version), beats out unordered_map in all my benchmarks.

Background

I've often been irritated by how slow unordered_map is in C++. Too often, I have something that runs fast enough in terms of complexity, but the constant factor from unordered_map slows down the solution too much. Yesterday though, after using the useful order statistics tree from https://codeforces.com/blog/entry/11080, I was curious if there were any other useful data structures hiding in the Policy STL. And lo and behold, I found a hash table.

Benchmarks

Well, enough backstory, let's look at some numbers. All benchmarks below are compiled with C++14 -O2.

unordered_maplinear insertion:                                  0.689846
cc_hash_tablelinear insertion:                                  0.408233
gp_hash_tablelinear insertion:                                  0.256131

unordered_maplinear read/write:                                 1.69783
cc_hash_tablelinear read/write:                                 0.202474
gp_hash_tablelinear read/write:                                 0.26842

unordered_maprandom insertion:                                  2.90184
cc_hash_tablerandom insertion:                                  3.15129
gp_hash_tablerandom insertion:                                  0.56553

unordered_maprandom read/write:                                 2.02336
cc_hash_tablerandom read/write:                                 0.333415
gp_hash_tablerandom read/write:                                 0.403486

While for linear insertions, the policy hash table gives modest improvements, the policy hash table blows the unordered_map out of the water when it comes to reads/writes. These are order of magnitude improvements that make hash tables usable when they previously weren't. "Official" benchmarks done by the DS authors can also be found here

Example

Benchmarks of course, don't always reflect the real world. So here's an example of it allowing a solution to be accepted that TLE's with unordered_map.

Example problem (5000 ms time limit)
Solution with unordered_map: (TLE on test case 8)
Solution with policy hash table directly substituted in: (TLE on test case 26)
Solution with unordered_map, rewritten to not use clears: (TLE on test case 26)
Solution with policy hash table and rewritten to not use clears: (AC with max time of 3180 ms)

Usage

To use this data structure:

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
gp_hash_table<int, int> table;

From there, the API seems almost exactly the same.

Defeating Anti-Hash tests

One weakness of hash tables is that mean people can find hash collisions offline and blow up the complexity of your hashmap. In my opinion, the easiest way of solving this is below. There's no need to define your own custom hash function.

const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
struct chash {
    int operator()(int x) { return hash<int>{}(x ^ RANDOM); }
};
gp_hash_table<key, int, chash> table;

Why is it so much faster?

See my comment here

A better hash function

There is one issue with using policy hash tables as is. The default hash function for numerics in C++ is just the identity. This is especially problematic for using hash tables for something like a fenwick tree, especially since the default bucket structure for policy_hash_tables is based of powers of 2 and not primes. If you're using policy hash tables for fenwick trees, you have 2 options. 1. Choose to use prime table sizes, as done here. 2. Choose a better hash function for integers, as done here.

Thanks to adamant for his post that revealed to me the existence of policy data structures, and thanks to ed1d1a8d for the discussion.

PS: In other posts for unordered_map, I've seen people claim that reserve and max_load_factor could increase performance drastically. They didn't seem to do much for me. However, if you want to do something similar for these hash tables, check out the example here

Code for the benchmarks can be found here

EDIT: I realized that gp_hash_table is the way to go, not cc_hash_table. gp_hash_table sacrifices ~10% reading/writing speed to gain 3-6x in insertion/deletion/clearing. I updated the post to reflect the new numbers.

Read more »

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

By PedroBortolli, history, 19 hours ago, In English,

Hello Codeforces community!

Me and my friend nakamura developed CFStats: a website that allows stats comparison between 2 Codeforces handles.

The comparison includes:

  • Rating graph comparison over the time (just like in Codeforces, but for 2 users)
  • All attempted (but unsolved) problems by each handle
  • Problems solved by tag by each handle
  • Unique problems solved by each handle
  • Problems that both handles solved
  • Contests that each user participated
  • Contests in which both handles participated (and their respective positions)

And we will be more than glad to introduce more features! We are open for your suggestions :)

Also, CFStats lets you create a profile. There, you can save:

  • Codeforces friends (so you can easily compare yourself to them with one click)
  • Problems to solve later
  • Contests to solve later

The advantage of saving such things is that every time your profile is updated a message will appear next to a solved problem/contest telling you it has been solved so you can delete it.

The code is available on GitHub!

We hope that CF Statistics will be useful for someone! If you have any bug report we will appreaciate it!

Read more »

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

By adamant, history, 45 hours ago, In English,

Hi there! Imagine you're participating in codechef long challenge and you see a problem from chemthan asking you to calculate some sums of powers like 1p + 2p + ... + np for all p from 0 to k. You immediately understand what's going on here and take Faulhaber's formula from your wide pants, do ya? Just take a look at it!

Beautiful, right? Wrong! This formula is dumb and it's hard to understand and remember! Why would you ever think about Bernoulli's number on any contest which lasts less than a week? And what the hell are those Bernoulli numbers?! Here is what you should do:

Let Sp = 1p + ... + np. Consider its exponential generating function (EGF):

Now you can simply find S0, ..., Sk by finding inverse series for and multiplying it with . Enjoy your power sums without Stirling and/or Bernoulli numbers!

Exercise: Solve this problem in .

P.S. Yes, you basically perform the same calculations as in Faulhaber's formula, but now you hopefully understand what you're doing.

Read more »

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

By wellaCoder, history, 2 hours ago, In English,

I am having trouble solving the problem given in the link below. Since the editorial is in Japanese, I cant understand it and Google translate is not much of help either.

Link to problem — Problem D: Island Wars

Looking forward for explanation or intuition to how to approach this problem.

Read more »

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

By AkshajK, history, 10 hours ago, In English,

Hey all,

I spent some time writing a textbook on how to efficiently convert between different bases, and thought it may be useful to those of you who are learning this for the first time.

Link: https://drive.google.com/file/d/12CeDNZO_trww-ZtGWMdSUCrhN8kcbi2U/view

Read more »

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

By Gassa, history, 3 days ago, translation, In English,

Hi all!

I invite you to take part in Codeforces Marathon Round 2. The contest will start on Tuesday, July 24, 2018 at 15:00 MSK, and will last for 7 days. There will be one problem based on game mechanics of a couple of board games for children. The problem most likely does not have a fast and full solution. So the solutions will be given scores, and the winner will be the one who gets the highest total score.

The contest will be unrated because the problem is considerably different from the problems of rated rounds.

During the time of the contest, the solutions will be checked on examples and preliminary tests. After the contest is over, the final solution of each contestant will be checked on the final test set, and the total score for this test set will determine the final scoreboard. The contest will take place on Codeforces platform and is supported by the Community Of Master Programming at St. Petersburg State University (link in Russian) and 90.01 Group.

The Codeforces platform has seen only few marathons so far. So, if something breaks, don't be upset, just write about it, and we will try to fix it.

Good luck in the contest!

Read more »

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

By kingofnumbers, 46 hours ago, In English,

Hello CodeForces Community!

We’re back with a new and exciting set of coding challenges with the July Cook-Off 2018 sponsored by ShareChat. Plus there are some exciting job/internship opportunities by ShareChat for participants. More details on the July Cook-Off contest page here:

Looking forward to seeing your participation in yet another exciting monthly contest! Joining me this time on the problem setting panel are:

  • Problem Setters: kefaa (Kirill Gulin), kingofnumbers (Hasan Jaddouh)
  • Problem Tester: isaf27 (Ivan Safonov)
  • Editorialist: vijju123 (Abhishek Pandey)
  • Statement verifier: xellos (Jakub Šafin)
  • Russian Translator: Fedosik (Fedor Korobeinikov)
  • Mandarin Translator: huzecong (Hu Zecong)
  • Vietnamese Translator: (VNOI Team)

Contest Details:

Time: 22nd July 2018 (2130 hrs) to 23rd July 2018 (0000 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone

Contest link: codechef.com/COOK96

Registration: You just need to have a CodeChef handle to participate. For all those, who are interested and do not have a CodeChef handle, are requested to register in order to participate.

Prizes: Top 10 performers in Global and Indian category will get CodeChef laddus, with which the winners can claim cool CodeChef goodies. Know more here: https://discuss.codechef.com/questions/51999/how-do-i-win-a-codechef-goodie
(For those who have not yet got their previous winning, please send an email to winners@codechef.com)

Good Luck!

Read more »

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

By Petr, history, 26 hours ago, In English,
 
 
 
 
  • Vote: I like it  
  • +52
  • Vote: I do not like it