KrK's blog

By KrK, history, 7 weeks ago, In English,

Hello,

Does anyone know where I could find the test data for the task Travel Agency (Algorithmic Engagements 2006)? I have gone through the problem statement on the SZKOpul online judge, but I did not find the input files there. The input files there are essential to solve the problem :)

Thanks!

KrK

Read more »

 
 
 
 

By KrK, history, 4 months ago, In English,

I would like to discuss C. Triple Flips from today's competition.

This problem was way too difficult for me during the competition because of its constructive nature. However, when upsolving I came up with the following solution:

1) If we have enough space from one side, we could flip '1' to '0' without influencing other elements. For instance, flipping 8th '1' to '0' would be three operations (2, 5, 8), (2, 3, 4), (3, 4, 5).

2) When we may not have enough space (it could happen with n = 7 for a middle element, for example), n is small (let's say n <= 15). In this case, we could apply a simple BFS for bitmasks.

3) When n > 15, I consider the first and the second '1'. I try to erase them both at once by finding the third element (which is to the right of the second '1', and it does not matter whether it is '0' or '1'), and flipping them all. Of course, this element might not exist (the third element of the arithmetic progression might be out of bounds of the string :) ). In this case, I eliminate the first '1' according to (1). When I apply this step, I repeat the process until one elements remains. Then I just eliminate it.

Do you think that this is correct? Spoiler alert: no, this is not. Although at first I thought that the idea in (3) manages to capture all '1's efficiently, it is quite clear that this could lead to n / 2 operations for lengthy strings. However, before realizing this, I managed to submit this idea and get AC. Look at my accepted incorrect submission here.

The test is: 11010..010101 (string length of 100000). My solution needs only 50005 operations to solve this! :))

The moral of the story: guys, please prepare strong test cases! I know how hard it is to prepare problems, but I think that it is worth doing this extra step.

Thanks!

UPD: For those who are looking for a working solution using a similar idea, I fixed it by this submission. It is almost the same, but avoids the issue of the substring "110", maintaining not only the previous '1' (for the second '1'), but a couple of them. This makes the inefficiency caused by "110" avoidable. Take a look at the solution for details. Let me know if you could hack this one as well! :)

Another solution overcoming the issue is proposed by tfg in comments.

Also komendart has added this test and some others (look down for his comment). So your solutions are currently checked against those tests when submitting!

Read more »

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

By KrK, history, 3 years ago, In English,

Hello, guys!

17 months ago I have made a post in my Codeforces blog inviting high-rated coders to join a secret group on Facebook. The link to the post is here. Sad news is that it is currently totally inactive as many members of the group are probably too busy with their careers... However, it can be seen that many of you need this group, because I get a lot of messages of people requesting to join the group. I apologize if I have ignored your message (I just did not have enough patience to write that the group is inactive over and over again).

In fact, I believe that we can resurrect the group, so invite all high-rated members to join! The requirement that you need to satisfy is following: currect_codeforces_rating + max_codeforces_rating + topcoder_rating >= 6000

If you don't have a topcoder account, currect_codeforces_rating + max_codeforces_rating >= 4500 (harder to satisfy).

Other requirements are similar to described in the old post:

  • You have to participate at least once per week in any contest

  • You have to be solving at least 3 types of the contests currently from this list:

    • Topcoder
    • Codeforces
    • OpenCup
    • ITMO training
    • Codechef (any type)
    • Hackerrank (any type)
    • COCI
    • USACO
    • ZOJ contests
    • SPOJ contests

If you want to join the described group — please write to me privately on Codeforces. Show me that you satisfy all the requirements and provide me with your email address (to send the invitation to the group to). Some people had problems with getting the invitation by email. The email address which is associated with Facebook works better, so you are advised to write this address.

P. S. Sorry if I can't get back to you immediately after I read your message. Codeforces has a limit of writing to the maximum of 10 distinct users per one hour.

UPD. Some people wanted that the group would be made public. The members of the group voted and decided that it should be public. Rejoice! The link to the group (if you want to post or comment, you still have to enter the group)

Read more »

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

By KrK, history, 3 years ago, In English,

Hello, guys!

Recently ACM teams from the Baltic countries (Estonia, Latvia and Lithuania) have competed against each other in the programming camp which was held in Lithuania and was organized for the first time.

You are invited to participate in four competitions out of five in the Gym, which will be run for the four consecutive days starting from tomorrow.

Some problems in the camp were original, others were taken from old KTU contests (which are not in the Gym currently) or various local competitions that were not well-known for the participants of the camp. The competition of the day 4 was a mashup contest and consisted of Codeforces problems. As a consequence of this, it is skipped.

Have a good day and interesting contests :)

KrK

UPD: The slides of analyses which explain the solutions very briefly (some problems are not explained) can be downloaded here.

Read more »

Tags ktu, gym
 
 
 
 
  • Vote: I like it  
  • +95
  • Vote: I do not like it  

By KrK, 4 years ago, In English,

Hello,

I want to share my a bit weird experience with you guys. I was solving Tavas in Kansas and had some serious problems with debugging my solution. In the end, it was clear that the idea was correct, I just needed to focus on the implementation. I rewrote a small chunk of code and was astonished by the fact that it was equivalent, but it got accepted. I tried to play with my implementations a little. And guess what? I found out that assert() on an obvious condition can make your code work!

Proof: the failed submission and the accepted submission (only with the assert added, where k should be 1).

I generally do not have great knowledge of compilators and stuff like that. But maybe someone has the idea what the hell happened? :D

Read more »

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

By KrK, 4 years ago, In English,

Hello, guys!

Do you remember the recent competition (KTU ACM ICPC Qualification Round 2013)? The better prepared and harder version of it (KTU ACM ICPC Qualification Round 2014) is scheduled on Sunday, Sep 28, 2014, at 12:00 PM.

The onsite contest has taken place today and it was very hard for KTU students. I would give it three stars of complexity but maybe a problem or two might be interesting for Div. 1 participants too.

Please, don't participate, if you have participated in the contest onsite.

Enjoy the contest!


Solution / Secret input

Read more »

Tags gym, ktu
 
 
 
 
  • Vote: I like it  
  • +43
  • Vote: I do not like it  

By KrK, 4 years ago, In English,

Hello, guys!

I invite you to take part in the last year's competition which took place in Kaunas University of Technology and had participants from three different Universities in Lithuania.

The best participant was selected to KTU #1 (the 30th place in the last year's ACM finals) and other top KTU participants were selected to KTU #2 and KTU #3 teams.

Moreover, some of the hardest tasks were used in the preparation for IOI competition.

The contest is scheduled on Saturday, Sep 20, 2014, at 12:00 PM.

As the contest has three stars of complexity, it may be very interesting for Div. 2 participants, but I don't recommend it for Div. 1 participants and those who already participated in the contest.

All kinds of feedback are gladly accepted, as this contest is also a dress rehearsal for this year's KTU qualification round which is prepared with Polygon and will be made public for all Codeforces participants.

Enjoy the contest!


Solutions written by the authors of the problems:


All problems have been fixed

Read more »

Statements of K1 training
Tags gym, ktu
 
 
 
 
  • Vote: I like it  
  • +65
  • Vote: I do not like it  

By KrK, 4 years ago, In English,

Hello,

I can not send any messages (via "Talks"). I always get an error:

Codeforces is temporary unavailable Possibly the server is too busy, something has gone wrong or it is server maintenance. Anyway try again in a few moments.

I tried to send a message several times yesterday and today. None of them actually succeeded. As other functions of Codeforces are working for me and I am able to receive messages, I think that the problem may be specific for me.

I can not contact MikeMirzayanov. Therefore, I post the description of my problem right here in the blog.

Thanks!

Read more »

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

By KrK, 5 years ago, In English,

Hello,

I came up with an idea today — to form an active competitive programmers' group.

Why do I think that it is needed?

  1. People who participate in a lot of current contests may not find people to talk with about participating, problems, etc... (It's especially true, if you are not from strong (in terms of competitive programming) University).

  2. Some contests' sites don't provide an editorial after the contest. So it is may be more convenient to discuss the problems in a closed group than to post the question on Codeforces or Topcoder.

  3. It's fun and you may make some (intelligent) friends :)

Some experience in such type of groups.

Several years ago I with some of the programmers from Codeforces formed a contest practice group on Facebook. We solved SGU contests and practised in past Topcoder SRM rooms. It was fun. Currently, this group is inactive. To prevent this to happen again I will introduce some user requirements (based on performance ratings and activity).

What are requirements for the group members?

  1. Your rating have to be >= 2000 in Codeforces or >= 1800 in Topcoder (at a moment of joining the group).

  2. You have to participate at least once a week in any contest.

  3. You have to be solving at least 3 types of the contests currently from this list:

  • Topcoder
  • Codeforces
  • OpenCup
  • ITMO training
  • Codechef (any type)
  • Hackerrank (any type)
  • COCI
  • USACO
  • ZOJ contests
  • SPOJ contests

How to join?

  1. We have created a hidden group on Facebook. Of course, more people are still welcome to join us.

  2. If you would like to join this described group — please write to me privately on Codeforces. (Don't forget to mention your Topcoder handle if you have one, Facebook account and an email to receive an invitation)

Feel free to write some comments or suggestions about this post.

UPD1: Added other popular contests to the list.

UPD2: Added SPOJ contests; we already have over 10 members (with 4 grandmasters on Codeforces). It's already quite hard to talk personally with you, guys! :) Thank you for joining. Today I will create a group and I will send a message to each of you.

UPD3: We have 26 members! I updated How to join? section and updated the Topcoder requirements (because there were some comments that it is not fair compared with Codeforces' requirements). In addition, we don't want the group to become too big. However, if you have written to me (privately) before this update, you can enter with 1600 Topcoder ranking, instead of 1800.

Read more »

Discussion of Mission Problem D
 
 
 
 
  • Vote: I like it  
  • +46
  • Vote: I do not like it  

By KrK, 6 years ago, In English,

Good evening,

I am trying to solve a problem Torcoder.

Here is my code.

I submit it and I get MLE (which is 256 mb).

It is quite strange since the biggest amount of memory is used with the array "int freq[524288][26]". And it is 52 mb.

However, when I run the same code with the same test in "Custom test", I get the right result:

abacaba

===== Used: 0 ms, 55404 KB

What's the difference? How could I fix that?

Thank you.

Read more »

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

By KrK, 6 years ago, In English,

Hello,

Does anybody know where I could upsolve "Moscow 2012" problems? It was possible to solve these problems in contest.yandex.com even yesterday. However, it is not possible now. And this contest doesn't appear at "Gym" section in Codeforces.

Read more »

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

By KrK, 7 years ago, In English,

Having used cin/cout streams all the time, I decided to learn scanf. Now I have some problems with reading long double. I use Dev-cpp.

There is a part of my program:
...
typedef long double ld;
...
pair <ld, ld> c[Maxn];
...
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%Lf %Lf", &c[i].first, &c[i].second);
cout << c[0].first << " " << c[0].second << endl;
...

My input:
3
-5 9
0 1
5 -1

Output:
0 0

So no long doubles are read. I tried to replace "Lf" with "Le", "LE", "Lg", "LG", "e", "E", "f", "g", "G", "le", "lE", "lf", "lg", "lG". None of them seems to be working. Where is the problem?

Read more »

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

By KrK, 8 years ago, In English,

Hello.
I submitted this code to this problem with option "GNU C++ 4.6" and received "WA on test 1".
Output was:
1
CS
while the expected answer:
2
SC
However, the program was correct in my pc (I use Dev-C++). I tried to resubmit the same code but with other option "MS C++" and it worked.
So, can somebody explain to me why this code didn't worked with "GNU C++ 4.6"?

Read more »

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

By KrK, 8 years ago, In English,

Hello,

Maybe someone has solved this problem. I tried to solve it but everything was in vain. I think that we have a disconnected graph and we just need to count degrees of every vertex in connected components. Then we know what minimum number of threads is needed. But how to create a graph from the given images? One very intuitive approach would be this. Where red edges are stitches on the face of cloth and green edges are stitches on the rear of cloth. The graph itself represents the sample input. How to change this graph that the problem could be solved? I think that we need to make its edges of the same type. But how to do it?

Read more »

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