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'
read(a, b);
writeln(a + b);
end.
Java:
import java.util.*;
import java.io.*;
public class Solution
{
public static void main (String[] argv) throws Exception
{
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(in.readLine());
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;
}
Questions will be available on English, right?
Of course yes.
how many problems exist?
rating will be updated based on div 2 users results or based on every users results?
only div2 users
Problems will be sorted according to difficulties?
Usually, in contests with ACM-ICPC rules problems don't sorted according to difficulties.
why contest isn't rated for Div 1 ? will it be a bit easier ?
I had registered in this contest, why i still see
Register now
?I have this problem too, Can you solve it? Also there are different time to contest beginning, what does it mean?
One countdown is for contest start, other — for registation.
Will Registration continue till the contest's finish?
Yep. It's because of ICPC rules without hacks therefore no room division needed.
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)
How many problems exist? And how long does contest take ? Thanks
Contest duration is 2 hours.. Wait for some time , you will know the number of problems
Thanks :D
About 200 new participants , excluding the official contestants . I hope people have not made multiple accounts like last time
They would not do it as there are no rooms !
In queue 4ever...
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.
Happy that contest is held on CF , upset that CF has a bit weak server. :|
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.
unrate because your result is unsatisfactory? conditions were the same for all of the participants, am I right?
You can disagree but it is rated just among div2 and my rating will surely increase today, so it is not unsatisfactory to me.
just fixed
I like this exam . You?
Amazing system testing in last.
Nice problems! Any tips for C?
IN EDIT
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
Nice problem set.
Agree, i think many other people will agree too.
4 out of 8 problems were quite easy. But it's not bad, considering that it was just a qualification round.
How long time take the Rating's Upgrade?
I am also waiting for the same.
So the Rating is in queue too.
I'm currently starving!!! Please, hurry!!!
I'm currently starving!!! Please, hurry up!!!
The system is not a person, it doesn't care whether you are starving or even dying ;)
updated. too fast today (as no system test)
I like these kind of contests :-)
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?
from any record before the current record
thanks sameer47 now i know what my mistake was
it was awful! wrong testcases .. long time of judging ...
wrong testcases? didn't notice..
yea, in problem e
...and which of them you think is incorrect ?
Wrong Wrong Wrong! Problem D input 3 -1 3 5 3 -1 4 5 4 -1 according to accepted solution like: http://codeforces.net/contest/245/submission/2591027 http://codeforces.net/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?
It's not. Your input is wrong, since it is impossible to generate it in the way, described in statement.
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?
"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.
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
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!
Yes. dp[i][j] = number of palindromes in the [i,j] substring.
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.
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!
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.
how do you check isp[i][j] efficiently
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.
I tried solve with manacher however not work, someone could tell me that I have bad
http://www.codeforces.com/contest/245/submission/2595260
thx
There's a bug in a code from e-maxx.ru, read first comment there and fix it
I get this solution only 5 minutes after understand this problem Anyway, one karma for you :D
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.
Queue was formed based on submission times. Those that solved first two problems really fast were in the beginning of the queue.
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
Can someone explain the solution for problem G?
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.net/contest/245/submission/2602015
I hope it helps :)
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.net/contest/245/submission/2607465
Try to replace strings by numbers, so you will not need map to hold the friends list.
yeah, should avoid using stl in the first place :), thanks