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

Hello, codeforces!

The community wants so the community gets it! :D Here it is, my very first blog about tasks and algorithms. At the beginning I've decided to post my entries on codeforces, maybe I'll switch to something different if it becomes uncomfortable.

To pour the first blood I decided to choose a task from one of the old ONTAK camps. Task's name is "different words". The statement goes as follows:

You are given n words (2 ≤ n ≤ 50 000), every of length exactly 5 characters. Each character can be a lowercase letter, an uppercase letter, a digit, a comma... basically, it can be any character with ASCII code between 48 and 122 (let's say that k is the number of possible characters). A task is to find all pairs of indexes of words which are . Two words are if they differ at all 5 corresponding positions. So for example words and are really different and words and are not, because in both of them the third character is . As there can be many such pairs (up to ), if there are more than 100 000 pairs, then the program should print that there are only 100 000 and print this number of pairs (arbitrary chosen).

Please, note that this task comes from the contest which took place a few years ago, so don't think about bitsets. :P

So, how can we attack this problem? At first, you may think about some meet in the middle. It turns out to be hard, even if you can come up with something with k3 in complexity, then it'll probably be multiplied by n. O(k5) is also too much. Inclusion-exclusion principle unfortunately also won't be helpful, as we want to find those pairs, not only count them, and working on sets of words won't be so effective.

The biggest problem is that k is big. If it'd be, let's say, up to 10, then it'd be solvable in some way, but I won't go deeply into this solution, cause it isn't interesting and k is of course bigger. But I've mentioned small k. Why couldn't we dream about even smaller k? If k would be up to 2 (so words would consist only of digits 0 and 1) then this task would be trivial. We'd just group words which are the same, and for each word its set of really different words would be the group with words where every zero is changed into one and vice versa. But again, k isn't small...

Buuuuut, we can imagine that it is! Let's say that we assume that characters with even ASCII characters are "new zeros" and characters with odd ASCII characters are "new ones". Then for sure if two words are really different with these assumptions, then they are really different without them, cause if they'd have this same character at some position, then this character would change into this same "new character". This allows us to find some pairs, unfortunately not all of them, but the way definitely looks encouragingly.

If we've found some of the pairs, maybe we should just try one more time? But how should we change characters now? Now comes an experience: if you have no idea what to do or you don't want to do some complicated construction, then just do something random! So we could randomly change every character into zero or one and then run our algorithm for k equal to 2 — match groups of opposite words. What's the probability for a fixed pair that we'd find it during one run of our algorithm? If we already know what we've assigned to each character of the first word, then on every corresponding position in the second word there should be a different character — for each position we have a chance, that this assigned character will be correct, so we have probability equal to that the whole word will match.

What's the number of needed runs? Looking at limits we can guess that it could be a few hundred. Let's calculate the probability of fail if we'd repeat algorithm 600 times. The probability that we wouldn't find some pair is equal to , the probability that we'd find it, of course, and finally, the probability that we'd find all of them (or some 100 000 of them) is equal to which is greater than 0.999, so it's definitely enough.

There is one more thing. Consider words and . They are really different. Let's say that we've assigned 0 to a. Then we have to assign 1 to b. Then we have to assign 0 to c. Then we have to assign 1 to a. So there is a problem... At first glance, it might look problematic, but it turns out that it's easy to fix it. We shouldn't just assign zeros and ones to characters. We should assign them to pairs (character, position). Then everything will go well.

Total complexity is something like O(n·600·log(n)), but we can get rid off the log factor by using hashmaps.

Sooooo, it's the end of my first blog, sorry if it's too long. I hope that you've found this task useful and interesting. What do you think about this format, what was missing, what was bad? It'd be great to see a feedback from you. See you next time! :D

Read more »

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

By Radewoosh, history, 47 hours ago, In English,

Hello codeforces! I want to share my idea with you.

I've noticed that I know some nice tricks and some tasks with very educative solutions, which might be interesting, surprising or useful in other tasks. Recently I am considering starting my own blog, where I'd share chosen tasks with you and write about possible ways to solve them. I wanted to ask the community about it, cause I don't want you to hate this idea and write comments like "boooo, we already have Petr's blog, you are just copying his idea, you just want contribution, you are next Swistakk, go away".

What do you think about this idea? I'd be able to change form of this blog as you wish and add additional sections. Should I write such blogs?

Read more »

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

By gepardo, history, 9 hours ago, In English,

Hello, Codeforces!

I think many of you know about Mo's algorithm. For those, who don't know, please read this blog.

Here, I consider an alternative (and faster) approach of sorting queries in Mo's algorithm.

Table of contents

 

Read more »

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

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

Thank your for participation!

Problem D2A (New Building) was authored and prepared by burunduk2.

Problem D2B (Badge) was authored and prepared by me, the version in SIS's olympiad contained the version with n ≤ 105.

Problem D1A (Elections), D1B (Hat), D1D (Large Triangle) were authored by achulkov2, with D1A prepared by Schemtschik, D1B by achulkov2 and D1D prepared by achulkov2 and senek_k.

Problem D1C (Sergey's Problem) was authored and prepared by WreckingBall.

Problem D1E (Raining Season) was authored and prepared by izban.

Editorials were written by izban and VArtem

Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...

Read more »

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

By tourist, history, 31 hour(s) ago, In English,

The rules for advancement to the onsite finals of TCO 2019 Algorithm have changed from those for TCO 2018:

http://tco19.topcoder.com/home/algorithm/algorithm-rules

This page claims there are "three (3) ways to advance to the Onsite Finals"!

The first way to advance is to take part in SRMs. There are four three-month Online Stages, during which every positive score in an SRM counts towards a global ranking. The best competitor in each Online Stage advances to the onsite finals directly, with the next 10 competitors advancing to Online Round 4 (which is the final qualification round).

The other two ways stay the same. The best 10 competitors (used to be 14 though) advance from Online Round 4, and the best 2 competitors advance from Online Wild Card Round.

The changes seem to be big enough -- and already relevant, since SRM 736 on August 15 (in two days from now) already counts towards Online Stage 1. However, apart from TCO 2019 website I've only seen this information in Topcoder weekly newsletters, and I believe many people have missed it.

What do you think?

Read more »

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

By gKseni, 2 days ago, translation, In English,

Important day! Today we will know the winners of VK Cup 2018. The prize fund of the competition — numbers in binary notation:

  • 1 place — 1048576 rubles
  • 2 place — 524288 rubles
  • 3 place — 262144 rubles
  • 4-8 place — 131072 rubles

We are start at 10:40. Monitor the progress here.

Current standings

Good luck to the competitors! At the evening I add the results in this post.

Read more »

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

By _kun_, history, 6 days ago, translation, In English,

Hi!

Summer Informatics School (SIS / LKSH) is a summer school for students in grades 6-10. SIS is focused mainly (but not only) on students participating in the Olympiads in Informatics — from beginners to participants of international competitions. SIS is held in July and August, each of them is visited by about 200 students from all over Russia and abroad. The language of the camp is Russian. Additional information about SIS is posted at lksh.ru

Right now, the August branch of the Summer Computer School is running, and on August 11 the traditional team Olympiad is going to place. I am happy to present a rated round based on it!

The round will be rated for both divisions, will be held in Aug/11/2018 16:35 (Moscow time), in each division there will be 5 tasks and 2 hours to solve them.

The problems of this round and the SIS olympiad were authored and prepared by SIS's teachers: izban, achulkov2, Schemtschik, i_love_isaf27, senek_k, asokol, WreckingBall, burunduk2. Also, I would like to thank Dembel for his help with olympiad's organization.

Thanks to our problems testers: _meshanya_, burunduk2, gritukan, niyaznigmatul, manoprenko!

Thank you, MikeMirzayanov, for the codeforces and polygon systems!

Yes, we are aware, that this contest clashes with ProCon Junior on codechef. However, given the schedule of the SIS and the approaching VK cup finals we can't do anything with it, sorry for that =/

Good luck!

UPD: The round will have one interactive problem for both divisions. Please, read the post about interactive problems here: Interactive Problems: Guide for Participants.

Congratulations to winners!

Div1:

  1. Marcin_smu
  2. Radewoosh
  3. Swistakk
  4. Panole233
  5. ko_osaga

Div2:

  1. Onuz
  2. aurelio
  3. usachevd0
  4. jebouin
  5. etiennerossignol

Upd Thank you for participation! Due to vk-cup conduction rating recalculation will happen slightly later, than usually.

Upd The editorial is published!

You may also check the unofficial editorial, written by neal.

Read more »

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

By majk, 28 hours ago, In English,

Topcoder SRM 736 is scheduled to start at 15:00 UTC, August 15, 2018. Note that as per the new Topcoder Open Algorithm rules (see associated discussion on CF) this round counts towards 2019 Topcoder Open Online Stage 1.

The tasks were prepared by me. I'd like to thank misof and paulinia for comments and testing.

You will be able to register for the SRM in the Arena or Applet 4 hours prior to the start of the match. Registration closes 5 minutes before the match begins, so make sure that you are all ready to go.

Refer to this guide to set up your environment for competing.

Good luck, have fun, positive rating!

Read more »

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

By csacademy, 29 hours ago, In English,

The 25th Central European Olympiad in Informatics will take place in Warsaw, Poland, during August 12th-18th 2018. The most gifted high school students from 14 countries will have the opportunity to prove their knowledge and skills in informatics.

The CS Academy team will organise the online mirror for this year's competition. The online mirrors will take place after the finish of each of the 2 competition days, having the same scoring format.

The online mirror schedules are the following:

Contest format

  • The contest will be rated for all users.
  • You will have to solve 3 tasks in 5 hours.
  • There will be full feedback throughout the entire contest.
  • The tasks will have partial scoring. The maximum score for each problem will be 100 points.
  • There will be a time tie breaker, so two users having the same total score at the end of the contest will be further sorted by the penalty.
  • The penalty will be equal to the first time they achieved the final score. Only submissions that increase the total score are taken into account. This means that after getting 50 points on a problem you will still have 50 points even after submitting a solution that gets 0 points and that the penalty will remain the same.

Facebook event

We created a new Facebook event. If you choose "Interested" here, you will be notified before each round we organise from now on.

Read more »

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

By hunterr_196, history, 27 hours ago, In English,

Can anyone please help me with this Codechef August Long Challenge 2018 problem QUESTION why my solution is giving Wrong Answer and for which test case it is failing and why..... solution link Solution It will be a great help for me....thank you.

Read more »

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