ADJA's blog

By ADJA, history, 19 months ago, In English,

Better late, than never :) Almost a year have passed, but I finally finished a two-part blog post about our team's (Nazarbayev University from Kazakhstan) journey to ACM-ICPC World Finals 2015 in Morocco.

Here are the links. Enjoy!
http://adilet.org/blog/19-04-16/
http://adilet.org/blog/02-05-16/

It was a fun event, thanks to everybody who made it happen!
And good luck to all teams in Thailand soon ;)

P.S. You may also be interested in a blog post about ACM-ICPC WF 2014 here

Read more »

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

By ADJA, history, 2 years ago, In English,

550A - Two Substrings

There are many ways to solve this problem. Author solution does the following: check if substring "AB" goes before "BA", and then vice versa, if "BA" goes before "AB".

You can do it in the following way: find the first occurence of "AB" then check all substrings of length two to the right of it to check if substring "BA" also exists. Then do it vice versa.

Complexity of the solution is O(n), where n is the length of the given string.

550B - Preparing Olympiad

Because of the low constraints, this problem can be solved by complete search over all problem sets (there are 2n of them).

For every potential problem set (which can be conviniently expressed as bit mask) we need to check if it satisfies all needed criteria. We can simply find the sum of problem complexities and also the difference between the most difficult and the easiest problems in linear time, iterating over the problems that we included in our current set/bitmask. If this problem set can be used, we increase the answer by one.

Complexity of this solution is O(2n·n).

550C - Divisibility by Eight

This problem can be solved with at least two different approaches.

The first one is based on the "school" property of the divisibility by eight — number can be divided by eight if and only if its last three digits form a number that can be divided by eight. Thus, it is enough to test only numbers that can be obtained from the original one by crossing out and that contain at most three digits (so we check only all one-digit, two-digit and three-digit numbers). This can be done in O(len3) with three nested loops (here len is the length of the original number).

Second approach uses dynamic programming. Let's calculate dp[i][j], 1 ≤ i ≤ n, 0 ≤ j < 8. The value of dp is true if we can cross out some ditits from the prefix of length i such that the remaining number gives j modulo eight, and false otherwise.

This dp can be calculated in the following way: let ai be ith digit of the given number. Then dp[i][aimod8] = 1 (just this number). For all 0 ≤ j < 8 dp[i][(j * 10 + ai)mod8] = max(dp[i][(j * 10 + ai)mod8], dp[i - 1][j]) (we add current digit to some previous result), dp[i][(j * 10)mod8] = max(dp[i][(j * 10)mod8], dp[i - 1][j]) (we cross out current digit).

Answer is "YES" if dp[i][0] = 1 for some position i. For restoring the answer we need to keep additional array prev[i][j], which will say from where current value was calculated. Complexity of such solution is O(8·len) (again len is the length of the original number).

550D - Regular Bridge

Let's prove that there is no solution for even k.

Suppose our graph contains some bridges, k = 2s (even), all degrees are k. Then there always exists strongly connected component that is connected to other part of the graph with exactly one bridge.

Consider this component. Let's remove bridge that connects it to the remaining graph. Then it has one vertex with degree k - 1 = 2s - 1 and some vertices with degrees k = 2s. But then the graph consisting of this component will contain only one vertex with odd degree, which is impossible by Handshaking Lemma.

Let's construct the answer for odd k. Let k = 2s - 1.

For k = 1 graph consisting of two nodes connected by edge works.

For k ≥ 3 let's construct graph with 2k + 4 nodes. Let it consist of two strongly connected components connected by bridge. Enumerate nodes of first component from 1 to k + 2, second component will be the same as the first one.

Let vertex 1 be connected to the second component by bridge. Also connect it with k - 1 edges to vertices 2, 3, ..., k. Connect vertices 2, 3, ..., k to each other (add all possible edges between them), and then remove edges between every neighbouring pair, for example edges 2 - 3, 4 - 5, ..., (k - 1) - k.

Then we connect vertices 2, 3, ..., k with vertices k + 1 and k + 2. And finally add an edge between nodes k + 1 and k + 2.

Build the second component in the similar manner, and add a bridge between components. Constructed graph has one bridge, all degrees of k and consists of O(k) nodes and O(k2) edges.

Complexity of the solution — O(k2).

550E - Brackets in Implications

Let input consists of , ai is 0 or 1 for all i.

Let's show that there is no solution in only two cases:

1) an = 1.

, for all x, and no parentheses can change last 1 to 0.

2) Input has the form or its suffix with at least two arguments.

This can be proven by induction. For input there is no solution, for longer inputs any attempt to put parentheses will decrease the number of 1s in the beginning by one, or will introduce 1 in the last position (which will lead to case one).

Let's construct solution for all other cases.

1) For input 0 we don't need to do anything.

2) For input of the form we don't need any parentheses, the value of this expression is always

3) Expression in the form (where second missed part consists of ones only). Then .

Complexity of the solution is O(n).

Read more »

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

By ADJA, 2 years ago, translation, In English,

Hello, Codeforces!

We are glad to announce that on 4th of June at 19:30 MSK Codeforces Round #306 will be held. Authors of this contest are me (Adilet Zhaxybay) and Timur Sitdikov (Timur_Sitdikov). The round will be rated for the second division, however, participants from the first division can, as usually, participate in it unofficially.

We want to thank all the people, who helped us to prepare the contest: Max Akhmedov (Zlobober), who helped us with the problems, Bekzhan Kassenov (Bekzhan.Kassenov) and Sergey Lazarev (SergeyLazarev), who tested the round, and Maria Belova (delinur), who translated problem statements. Also we want to say great thanks to Mike Mirzayanov (MikeMirzayanov) for creating Codeforces and Polygon.

By the way, as far as we know, Timur_Sitdikov is the first participant from Uzbekistan, who took part in the preparation of Codeforces round. We hope that everything will go well :)

Good luck to all!

UPD The scoring will be dynamic

UPD2 Editorial can be found here

UPD3 Congratulations to winners!

  1. gotze

  2. I_Love_Nodir.Daminov

  3. tun

  4. ptnk130210

  5. goodhope

Round is over, thanks to everybody, who took part in it!

Read more »

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

By ADJA, 3 years ago, translation, In English,

Hello, Codeforces!

My name is Adilet Zhaxybay, and together with Bekzhan Kassenov (Bekzhan.Kassenov) we are authors of Codeforces #294, which will be held on 28th of February at 16:00 MSK. This is our first Codeforces round and we are happy to invite all of you to participate in it. The round will be rated for the second division, however, participants from the first division can, as usually, participate in it unofficially.

As far as we know, it is the first Codeforces round, which was completely prepared by the authors from Kazakhstan. We are very honored by this fact and hope that everything will go great. We are encouraging other participants from our country to join us — I am sure, that you can prepare a lot of very nice problems. Preparing Codeforces round is possible ;)

We want to thank all the people, who helped us to prepare the contest: Max Akhmedov (Zlobober), who helped us with the problems, Nurlan Kanapin (kt-9) and Mansur Kutybaev (Mex-Mans), who tested the round, and Maria Belova (delinur), who translated problem statements.

Also we want to say great thanks to Mike Mirzayanov (MikeMirzayanov) for creating Codeforces and Polygon. We want to congratulate Codeforces with its fifth anniversary. We, authors of the round, were very lucky to start competitive programming at the time, when Codeforces already existed, and it helped us really a lot!

We love, when authors of the round write a bit about themselves (we encourage everybody to do so) — this helps to feel that there are real people behind the problems. Thus, we will write a bit about ourselves. We are students from Nazarbayev University (nu.edu.kz). NU is a new university with English as a language of teaching, which is located in the capital of Kazakhstan, Astana. Our university participates in ACM-ICPC only from 2012, but the team from NU already qualified to World Finals twice — in 2014 and 2015. We hope that we will do only better in the future!

Good luck to all!

UPD Score distribution will be standard (500 — 1000 — 1500 — 2000 — 2500)

UPD2 Editorial is available here

Congratulations to winners!

  1. AkashiSeijuro

  2. hzwerhzwer

  3. mxh3777

  4. Kieu_Duyen

  5. ruozha2 & i_hate_t0nzuk

Round is over, thanks to everybody, who took part in it!

Read more »

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

By ADJA, 3 years ago, In English,

New data structure for solving problems involving palindromes in the strings:
http://adilet.org/blog/25-09-14/

Thanks to MikhailRubinchik for sharing it!

Read more »

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

By ADJA, 3 years ago, translation, In English,

Some impressions from a contestant's point of view:
http://adilet.org/blog/30-06-14/
http://adilet.org/blog/02-07-14/

Thanks to all organizers and volunteers who made this World Finals possible!

Read more »

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

By ADJA, 3 years ago, In English,

Hello!

As a part of preparation for ACM-ICPC 2014 World Finals our team NU 1 prepared (and continues preparing) Algos — collection of some useful algorithms. Today we decided to share it with Codeforces community.

For the ease of use of Algos, all algorithms (with very rare exceptions) can be compiled and executed as is. Moreover, in order to verify the correctness of code and to help understanding the purpose of algorithm, the source code of every algorithm is based on some reference problem (on which the link is provided). Short description and time complexity are also available for every algorithm.

Algos is originally based on the repository on Github. You are very welcome to fork and contribute!

Requests, bug-reports and just feedback are welcome in the comments :)

'Algos' algorithm collection.

Github repository.

Which other algorithms you would like to see there?

Read more »

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