### MikeMirzayanov's blog

By MikeMirzayanov, 8 years ago, ,
Welcome and good luck on the round!

I'd like to remind that if you have any questions on the problems, the best way to ask them is to use the web interface on the problems page.

Later in the same post we will discuss the round.

Wish you high rating,
MikeMirzayanov.

UPD. For contest you may thanks team Saratov SU #5, namely, users Gerald and

UPD2. And better late than never: the presence of English statements we are obliged only to Julia. Many thanks to her for 8 wonderful translations of 8 rounds.
Announcement of Codeforces Beta Round #8

•
• +22
•

 8 years ago, # |   0 Admin, Please release the Test Data??  It is very tough for me think of all the test cases....
•  8 years ago, # ^ |   +2 If it's tough for you, find more easy challenge then.Do you know any contests with test cases release?
•  8 years ago, # ^ |   0 Yes. TopCoder.
•  8 years ago, # ^ |   +3 Hm, yeah, I didn't think about TopCoder. Sorry then.But anyway, there's more sense to proceed solve problems in practice room without knowledge of the test cases, in my opinion.
•  8 years ago, # ^ |   +2 Hm... Let me think... Like IOI, TopCoder, COCI, USACO and pretty much everything IOI-style...
•  8 years ago, # ^ |   0 OK, I agree.But this competition is in ACPC style and in this way organizers hide test cases even after the end of the competition.
•  8 years ago, # ^ |   +3 Well, in ICPC you also can't view other person code, I guess. But here, you can download Petr's solution and just randomize cases until you find a non-working case on your code (I tihnk, that's gonna happen not so rarely). So, it will just make possible task simplier to release test cases after the contest.
•  8 years ago, # ^ |   +1 Hi, where I can download Petr's solutions?
•  8 years ago, # ^ |   0 Enter contest -> Click on a number, showing how many users solved this task -> Click on any submission numberIt seems, that you can't scroll through all submissions, but you will find some "Accepted" for sure.
•  8 years ago, # ^ |   0 thanks
•  8 years ago, # ^ |   0 i thnk now no one (except admin) can get "petr"'s solution(i have checked each sort option)showing solution in this way is not quiet uncomfortable to access...it shud be accesible through STANDING page.....so that everyone can see the solution of high rankers comfortably...(well that another kind of sort i think....... :) )
•  8 years ago, # ^ |   0 Actually you can view Petr's solutions, check this out:http://codeforces.ru/contest/8/status/B?order=BY_ARRIVED_ASC
•  8 years ago, # ^ |   0 sorry I forgot mentioning....actually i was searching for problem A...... :)
•  8 years ago, # ^ |   0 http://codeforces.ru/contest/8/status/A?order=BY_ARRIVED_ASCYou can view any problem, just append order=BY_ARRIVED_ASC manually to the URL.
•  8 years ago, # ^ |   +6 I am a fan of constructive argumentation; I would, therefore, be happy to learn some advantages of not releasing official test data. Until that I support all the frustrated coders who just can't find bugs in their solutions. Contest is one thing, but in my opinion the process of practice would only benefit if test data was available - whether one decides to use it or not, it is totally his/her responsibility and choice of training techniques.
•  8 years ago, # ^ |   0 You can view accepted solutions and compare them with your one. It's useful excercise.What does Mikhail Mirzayanov think about test data release?
•  8 years ago, # ^ |   0 I think that open test would be useful.Especially when an error is in technical details e.g. array sizes etc.
 8 years ago, # |   +1 why can the problem C shows out the PE error?
•  8 years ago, # ^ |   0 Same problem here. Any ideas on why the PE for problem C test 5?
•  8 years ago, # ^ |   0 It is not differ much from WA.Solution returned some time T, and some order P.PE returned when total time, needed to collect objects in order P differ from time T.
•  8 years ago, # ^ |   0 It also happened to me. It was path reconstruction.
•  8 years ago, # ^ |   0 Thanks Fefer and Enric, got AC now.
•  8 years ago, # ^ |   0 hi~can you tell me how did you solved the PE problem on test 5?i've been stuck at it for more than 2 hours...and can't find my problem...
•  8 years ago, # ^ |   0 In my case, it was that my program first attempted to pick up a pair of objects, and recorded the best option, and afterwards when it tried picking up only one and found a better solution, it forgot to say "only pick up one" and so the order it output was wrong.
 8 years ago, # |   +6 Really liked the problems, but 1 geometry would be really enough :)
 8 years ago, # |   0 i think this time,the judge is too terrible:(
 8 years ago, # |   +1 It's a pity that testing problem isn't fully solved... Especially it felt at the end of the round, where appeared a huge queue of problems to test.
 8 years ago, # |   0 Could you please post the 9-th test for the B problem? :)
•  8 years ago, # ^ |   0 I think the 9th case consist of something like this, UURRDLHere the answer should be "BUG", but if you don't check the adjacent squares, you'd get "OK".
•  8 years ago, # ^ |   0 I've already sorted it out, my solution was correct, but I accidentally submitted it with debug output on, so it messed up.Thanks anyway :)
 8 years ago, # |   0 Could you please post the 3rd test for the A problem? :)
 8 years ago, # |   0 please provide the #Test9 for A - Train and Peter
•  8 years ago, # ^ |   0 same to me, I fail at this test case too. The statement may not be clear enough to detect the errors for me :(
•  8 years ago, # ^ |   0 I misunderstood the problem A-Train and PeterI got Ac finally its "Substring" searching problem#include#include#include#includeint main(){  char s[100003],r[100003];  int i,j,k;  char s1[100003],s2[100003],*ch;  int flag1=0,flag2=0;  scanf("%s%s%s",s,s1,s2);  k=0;  for(i=strlen(s)-1;i>=0;i--)    r[k++]=s[i];    r[k]='\0';      if(strstr(s,s1)){   ch=strstr(s,s1);   if(strstr((ch+strlen(s1)),s2)) flag1=1;   }    if(strstr(r,s1)){   ch=strstr(r,s1);   if(strstr((ch+strlen(s1)),s2)) flag2=1;   }    if(flag1==1&&flag2==1) printf("both\n");  else if(flag1==1&&flag2==0) printf("forward\n");  else if(flag1==0&&flag2==1)printf("backward\n");  else if(flag1==0&&flag2==0) printf("fantasy\n");  return 0;}
•  8 years ago, # ^ |   0 yes, this problem is simple if one notice that they allow only continous stations.
•  8 years ago, # ^ |   0 Try that testsaaacaaacaaabackwardaacaaaacaaaforwardaacaaacaaafantasy
•  8 years ago, # ^ |   0 I just realize that these sequences contains continuous stations. Before, i think:s=aabcds1=acs2=d=> forward :(
•  8 years ago, # ^ |   0 how about ... UURD ?
•  8 years ago, # ^ |   0 never mind, wrong problem
•  8 years ago, # ^ |   0 It's for problem B.And the ans is BUG.
•  8 years ago, # ^ |   0 Yes，it is a bug。
 8 years ago, # |   +1 how can i turn the pages in the status?
•  8 years ago, # ^ |   0 It seems that it's "under construction".
 8 years ago, # |   +1 Who wants to see a Petr in a train? =)
•  8 years ago, # ^ |   0 Hi, where I can download Petr's solutions?
•  8 years ago, # ^ |   0 I want。
 8 years ago, # |   +5 There are some odd effects with ratings. For example, before contest I was in Division 2, solved 2 problems and now I have rating 1603. MRoizner was in Division 1, solved 3 problems and now has rating 1567. It seems a little bit strange.  =)
•  8 years ago, # ^ |   0 It's all right. He solved problems worse than average participant of his 1st div.
•  8 years ago, # ^ |   0 What's the different between Div 1 and Div 2?I am a new for Codeforces.
•  8 years ago, # ^ |   0 Non-rated users (newbies) or those having less than 1500 rating points belongs to second division. Others ( >= 1500 rating ) belongs to first division.By the way at first contest you have rating 1500 and have changes with it participating in second division.
 8 years ago, # |   0 Could you please post the 19th  test for the A problem? :)
 8 years ago, # |   +20 Thanks for the nice problems!Although when I submitted D for the second time, I was almost completely sure it will fail again, since there're too many if's :)
 8 years ago, # |   0 We dont have forum at this moment?
 8 years ago, # |   +6 Hi.  Is it possible to have a public Google Calendar with the match times updated on it?  This saves me trouble of converting between Moscow and New York time all the time ;)
•  8 years ago, # ^ |   0 I have such calendar.Is is suitable for you?
•  8 years ago, # ^ |   0 This works, but will it be updated at all times permanently? (i.e., whoever is maintaining that Calendar may get busy in life and stop updating.)
•  8 years ago, # ^ |   0 While the calendar will be updated he will be updated.That's nothing more I can say about it.By the way you can tell me if I forgot something. That really helps sometimes.
•  8 years ago, # ^ |   0 Well, for one thing, TopCoder SRM 467 is marked on the wrong date, as far as I can tell.
•  8 years ago, # ^ |   +12
•  8 years ago, # ^ |   0 Am I wrong?
•  8 years ago, # ^ |   0 I am not sure.  It shows up on my Calendar on Wednesday, but it is on Thursday.  My time zone is synchronized with TopCoder so I am fairly confident.
•  8 years ago, # ^ |   0 Oh, realy my mistake. Thanks!
•  8 years ago, # ^ |   0 really cool...would you please tell me how you did it? I mean how to sync the information from the website to  google calendar? because I want to arrange some contests from schools in my region, and they always post the time on their website, like this:Thank you very much :D
•  8 years ago, # ^ |   0 I created a new calendar and pasted a contest event with time in my time zone. So I sync information by hands.
•  8 years ago, # ^ |   0 great job. Thank you:)
 8 years ago, # |   0 still WA on problem B...I've considered situations like UURD... and I used a BFS.But always get WA on the 1st Test....any help?
•  8 years ago, # ^ |   0 You can use hash……I AC it with a map[230][230].
•  8 years ago, # ^ |   0 no cycle,and bfs
•  8 years ago, # ^ |   +12 http://codeforces.ru/blog/entry/259#comment-2894galymzhan:Problem B doesn't need BFS. I solved it in linear time using followin approach:set all f[201][201] = 0;set f[100][100] = 1; // start locationsimulate moving and for each new location f[x][y], check the sum of four adjacent cells. If the sum > 1 then answer is BUG.
•  8 years ago, # ^ |   0 UPme too.I solve it without bfs.
•  8 years ago, # ^ |   0 nice algorithmBut my method should not be wrong =.=still can't find my error...Maybe I should wait till test cases are released. :(
•  8 years ago, # ^ |   0 Does the test UD gets a BUG?
•  8 years ago, # ^ |   0 yep...I tried this.
•  8 years ago, # ^ |   0 Hey, I solved mine like your idea exactly and the same problem ...but i think there is something wrong in the judge.have a look in my BFS function and got AC when i add that line , have a look:#include #include #include using namespace std;#define pb push_back#define rep(i,m) for(int i=0;i vi;typedef vector > vii;typedef long long ll;#define oo ((int)1e9)int arr[1001][1001];int vis[1001][1001];int dx[]={0 , 1 , 0 , -1};int dy[]={1 , 0 , -1 , 0};int BFS(int ii , int jj){ queue > > q; q.push(make_pair(0 , make_pair(500 , 500))); vis[500][500] = 1; while(!q.empty()){ int j = q.front().second.first , k = q.front().second.second , len = q.front().first; q.pop(); if(ii == j && k == jj)return len; rep(i , 4) { if(arr[dx[i]+j][dy[i]+k] == 0 || vis[dx[i]+j][dy[i]+k])continue; q.push(make_pair(len+1 , make_pair(dx[i]+j, dy[i]+k))); vis[dx[i]+j][dy[i]+k] = 1; } }     cout << "It will never cout this !!" ;     return 0; // without this line it will get WA in test case 1 , Now AC}
•  8 years ago, # ^ |   0 thx a lot...but that's not my problem .I will try to rewrite this problem again...maybe there are some small flaws in my program, though I tried thousands times to make sure it won't :DBTW: It's not the problem about the judge. the line: "return 0; "gives the operation a signal that the program ends correctly.otherwise the operating system on the server would think this program has some wrong, because no signal inform it that the program is right.
•  8 years ago, # ^ |   0 The return 0 is not in the main, its in a function I call. Also control never reaches this statement (Thats why I added a cout before it to double check). It compiles successfully at the judge? Why should not work?
•  8 years ago, # ^ |   0 so sorry that I didn't read your post carefully...and I added that line, finally got AC.Thank you so much, and now I understand the reason...because maybe the BFS can't find a route.^_^and, sorry again.
•  8 years ago, # ^ |   0 I am glad to help :)...but please Can you post a test case that I can't find a route ??
 8 years ago, # |   0 Could anyone explain how to solve problem C, please ? Is it greedy ?
•  8 years ago, # ^ |   0 dp
•  8 years ago, # ^ |   0 Main idea of DP for this problem?
•  8 years ago, # ^ |   +1 dp(S), which has 2^n states, the cost of visiting all the vertices s_i in the set S.Then, you can just visit one node, or two. This leads us to a n^2*2^n algorithm, which is too slow.Coding it in n*2^n using the fact that you can start from the first element in the set should be enough. When you visit just one vertex do one recursive call, and when you have to visit a pair of vertices just iterate on the second one (you can choose s_1 always as the first one). Precalculating distances in an array may also be useful.
 8 years ago, # |   0 Thanks for the contest :) It was my first contest here. Problem C seemed to be killing problem for me. I've got TLE #12 too many times. Finally I found out that I can make it N-times faster and finally got Accepted.
 8 years ago, # |   +2 UPD: And many thanks to Julia for her devoted help in translating the 8th round in a row. Not modest, but true...
 8 years ago, # |   0 Can anyone tell me what can be bug with WA 6 in problem C?
•  3 years ago, # ^ |   +8 Seriously, can anyone tell me what is the test case #6? I really want to know.
•  3 years ago, # ^ |   +3 Still remember this problem. I only glanced at your code, so I can be wrong, but here is something that I really don't think should be in there: if(n%2==0){ for(int i=2;i<=n;i+=2){ The oddity of the number of the objects does not matter, also you I don't think you want to jump 2 objects at a time. It looks like you are trying to make as many groups as possible, when in fact some objects are better left alone. (Precisely, pairing up any 2 objects which make an obtuse angle with the purse will only increase the distance, given how it's calculated in this task).Consider a bitmask dp where you either pick the leftmost zero alone or in a group with any other zero.
•  3 years ago, # ^ |   0 Oh, now I see. Thanks a lot. I understood my mistake.
 8 years ago, # |   0 anyone who can tell the solution of problem E?
8 years ago, # |
0
something wrong with the judge...
when i submit my solution, it shows
 Judgement failed