Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

By savkinsd2089, history, 12 hours ago, translation, In English,

Hi!

I'm glad to invite you to Codeforces Round #526, which will be held on Dec/10/2018 19:35 (Moscow time). The round will be rated for both divisions.

Problems were prepared by me, Dimon, maxim.shuklin, egor.lifar.

Thanks to ismagilov.code, Kuyan, 300iq, alexey_kuldoshin, Jatana for testing, arsijo and gritukan for helping us and MikeMirzayanov for the great Codeforces and Polygon platforms.

You will be given 6 problems in each division and 2 hours to solve them.

UPD:

The scoring distribution in Div. 1: 500-1000-1500-2000-2000-2500

The scoring distribution in Div. 2: 500-1000-1500-1750-2250-2750

Have fun & Good luck!

Read more »

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

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

SnackDown 2018 elimination round starts in ~8 minutes. Top 300 get T-shirts

Let's discuss the problems after the contest!

Read more »

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

By NeercNews, 3 days ago, translation, In English,

Hello friends!

text

This weekend, on 8-9th of December — St. Petersburg, Barnaul, Kremenchug, Tbilisi, Almaty and Sochi will host the XIX Russia Team Open High School Programming Contest. Competition will be attended by more than 250 teams. Contest is held for the first time in Sochi this year -Educational Center “Sirius” will host nine teams.

The main contest will start on 9th of December at 10:00. You can follow current results by the link. Link to the tasks will be able right after the start of the tour.

A mirror will be available on Dec/09/2018 11:05 (Moscow time) – this is for those, who are not a participant, but also want to solve interesting problems! Do not join our broadcasts if you plan to take a part in the mirror. We warn you that, because of spoilers. And, of course, do not open the problem conditions before the start of the round.

If you do not want to participate in a mirror, be sure to join our broadcasts — in video format from the ICPCLive team and in text format in our Telegram-channel!

And if you want to come to the Russia Team High School Contest in St. Petersburg as a guest – just fill in the guest form and get your badge at the registration!

Our friend ismagilov.code has a post – follow this link to see a large set of commands with their total rating. Thank you for interesting information!

And please welcome some teams that stand a good chance to become Cup winners:

Team City Participant 1 Participant 2 Participant 3 Rating
Мертвые души Kazan + SPb scanhex gainullin.ildar Крамник Сергей 5641
Вова спит дома Moscow voidmax aleksandr2754 Jatana 6854
Чудо Зверята! Almaty YaDon4ick Batrr ruslanjan 6727
danya.smelskiy Kremenchuk Sonechko zubec Nasic_number_one 6701
Проблемы с Поллардом? SPb, Vsevolozhsk Qlukva andrey_efremov Forestryks 6660
Komarovi+Mziuri 1 Tbilisi nikabb temotoloraia baqargam 6597
Пурпурный виноград Moscow savkinsd2089 Kuyan Dimon 6558
Пыльная Испания Chelyabinsk Mlxa sava-cska liriKl 6529

Read more »

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

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

It's the happy birthday of our beloved Dr. Bill Poucher!

Happy birthday sir.

You are a legend.

<3 <3 <3

Read more »

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

By mkisic, history, 4 hours ago, In English,

Hi!

There are a lot of competitive programming coaches who offer online lessons. What do you think, should Codeforces create some subpage where coach can provide information (like prices) about himself?

In chess world, popular sites have pages about that. For example,

https://lichess.org/coach

https://www.chess.com/coaches

Read more »

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

By hmehta, history, 30 hours ago, In English,

Topcoder SRM 743 is scheduled to start at 12:00 UTC -5, December 9, 2018. Registration begins 24 hours before the match and closes 5 minutes before the match begins.

Problem Writer: boba5551

This is the second SRM of Stage 2 of TCO19 Algorithm.

Stage 2 TCO19 Points Leaderboard | Topcoder Java Applet | Next SRM 744 — December 14

Hope to see most of you competing! All the best!

Read more »

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

By Chilli, history, 5 months ago, In English,

One of my favorite implementations of segment trees has always been "Easy and Efficient Segment Trees, by Al.Cash. I used to dread segtree problems, but after reading that blog post and adapting a super simple implementation I've gotten a lot better with them. However, there are some types of segtree that you can't implement in that fashion, namely dynamic segtrees and persistent segtrees. See here for criticism. With the advent of policy hash tables, however, one can now implement dynamic segtrees in Al.Cash's style with somewhat comparable performance to a custom dynamic segtree.

Standard segtree

This is how a standard segtree looks like. You can set a single element, and query for ranges. It's nice and simple, and I think it's a great implementation.

int N;
int seg[2 * MAXN];

void modify(int p, int val) {
    for (seg[p += N] = val; p > 0; p >>= 1)
        seg[p >> 1] = seg[p] + seg[p ^ 1];
}

int query(int l, int r) {
    int res = 0;
    for (l += N, r += N; l < r; l >>= 1, r >>= 1) {
        if (l & 1)
            res += seg[l++];
        if (r & 1)
            res += seg[--r];
    }
    return res;
}

Dynamic Segtree

However, say your underlying array had 1e9 possible locations, but it only contained 1e5 elements. For example, take a look at this post. Obviously, you can't store all 2e9 elements in your segtree, so what should you do? Here's one solution, replace the array with a hash table. However, as adamant mentions, unordered_map has too much overhead. We'll be benchmarking against the dynamic segtree provided here. I'll also be using a custom hash function. So to be clear, the implementation now looks like:

Code

And benchmarking it with 1e5 random insertions and 1e5 random queries.

pointer: 0.171485
unordered_map: 2.0646

Wow. The unordered_map is nearly 12x slower. That's not really feasible for a lot of contests. What if we replace it with a policy hash table, though?

Code
pointer: 0.202186
policy hash table: 0.384312

Only a 2x decrease in speed. That's already very feasible. However, one might notice that since maps in C++ create elements if you try to access a key that doesn't exist, we're creating a lot of useless elements. Thus, we can simply wrap a check to make sure the element is in the array before we try to access it

EDIT: Updated with dalex's optimization.

gp_hash_table<ll, ll, chash> seg;

ll get(ll x) { return (seg.find(x) == seg.end()) ? 0 : seg[x]; }
void modify(ll p, ll val) {
    for (seg[p += N] = val; p > 0; p >>= 1) {
        seg[p >> 1] = get(p) + get(p ^ 1);
    }
}

ll query(ll l, ll r) {
    ll res = 0;
    for (l += N, r += N; l < r; l >>= 1, r >>= 1) {
        if (l & 1)
            res += get(l++);
        if (r & 1)
            res += get(--r);
    }
    return res;
}

Results (averaged over twenty runs):

2e5 insertions and 2e5 queries

pointer: 0.44085
policy hash table: 0.57878

1e5 insertions and 1e5 queries

pointer: 0.19855
policy hash table: 0.29467

1e4 insertions and 1e4 queries

pointer: 0.014
policy hash table: 0.027

So while we're nearly twice as slow with 1e4 elements and 1e4 queries, we're actually only 30% slower with 2e5 insertions and 2e5 queries.

One more thing. While I'm giving numbers like "30% slower", that's a little bit misleading. If we break down the numbers between insertion/querying, we see this:

2e5 insertions and 2e5 queries Queries:

pointer: 0.41625
policy hash table: 0.15627

Insertions:

pointer: 0.1367
policy hash table: 0.42619

1e4 insertions and 1e4 queries Queries:

pointer : 0.094
policy hash table: 0.007

Insertions:

pointer : 0.0045
policy hash table: 0.0191

So as we see from this more granular breakdown, the Policy Hash Table implementation is actually ~3x faster at querying than the custom implementation, while the custom implementation is roughly ~3x faster at inserting elements.

TL;DR: Using policy hash tables is an extremely easy and fairly efficient method of implementing dynamic segtrees.

Read more »

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

By randHandle, history, 7 hours ago, In English,

Hi, I came across this problem where you are given an array a, your task is to convert it into a non-increasing form such that we can either increment or decrement the array value by 1 in minimum changes possible.

One approach that I could think of using dp where dp[i][j] stood for minimum number of changes for first i elements if we use the largest j heights in the original array.

This approach has time complexity of O(N^2) and space complexity of O(N). But there seems to be better approach as mentioned in this blog https://www.geeksforgeeks.org/minimum-incrementdecrement-to-make-array-non-increasing/. But I was neither able to understand the approach described nor the code given.

But I checked the correctness of the code in the blog against my dp code. Both of them were producing same results. So if anyone could let me know how the O(N*log(N)) solution works that would be great.

Read more »

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

By helium99, history, 2 days ago, In English,

Hi everyone! I have a testcases include a lot of tests (example 1.in/1.out,...). But I do not know how to write a script (or a program with C++ or any language) to test my testcases. If you know how to do it, hope you will help me! Thank you.

Read more »

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

By NuteIlA, 11 hours ago, In English,

Hello World!

Read more »

Tags c++
 
 
 
 
  • Vote: I like it  
  • +4
  • Vote: I do not like it