### gridnevvvit's blog

By gridnevvvit, 8 years ago, translation,

Hello!

Soon (on October 1 at 19:30 MSK) you are lucky to participate in Codeforces Round #203 for Div. 2 participants. Traditionally, Div. 1 participants can take part out of the competition.

Problems have been prepared by me. I want to thank Gerald Agapov (Gerald) for help in preparation of this round, Ilya Los (IlyaLos) for testing of problems, Alexander Ignatyev (ai9128429340875) for testing of problems and for idea of one of the problems, Michael Mirzayanov (MikeMirzayanov) for marvelous Codeforces and Polygon systems, Mary Belova (Delinur) for translation of statements.

Good luck!

UPD:Scoring will be dynamic. Problems are sorted by increasing order of difficulty.

UPD: Congratulations to winners:

UPD: Editorial

• +144

 » 8 years ago, # | ← Rev. 2 →   +44 Happy National Day for all Chinese participants!Wish everyone a high score! PS: It would be better for us Chinese participants if only start time of each round could be made a little bit earlier...
•  » » 8 years ago, # ^ |   +5 can't agree more. contests on codeforces always start at Beijing time 23:30 toooooo late...
•  » » » 8 years ago, # ^ |   +11 can't agree more
•  » » 8 years ago, # ^ |   0 Can not agree more!
 » 8 years ago, # |   -31 GL&HF!
 » 8 years ago, # |   -25 I hope this contest don't like last.
•  » » 8 years ago, # ^ |   +21 whats wrong with the last one? (:
•  » » » 8 years ago, # ^ |   -24 You can surely see my username written in green colour ,can't you !! This is what happened in the last contest :(So, fingers crossed this time :) (y)
 » 8 years ago, # |   +8 Why is it that registration closes before contest ?? and we can't enter after the contest hast started?
•  » » 8 years ago, # ^ |   +11 Valid point. But I assume one reason may be challenge phase. If there is no registration there might not be fair and optimal way of room assignment as every body will simply log on at the time of the competition.
 » 8 years ago, # |   +8 R.I.P clarity..
 » 8 years ago, # |   -8 I submitted problem C in Java to get TLE on test case 5. Rewrote the same algorithm in C# and it passed test case 5. That's really not fair. >.<
 » 8 years ago, # |   +29 The problems translations to English needed more work. Also problems A, B & C didn't have any explanation for their sample tests.
•  » » 8 years ago, # ^ |   +8 Couldn't agree more. I took much time reading description of Problem B and hardly got how sample tests works because of no explanation, but easily understand Problem C by a quick glance.I think Problem C should be set before Problem B.
 » 8 years ago, # |   +21 i can't understand problem B :(
•  » » 8 years ago, # ^ |   +8 i have same problem. but i sent a clarify question and understood it. when you cant understand a problem you should send a clarify question. they often send you a compelete answer! sorry for my poor english.
•  » » 8 years ago, # ^ |   +2 Same here. It was very difficult understanding the problem B. But looking into the submissions in the room, I was skeptical of making my comment. I think we as a community will benefit if the problems are better written.
•  » » 8 years ago, # ^ |   +1 The same to you！！！
•  » » 8 years ago, # ^ |   0 it's the only problems that I solved :lol:
 » 8 years ago, # |   +9 The title of the competition is too difficult to read！！！
 » 8 years ago, # |   +2 Could not submit E on last minute as server was down :-( 5 additional minutes should be granted IMHO
 » 8 years ago, # |   +6 I think some phrase and grammer is difficult to realize for people have poor english like me.
 » 8 years ago, # |   +3 8 successful hacks for problem A with this test case 2 1 3 5 10
 » 8 years ago, # |   0 From where I can get the tutorials for the contest?
•  » » 8 years ago, # ^ |   0 editorials will be published after some time...
 » 8 years ago, # |   +2 I failed to submit my solution for problem C the last second before the end because I can't enter the site.what a pity!
•  » » 8 years ago, # ^ |   +1 I was in exactly same situation...15 sec remaining, I submitted problem D but.. the submission was denied..and the contest ends.. :(
 » 8 years ago, # |   +11 problems did not interesting,did not short,did not have sample test explanation,statement was not perfect.I don't like this contest :) may be becose I wrote badly ;)
•  » » 8 years ago, # ^ |   +7 E is interesting indeed.
•  » » » 8 years ago, # ^ |   0 I have no time to read problem E :( i was tryng to translate problem B with my fully english,and to solve problem D becose was thinking that problem D would be easy than problem E as usual time :)
•  » » » 8 years ago, # ^ |   0 statement says : "a graph without any loops and multiple edges" , what's meaning of loop ??
•  » » » » 8 years ago, # ^ |   +1 An edge from one node to itself
•  » » » » » 8 years ago, # ^ |   +8 "loop" != "cycle" :-| Got it !
•  » » » » » » 8 years ago, # ^ |   0 Same mistake :\
•  » » » » » » » 8 years ago, # ^ |   0 Same midtake too
•  » » » » 8 years ago, # ^ |   +5 A loop is an edge whose both ends are connected to the same vertex.
 » 8 years ago, # |   0 duh! And C went to 1000.. Scoring should be gradual not sudden like 500-1000-1500 ...
 » 8 years ago, # |   -7 When will ratings be updated???
 » 8 years ago, # |   0 For Problem C :My java code gets TLE at test 5 .This is the Code : http://codeforces.com/contest/350/submission/4630115After The contest I changed it to C++ And the same code passes :This is my C++ code : http://codeforces.com/contest/350/submission/4632017Kinda disappointing :/
•  » » 8 years ago, # ^ |   +3 I think it's because of big amount of System.out.println()
•  » » » 8 years ago, # ^ |   0 Maybe I shall use String Builder and append stuff together , but I couldn't get that this is the reason of my TLE. :/
•  » » » » 8 years ago, # ^ |   +5 You could try using PrintWriterPrintWriter out = new PrintWriter( System.out ); // all your prints out.flush() // send your prints to the outputIt is faster.
•  » » 8 years ago, # ^ | ← Rev. 2 →   0 Sorry, there is.
•  » » » 8 years ago, # ^ |   0 How do you solve it without sorting?
•  » » » » 8 years ago, # ^ |   0 I'm getting the closest points to my starting point to avoid facing a bomb in my way to a far bomb and it goes like that till the end so the condition is satisfied.
•  » » » » » 8 years ago, # ^ |   0 Ok, and how do you take the closest point to the origin?
•  » » » » » » 8 years ago, # ^ |   0 By getting the minimum sum of (x + y) for the bombs points
•  » » » » » » » 8 years ago, # ^ |   0 And isn't it faster to sort the bombs by x+y and then iterate through them? Since it is still not enough to get AC using Java, I don't think that choosing the min(x+y) with O(n) for every bomb works in 2 sec in any language.
•  » » » » » » » » 8 years ago, # ^ |   0 Sry I misunderstood you , I was explaining how im sorting them but without sorting Idk how to do it
 » 8 years ago, # |   0 From problem E:"non-directed connected graph from n vertexes and m edges, containing no loops and multiple edges"Doesn't this mean that the graph is a tree?
•  » » 8 years ago, # ^ |   +4 No, loops != circles. No loops simply means that there is no edge from one node to itself.
•  » » 8 years ago, # ^ |   0 loop != cycle. loop is an edge from a node to itself
 » 8 years ago, # | ← Rev. 3 →   0 In problem C, can anybody explain to me why this get AC, // std::sort(..., ..., cmp) ; bool cmp(dot d1, dot d2){ return abs(d1.x)+abs(d1.y) < abs(d2.x)+abs(d2.y) ; } while this was not? bool cmp(dot d1, dot d2){ if(d1.x == d2.x) return abs(d1.y) < abs(d2.y) ; return abs(d1.x) < abs(d2.x) ; // move x first, y second. } Thank you for your reading.edit: Thanks for reply. I found a test case that make sort() result not correct.a = (1, 3), b = (-1. -2), c = (1, 2) in my code (1, 3)==(-1,-2), (1, 3) > (1, 2), (-1, -2)==(1, 2) b = a, a > c, b = c → b=a>c=b, so a&c may not sort correctly.
•  » » 8 years ago, # ^ | ← Rev. 2 →   +1 Two dots: (2;10000) and (5;6). First one is definitely more distant than the second.
•  » » 8 years ago, # ^ | ← Rev. 2 →   +1 i got AC with first line of cmp being if(abs(d1.x) == abs(d2.x)) and second line same as yours above.the Manhattan distance cmp function would also give you AC.
•  » » 8 years ago, # ^ |   +1 Little tangent, but second cmp ( sort comparison function) is not right. For both calls, cmp( (5,100), (-5,100)), cmp( (-5,100), (5,100)) it returns true. It breaks transitivity. http://en.wikipedia.org/wiki/Comparison_sort
•  » » 8 years ago, # ^ | ← Rev. 2 →   0 But I got AC using both sort method above. Why?Correspondingly,
•  » » » 8 years ago, # ^ |   0 Your compare return (abs(a.x)==abs(b.x))?(abs(a.y)
 » 8 years ago, # | ← Rev. 2 →   +3 topped my room for the first time and advanced to Div-1 even though i failed A! :)P.S. very weak pretests for A!!
•  » » 8 years ago, # ^ |   0 Why does my code for Problem B give MLE? I have no idea.http://codeforces.com/contest/350/submission/4633434
•  » » » 8 years ago, # ^ |   0 Looks like recursion depth. May be could not allocate enough stack.
•  » » » » 8 years ago, # ^ | ← Rev. 2 →   0 I don't think that is the reason because I do not see any unnecessary recursive calls. It's similar to how others have done it.Edit : On taking a closer look, I realized that my code is not using a vis[] array hence, there is a possibility of it getting trapped in a cycle which causes stack overflow. You are right. Thanks :)
 » 8 years ago, # |   0 Failed to get Problem C because I used formula to find gradient instead of the distance formula. All this because I had little time left and rushed everything. Just saw that and corrected the formula to get AC. Absolutely deflated :(
•  » » 8 years ago, # ^ |   0 Thanks to the problem setter and testers!!
 » 8 years ago, # |   0 Hi, I tried debugging my codes but could not find anything wrong. Please help me to find what is wrong with my solutions.350C - Бомбы — solution id 4631490350B - Курорт — solution id 4628087The test cases are only partially shown so they were of little use.
 » 8 years ago, # |   0 I think the second test case for problem B is wrong as i got 1-2-4-5 and k=4; while the testcase says 4-5 k=2.Please can someone clarify please.
•  » » 8 years ago, # ^ |   0 Got it condition 2 of problem each object must have at most one connection to another object. I'm thinking in line of LIS is my intuition correct?
•  » » » 8 years ago, # ^ | ← Rev. 2 →   0 notice that path 2-4 is invalid as 2-3 also exists. a path is valid if the starting vertex leads to one other vertex only.
•  » » » » 8 years ago, # ^ |   0 already corrected myself my real question now is if Longest increasing subsequence is the right approach?
 » 8 years ago, # |   +2 thx this contest..I get 246 points.
 » 8 years ago, # |   0 Problem A, my program got WA on test #24 (expected 4, but got -1). I ran my code on my machine, however, the output was actually 4. I don't know why it got -1 on codeforces (even after I resubmit the code, it was still WA). Here is my contset submission 4621813
•  » » 8 years ago, # ^ | ← Rev. 2 →   +3 The second loop would be REP(i,m) for reading the b[i]'s.
 » 8 years ago, # |   0 Enjoyed the contest very much.Hacked 8 solutions successfully with the test case 3 1 3 4 5 8
 » 8 years ago, # |   +1 In my opinion, I prefer concice problem description, long description always take nonnative more time to understand, I think the algorithm matches should reduce the differences between native & nonnative.
»
8 years ago, # |
0

Can someone please tell me whats wrong with my code i've been at it for three days now i cannot seem to get the link so i'll just post the source.

Also tell me in what areas i need to improve in my coding.

## Problem B.Resort

import java.util.Scanner;

public class Resort {

static int lasth=1;
static int currmax=0;
static int newn=1;
static int n;
static int[] p;//its parent
static int[] c;//its cumulative cnt
static int[] f;//its frequency
static int[] e;//d element
static String out="";//output string.
static boolean first=true;
static String[] adj;
public static void output(int v){

while(p[v]!=0 && f[p[v]]==1 && v!=p[v]){
out = String.valueOf(v)+" "+out;
v=p[v];
}
out = String.valueOf(v)+" "+out;

}
public static void solve(){
for(int i=1;i<=lasth;i++){
//
if(c[i]!=0) continue;

if(p[i]==0){
c[i]=1;
}
else if(f[p[i]]>1){
c[i]=1;
}
else{
if(c[p[i]]==0){
int x = cntof(p[i]);
c[i]=x+1;
}
else{//count is not zero
c[i]=c[p[i]]+1;
}
}
if(e[i]==1){
if(c[i]>currmax){
currmax=c[i];
newn=i;

}
}

}
}
private static int cntof(int b){

if(p[b]==0) {c[b]=1;return  1;}

if(f[p[b]]>1)   {c[b]=1;return  1;}

if(c[p[b]]!=0)  {c[b]=c[p[b]]+1;return c[b];}

if(p[b]==b) {c[b]=1;return  1;}

else    {
int x = cntof(p[b]);
c[b]=x+1;

return c[b];
}
}

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

n=Integer.parseInt(in.nextLine());
adj = new String[n+1];
p=new int[n+1];
c=new int[n+1];
f=new int[n+1];
e=new int[n+1];

//remaining input
for(int i=1;i<=n;i++){
e[i]=in.nextInt();
if(e[i]==1)    lasth=i;
}//0 or 1.
for(int i=1;i<=n;i++){
p[i]=in.nextInt();
if(p[i]==0) {f[p[i]]=1;c[i]=1;}
else    {f[p[i]]+=1;}
if(i==p[i]) c[i]=1;
//if(p[i]<i && c[p[i]]!=0)    c[i]=c[p[i]]+1;
if(f[p[i]]>1)   c[i]=1;
if(e[i]==1 && c[i]!=0){
if(c[i]>currmax){currmax=c[i];newn=i;}
}

}

solve();

output(newn);
System.out.println(currmax);
System.out.println(out);

}`

}

 » 7 years ago, # |   +5 Problem C's TL should be increased. this tight TL is not fairHere is my code which at first stocked at test 5 after adding "ios::sync_with_stdio(false)" it passed and again stocked at test 6here is my submission http://codeforces.com/contest/350/submission/7048251just look at the times in AC codes here : http://codeforces.com/contest/350/status/C
•  » » 7 years ago, # ^ |   0 I see there times like 904 ms with python...By the way, I submitted your code with endls replaced with '\n' and look: http://codeforces.com/contest/350/submission/7049199 280 ms.
•  » » » 7 years ago, # ^ | ← Rev. 2 →   +5 that's interesting ! what a diffrence !an unrelated question to my first post : what is the diffrence between '\n' and endl ?thanks in advance