By Warawreh, 3 days ago, In English,

Hi, Everyone!

At Jan/20/2019 15:05 (Moscow time) will start Codeforces Round #533 (Div. 2). Round will be rated for second division (rating below 2100). As usual, participants from the first division can participate in the contest out of competition.

The round will consist of 5 problems in which you will be helping some of my friends and you will be given two hours to help them.

I would like to thank MikeMirzayanov for the Codeforces and Polygon platforms, _kun_ for round coordination and help with preparation. Also thanks to V--gLaSsH0ldEr593--V, Aleks5d,Nebuchadnezzar, Arpa, mohammedehab2002 and osaaateiasavtnl. for help with preparation and testing round.

As usual score distribution will be announced shortly before the contest.

Good luck!

UPD1: I'll be on the Discord channel after the contest, so we will be able to discuss the problems.

UPD2: Score distribution : 500-1000-1500-2000-2500

UPD3: The Editorial is ready.

Read more »

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

By Warawreh, 23 hours ago, In English,
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...

Read more »

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

By Errichto, 26 hours ago, In English,

Hi. I'm finally done with organizing Algorithmic Engagements, and I have time to go back to my streams!

Other Twitch programming streamers usually just do their job/project and they stream that. I'm going to do a similar thing. So, apart from my lectures and problem-solving streams, I will do a weekly longer stream, maybe around 6 hours.

My first Boring Programming Stream will be on Wednesday Tuesday (10am to 4pm CET, youtube link with countdown) and some of the things I might do are:

  • Writing editorials for my old problems.
  • Adding timestamps to my lectures on Youtube.
  • Planning the next lecture (or Facebook posts).
  • Reading the "Segment tree beats" blog (I know that tree, but I've never read examples and tasks given there).
  • Learning how to edit videos.
  • Reading Codeforces comments and maybe helping someone with a problem.
  • Learning how to use OneNote for drawing.
  • Choosing graphics (banner and thumbnails) for my channel.
  • Answering people's questions and comments.

This is something that I would do anyway, and it isn't confidential (unlike preparing problems), so I can stream it and allow people to hang out with me. Feel free to suggest something via discord or in the comments below this blog, but please notice that I will mainly do things that I need/want to do.

Cheers.

My Youtube channel: https://www.youtube.com/channel/UCBr_Fu6q9iHYQCh13jmpbrg.
I will stream on Twitch at the same time: https://www.twitch.tv/errichto.
Competitive Programming Discord: https://discordapp.com/invite/UzaURu7.

Read more »

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

By Alekhine, 4 days ago, In English,

CodeChef January Cook-Off starts in ~72h (Sunday, 20th January, 2019 at 21:30 IST). As ussual you will have 5 puzzles to solve in 150 minutes.

The character of the contest is Ada — the most intuitive girl I have ever met.

I challenge top coders to get full score in topcoder time.

By the way, the contest clash with the north regional junior chess championship of my country, so to me seems like a notorious coincidence.

good fun and have luck!

Contest log:

  • -24:00:00. Pran found a corner case on ADAROKS that I didn't contemplate, We fixed our solutions ad added more data.
  • 00:05:45. 28 acs for ADASCOOL in div1 and 14 in div2, Atreus is leading in div1.
  • 00:15:00. Div2 users found the cakewalk problem, stefdasca is leading in div2. In div1 lhic solved ADAMTR, his solution is similar to tester, I used 2-SAT as a blackbox.
  • 00:40:00. Internal Server Error :( now we know they upgraded their nginx to 1.4.7.
  • 00:43:00. CodeChef is up again, moreover Saiphani724 solved ADAMTR and is leading in div2. Pran predicts 4 perfect scores in div1, I predict 10.
  • 01:00:00. KrK solved ADAPWNS, now he is first and lhic is second.
  • 01:12:00. lhic aced ADAFUN, but he is still second because he didn't solved ADAPWNS, the problem is a trie dp, so its kind of standard.
  • 01:20:00. I noticed that my countrymate The_Blitz is participating in div2. It seems that having a chess handle is not helping him in the contest.
  • 01:32:00. uwi only solved 2 problems, did he gave up the contest after the server down?
  • 01:40:00. yashChandnani solved ADAFUN, now he is first!
  • 01:44:00. raveman solved ADAROKS, the top of the scoreboard in div1 is changing a lot!
  • 01:54:00. KrK solved ADAFUN and took the lead again, however I think raveman will winn, because he already solved ADAROKS which is harder.
  • 02:10:00. uwi is still on board it seems he had a hard time with ADAROKS, his solution fails on a case added by the tester (uwi, complain with pran), also I noticed that the educational hero pikmike is taking part in the contest, he managed to solve ADAPWNS, and is in the top 20.
  • 02:21:00. I bet raveman will winn, Pran bets on lhic.
  • 02:30:00. No participant got perfect score. Congrats to the winners!

Div 1:

 KrK

 lhic

 raveman

Div 2:

 Saiphani724

 andrew_ucla

 stefdasca

I'll add some hints for solutions in my blog: https://aleigorithms.wordpress.com/2019/01/17/codechef-january-cook-off-2019/

Read more »

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

By McDic, 3 hours ago, In English,

Hello. I am using Polygon to prepare problems.

This is my generator below:

#include <iostream>
#include "testlib.h"

long long int max2(long long int a, long long int b){
	return a>b ? a : b;
}

long long int ten(int x){
	long long int s=1;
	for(int i=0; i<x; i++) s *= 10;
	return s;
}

int main(int argc, char* argv[]){
	registerGen(argc, argv, 1);
	
	std::cout << rnd.next(1LL, atoll(argv[1])) << " ";
	std::cout << rnd.next(1LL, atoll(argv[2])) << " ";
	std::cout << rnd.next(1LL, atoll(argv[3])) << " ";
	std::cout << rnd.next(max2(1, atoll(argv[4])/10), max2(100, atoll(argv[4]))) << std::endl;
}

Is there any wrong thing? It always verdict FL in invocation and tests. Thank you for reading this.

EDIT 1 This is the log occurs when I try to generate inputs. ERROR: Unexpected verdict Can't prepare input file 'C:\Contesters\Work\invoker-prod\work\polygon2\34b2efc622c48530be13ce1989b01907\check-bc2d7412ca16433314f5a03914c1d409\run\input.fd0138e687.txt'.FAILED. Input:

Read more »

 
 
 
 

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

By pope1234, history, 6 hours ago, In English,

Hola amigos..!
Tighten your seatbelts and be prepared with all your skillset ‘Coz it’s high time for a Code-storm where all the champions will thrive but only a few will survive. So here comes the very first edition of “CodeCharades”, an online competitive coding championship presented by Codechef Chapter: IIT Patna, in association with ANWESHA & CodeChef as coding partner..! And yes, the winners will be rewarded with amazing prizes worth ₹5k and 250 codechef laddoos(for top 3 partcipants).


Date and time: 21st Jan, 2019, 9PM-11PM.


The contest will be hosted on codechef.com .


P.S. We won't go easy on you!!!

Follow this link to register yourself for the contest... click here

!! FOR MORE INFORMATION !!
Follow this link for facebook page...
https://www.facebook.com/IITPCHEF

Follow this link for contest-
https://www.codechef.com/COCS2019

Read more »

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

By hars123, history, 26 hours ago, In English,

I have tried this problem a lot and also figured out the states. I am trying to build up a 2D dp table dp[i][j] where first i-1 signs are satisfied and last number in the sequence is j. can someone help me in finding out the transitions for these states and solve this problem in O(N^2). If someone could suggest a top-down approach it would be really helpful as i generally find it difficult to find transitions using bottom-up approach.

Read more »

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

By OsamaFathy, history, 3 hours ago, In English,
 
 
 
 

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

Hello, Codeforces! The reason why I am writing this blog is that my ACM/ICPC teammate calabash_boy_love_15 is learning this technique recently(he is a master in string algorithms,btw), and he wanted me to provide some useful resources on this topic. I found that although many claim that they do know this topic well, problems concerning inclusion-exclusion principle are sometimes quite tricky and not that easy to deal with. Also, after some few investigations, the so-called "Inclusion-Exclusion principle" some people claim that they know wasn't the generalized one, and has little use when solving problems. So, what I am going to pose here, is somewhat the "Generalized Inclusion-Exclusion Principle". Most of the describing text are from the graduate text book Graduate Text in Mathematics 238, A Course in Enumeration, and the problems are those that I encountered in real problem set, so if possible, I'll add a link to the real problem so that you can solve it by yourself. I'll start with the basic formula, one can choose to skip some of the text depending on your grasp with the topic.

Consider a finite set and three subsets , To obtain , we take the sum + + . Unless are pairwise distinct, we have an overcount, since the elements of has been counted twice. So we subtract . Now the count is correct except for the elements in which have been added three times, but also subtracted three times. The answer is therefore

, or equivalently,

The following formula addresses the case applied to more sets.

The Restricted Inclusion-Exclusion Principle. Let be subsets of . Then

This is a formula which looks familiar to many people, I'll call it The Restricted Inclusion-Exclusion Principle, it can convert the problem of calculating the size of the union of some sets into calculating the size of the intersection of some sets. It's not hard to prove the correctness of this formula, we can just check how often an element is counted in both sides. If , then it's counted once on either side. Suppose , and more precisely, that is in exactly of the sets . The count on the left-hand side is , and on the right hand side, we have

for , thus the equality holds.

Example 1. Let's see an example problem Co-prime where this principle could be applied: Given , you need to compute the number of integers in the interval such that is coprime with , that is, . There are testcases. Constraints: , .

Solution

The standard interpretation leads to the principle of inclusion-exclusion. Suppose we are given a set , called the universe, and a set of properties that the elements of may or may not process. Here we can define the properties as we like, such as , , or even . Let be the subset of elements that enjoy property (and possibly others). Then is the number of elements that process none of the properties. Clearly, is the set of elements that possess the properties (and maybe others). Using the notation

we arrive at the inclusion-exclusion principle.

Inclusion-Exclusion Principle. Let be a set, and a set of properties. Then

The formula becomes even simpler when depends only on the size . We can then write for , and call a homogeneous set of properties, and in this case also depends only on the cardinality of . Hence for homogeneous properties, we have

This is the very essence of Inclusion-Exclusion Principle . Please make sure you understand every notation before you proceed. One can figure out, by letting , we arrive at the restricted inclusion-exclusion principle.

Example 2. This problem Character Encoding requires you to compute the number of solutions to the equation , satisfying that , modulo . Constraints: . Hint: the number of non-negative integer solutions to is given by .

Solution

Example 3. Well, this one is a well-known problem. K-Inversion Permutations. The statement is neat and simple. Given N, K, you need to output the number of permutations of length N with K inversions, taken modulo . Constraint: .

Solution

Example 4. This problem comes from XVIII Open Cup named after E.V. Pankratiev. Grand Prix of Gomel.Problem K,(Yes, created by tourist:) ) which gives a integer , and requires one to find out the number of non-empty sets of positive integers, such that their greatest common divisor is , and their least common multiple is , taken modulo .Constraint: .

Solution

I guess that's the end of this tutorial. IMO, understanding all the solutions to the example problems above is fairly enough to solve most of the problems that require the inclusion-exclusion principle(but only for the IEP part XD). This is my first time of writing an tutorial. Please feel free to ask any questions in the comments below or point out any mistakes in the blog.

Read more »

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