### Gerald's blog

By Gerald, 6 years ago, translation, ,

Good day!

Elimination round of the CROC Collegiate Programming Competition for the MSTU Bauman students is going to be here soon. The official championship participants will take part in the competition, all others will be out of the competition in the table of results.

The contest is held by the well-known rules ACM-ICPC. Competition duration is 2:00 hours. Supported programming languages are C/C++, Pascal, Java, C#, Python, Ruby, PHP, Haskell, Scala, OCaml, and D.

This Round will be the rated for the Div-2 participants, regardless of whether one is the competition championship party or not. For Div-1 participants this round is unrated.

Please note that the official participants of the competition are not need to register for this competition they will be registered automatically (with advance registration at website).

Good luck to everyone!

UPD. Competition is completed, thank you very much for your participation! I hope that the problems with the queue is not much to spoil your impression of the contest. The results of elimination round for official participants will be announced tomorrow. Rating will be update soon. Additional information for those who are involved in this competition for the first time:

I/O is standard. A simple programs that solve the A+B problem are shown below.

#### Pascal / Delphi:

    var
a, b: longint;
begin'
writeln(a + b);
end.


#### Java:

    import java.util.*;
import java.io.*;

public class Solution
{
public static void main (String[] argv) throws Exception
{
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());

System.out.println(a + b);
}
}


#### С++:

    #include <iostream>

using namespace std;

int main(){
int a, b;
cin >> a >> b;
cout << a + b << endl;
return 0;
}


•
• +88
•

 » 6 years ago, # |   +12 Questions will be available on English, right?
•  » » 6 years ago, # ^ |   +11 Of course yes.
• »
»
6 years ago, # ^ |
Rev. 2   -40

# include <math.h>

using namespace std; int main () { //freopen("input.txt","r",stdin); //freopen("output.txt","w",stdout); long int i, j, l, ll,a1[100000]={0}, b1[100000]={0}, n, c[100000]={0}; char a[100000], b[100000]; cin>>a>>b; l=strlen (a); ll=strlen (b); for (i=0; i<l; i++) { a1[i]=a[l-i-1]-48; } for (i=0; i<ll; i++) { b1[i]=b[ll-i-1]-48; } if (ll>l) {n=ll;} else {n=l;} for (i=0; i<n; i++) { c[i]=a1[i]+b1[i]; } for (i=0; i<n; i++) { if (c[i]>9) {

if(i==n-1)1. - - - 1. 1. 1. 1.
{
n++;
}
c[i+1]++;
c[i]%=10;
}

} for (i=n-1; i>=0; i--) { cout<<c[i]; } cout<<endl; system ("pause"); return 0; }

•  » » » 6 years ago, # ^ |   -33 это для длинная арифметика ..
 » 6 years ago, # |   0 how many problems exist?
 » 6 years ago, # |   0 rating will be updated based on div 2 users results or based on every users results?
•  » » 6 years ago, # ^ |   +13 only div2 users
 » 6 years ago, # |   +4 Problems will be sorted according to difficulties?
•  » » 6 years ago, # ^ |   -25 5 problems? 7 problems?
•  » » 6 years ago, # ^ | ← Rev. 2 →   +2 Usually, in contests with ACM-ICPC rules problems don't sorted according to difficulties.
 » 6 years ago, # |   +13 why contest isn't rated for Div 1 ? will it be a bit easier ?
 » 6 years ago, # |   0 Will there be an editorial after the completion of competition ?
 » 6 years ago, # | ← Rev. 4 →   +11
 » 6 years ago, # | ← Rev. 2 →   +8 I had registered in this contest, why i still see Register now ?
•  » » 6 years ago, # ^ |   0 I have this problem too, Can you solve it? Also there are different time to contest beginning, what does it mean?
•  » » » 6 years ago, # ^ |   +2 One countdown is for contest start, other — for registation.
•  » » » » 6 years ago, # ^ |   0 Will Registration continue till the contest's finish?
•  » » » » » 6 years ago, # ^ |   +7 Yep. It's because of ICPC rules without hacks therefore no room division needed.
•  » » » » 6 years ago, # ^ |   +3 It's quite confusing, I thought the contest would be starting in around 3 hours, but it's starting in less than 1 hour! (~45 minutes)
 » 6 years ago, # |   0 How many problems exist? And how long does contest take ? Thanks
•  » » 6 years ago, # ^ |   +2 Contest duration is 2 hours.. Wait for some time , you will know the number of problems
•  » » » 6 years ago, # ^ |   0 Thanks :D
 » 6 years ago, # |   +2 About 200 new participants , excluding the official contestants . I hope people have not made multiple accounts like last time
•  » » 6 years ago, # ^ |   0 They would not do it as there are no rooms !
 » 6 years ago, # |   +3 In queue 4ever...
•  » » 6 years ago, # ^ |   +5 No more than 10 minutes. About 8-9 minutes mostly. We are sorry about the queue, it is the result of ACM-ICPC mode + very easy tasks for many participants. We will make conclusions and prevent this next time. Sorry again about 9 minutes queue.
•  » » 6 years ago, # ^ |   +6 Happy that contest is held on CF , upset that CF has a bit weak server. :|
 » 6 years ago, # |   -33 Its frustrating to see submission in queue for so long!! Hope admins will "Unrate" this contest. And please run cf in safe mode during contests.
•  » » 6 years ago, # ^ |   +18 unrate because your result is unsatisfactory? conditions were the same for all of the participants, am I right?
•  » » » 6 years ago, # ^ |   +1 You can disagree but it is rated just among div2 and my rating will surely increase today, so it is not unsatisfactory to me.
 » 6 years ago, # | ← Rev. 3 →   -11 just fixed
 » 6 years ago, # |   +10 I like this exam . You?
 » 6 years ago, # |   +8 Amazing system testing in last.
 » 6 years ago, # | ← Rev. 2 →   +1 Nice problems! Any tips for C?
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 IN EDIT
•  » » 6 years ago, # ^ |   0 just count it from behind.. if n=7 then count how much we take coin from - 3 6 7 (we must make chest-6 and chest-7 empty) - 2 4 5 (we must make chest-4 and chest-5 empty) - 1 2 3 (we must make chest-2 and chest-3 empty)then add the coin left in chest-1
 » 6 years ago, # |   +20 Nice problem set.
•  » » 6 years ago, # ^ |   +1 Agree, i think many other people will agree too.
•  » » » 6 years ago, # ^ |   0 4 out of 8 problems were quite easy. But it's not bad, considering that it was just a qualification round.
 » 6 years ago, # |   +3 How long time take the Rating's Upgrade?
•  » » 6 years ago, # ^ |   +3 I am also waiting for the same.
•  » » 6 years ago, # ^ |   +5 So the Rating is in queue too.
•  » » » 6 years ago, # ^ |   -8 I'm currently starving!!! Please, hurry!!!
•  » » » 6 years ago, # ^ |   -9 I'm currently starving!!! Please, hurry up!!!
•  » » » » 6 years ago, # ^ |   +3 The system is not a person, it doesn't care whether you are starving or even dying ;)
•  » » 6 years ago, # ^ |   0 updated. too fast today (as no system test)
 » 6 years ago, # |   +14 I like these kind of contests :-)
 » 6 years ago, # |   +1 in problems F, i wonder whether "the last n seconds" means the last N seconds from the last record, or the last N seconds from any other records?
•  » » 6 years ago, # ^ |   0 from any record before the current record
•  » » » 6 years ago, # ^ |   0 thanks sameer47 now i know what my mistake was
 » 6 years ago, # |   -17 it was awful! wrong testcases .. long time of judging ...
•  » » 6 years ago, # ^ |   +4 wrong testcases? didn't notice..
•  » » » 6 years ago, # ^ |   0 yea, in problem e
•  » » » » 6 years ago, # ^ |   +3 ...and which of them you think is incorrect ?
•  » » » » » 6 years ago, # ^ |   0 i think at first, the input of second testcase was -i don't know i saw like that or it was really like that! anyway i apologies if i was wrong. i think i was tired!
 » 6 years ago, # |   -16 Wrong Wrong Wrong! Problem D input 3 -1 3 5 3 -1 4 5 4 -1 according to accepted solution like: http://codeforces.com/contest/245/submission/2591027 http://codeforces.com/contest/245/submission/2590877 out put 7 7 5 and that's WRONG if you need to reconstruct array b[][] from accepted out put it will be -1 7(7&7) 5(7&5) -1 7 5 7(7&7) -1 5(7&5) = 7 -1 5 5(7&5) 5(7&5) -1 5 5 -1 so, i think it's wrong, is it?
•  » » 6 years ago, # ^ |   +25 It's not. Your input is wrong, since it is impossible to generate it in the way, described in statement.
•  » » 6 years ago, # ^ |   -17 and solutions which accepted input 3 -1 1000000000 1 1000000000 -1 1 1 1 -1 out put 1000000001 1000000001 1 and problem (D) said (0 ≤ ai ≤ 109) CONTRADICTION! how to accept it?
•  » » » 6 years ago, # ^ |   +5 "It is guaranteed that there is sequence a that satisfies the problem conditions. If there are multiple such sequences, you are allowed to print any of them."So your input is wrong, because there is no answer for test case.
 » 6 years ago, # |   0 Will there be any official editorials ?? If not , please somebody take the trouble of writing it (and in English too) because I liked the problem set very much and would like to know their solutions
 » 6 years ago, # |   0 Can anyone explain the solution to problem H? I'm a big newbie (you can check by my rating ;p). It's just a simple DP O(n^2)?thanks!
•  » » 6 years ago, # ^ |   +1 Yes. dp[i][j] = number of palindromes in the [i,j] substring.
•  » » » 6 years ago, # ^ |   0 Thanks!
•  » » 6 years ago, # ^ |   +11 First you check this:isp[i][j] = "is the substring [i,j] palindrome?" After that you can try this simple DP:dp[i][j] = number of palindromes in the [i,j] substring.So it's easy to see that dp[i][j] is equal to dp[i+1][j] + dp[i][j-1] — dp[i+1][j-1] + isp[i][j].The intersection between [i,j-1] and [i+1,j] is equal to [i+1,j-1], so "dp[i+1][j] + dp[i][j-1]" calculates dp[i+1,j-1] twice and you've to subtract this one more time to maintain the correct result. Also, you've to add 1 in the solution if the substring [i,j] is palindrome. A lot of contestants solved this problem by using Manacher Algorithm + DP, but it's only a matter of time complexity.
•  » » » 6 years ago, # ^ |   +3 Thanks a lot, nice explanation! At first I though that I would have to use Manacher, since I haven't study this algorithm yet, I just gave up. Later I saw others contestants solution and I saw this DP, that's why I asked.Thank you very much!
•  » » » » 6 years ago, # ^ |   +3 Yes, but Manacher give us the length of the longest palindrome centered at Ti. But, between both solutions there isn't a big difference in time complexity.
•  » » » 6 years ago, # ^ |   0 how do you check isp[i][j] efficiently
•  » » » » 6 years ago, # ^ |   +6 isp[i][i] = 1, isp[i][j] = isp[i+1][j-1] && str[i] == str[j].It means, if the substring [i+1,j-1] is a palindrome one and str[i] is equal to str[j], so [i,j] is a palindrome substring.
•  » » » 6 years ago, # ^ |   0 I tried solve with manacher however not work, someone could tell me that I have badhttp://www.codeforces.com/contest/245/submission/2595260thx
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   0 There's a bug in a code from e-maxx.ru, read first comment there and fix it
•  » » » 6 years ago, # ^ |   0 I get this solution only 5 minutes after understand this problem Anyway, one karma for you :D
 » 6 years ago, # | ← Rev. 2 →   -18 I think that in this round there was a discrimination to some contestants. More precisely, I think that time that one was waiting in queue was calculated with the rating the contestants have.How is possible that I waited around 10 mins for every submission and some people had already solved 2 problems in the first 5 minutes. This is not a good thing, and I hope that I am wrong, because if it is true, it is really unethical.
•  » » 6 years ago, # ^ |   +1 Queue was formed based on submission times. Those that solved first two problems really fast were in the beginning of the queue.
•  » » 6 years ago, # ^ | ← Rev. 3 →   +19 It is obvious thing.. The queue was only formed becuase there were many submissions which the judge could not handle all at once. Obviously during the first 5 minutes there were very few people who made submissions and so received quick judgements. And no points for guessing that these were high rated coders.I hope you had done a lot of research before posting this , becuase this is a algorithmic platform , judge here is not a rascist and decisions are not taken here based on colors .**Colors only affect when you get upvotes and downvotes in the community** :P
•  » » » 6 years ago, # ^ |   0 What does this matter with racism ?!? There can be discrimination in many places, and it is not connected to racism.And I am sorry about my wrong conclusion we are humans, we do mistakes. Discussion closed for me.
 » 6 years ago, # |   0 will some sort of editorial / analysis be available soon?
 » 6 years ago, # |   +3 Can someone explain the solution for problem G?
•  » » 6 years ago, # ^ |   +3 The idea is similar to the last CF problem D (div 2). There are N guys (N is at most 2*M) and M pair of friends. You just do a brute force to check for all x, how many y has the most common friends (to check common friends you need a linear algorithm, like sorting everyones friends and doing a two pointers thing, or even easier calling set_intersection ;) ). It seems to be cubic, but its not, for one guy you do at most N*A + M operations (A is the number of his friends), the total complexity will be N*A + M + N*B + M + N*C + M + ... = N*(A+B+C..) + N*M = N*M + N*M = O(M^2). Here is my implementation if it is not clear yet: http://codeforces.com/contest/245/submission/2602015I hope it helps :)
•  » » » 6 years ago, # ^ |   0 i used another method, for each one, i get a set which has all the friend of him, so each pair in this set pair(a,b) should add one point. than i got a matrix, a[i][j] means how many friends, i and j have in common. this methods looks like n^2, but my solution time out at test 8, not sure why, anyone has any ideals? maybe stl just very slow....http://codeforces.com/contest/245/submission/2607465
•  » » » » 6 years ago, # ^ |   0 Try to replace strings by numbers, so you will not need map to hold the friends list.
•  » » » » » 6 years ago, # ^ |   0 yeah, should avoid using stl in the first place :), thanks
 » 6 years ago, # | ← Rev. 2 →   0 I'm confused! i wrote my solution for "problem C", but i don't know why i get wrong answer! Could someone tells me why my solution is wrong?!http://www.codeforces.com/contest/245/submission/2596191
 » 6 years ago, # |   0 Editorial is available in English @ http://codeforces.ru/blog/entry/5973