Endagorion's blog

By Endagorion, 6 years ago, translation,

Hi, Codeforces.

Today, on December 17 at 19:30 MSK regular, 283-rd Codeforces round will take place. Problems are authored by me, Mikhail Tikhomirov. Maxim Akhmedov (Zlobober) helped me with discussing and preparing the problemset, Maria Belova (Delinur) translated problem statements in English, and Georgy Chebanov (gchebanov), Alexander Mashrabov (map) and Niyaz Nigmatullin (niyaznigmatul) tested the round and helped us with finding bugs and mistakes; let's give them a round of applause!

The round will be for both divisions. The scoring is standard (not dynamic); score distribution is as follows:

Div. 1: 750-1250-1250-2000-2500

Div. 2: 500-1000-1750-2250-2250

This is going to be my fourth round at Codeforces. I really hope it will go as good as three before it. =) Wish you all the best of luck!

UPD: the round is over, thanks for participating!

Grats to the winners:

Div. 1:

Div. 2:

Editorial is here ( UPD: now in English!).

• +595

 » 6 years ago, # |   0 Is this the record for shortest round announcement? Very concise and direct. Lets hope problem statements are same way
•  » » 6 years ago, # ^ |   +62 Have to hope editorial is the opposite, however.
•  » » 6 years ago, # ^ |   +14
 » 6 years ago, # | ← Rev. 3 →   +4 The first three characters of your name are "End", I hope this contest won't put the end of my green color.
•  » » 6 years ago, # ^ |   0 Hopefully this will put the end of my blue colour; I hope to be purple again :)
 » 6 years ago, # |   +17 Why is this blog annoucements, statements, tutorials of a lot other contests?
•  » » 6 years ago, # ^ |   +61 Perhaps he was thinking, "Hmm, the blog announcement is so small, maybe I should add lots of attachments with it to make it bigger" :p
•  » » » 6 years ago, # ^ | ← Rev. 3 →   0 I don't think so.Endagorion can write a lot's of things to make blog longer.I think somebody attached to this blog these contests. But why??? That's interesting.
•  » » » » 6 years ago, # ^ |   0 What you are saying kind of makes sense. Why would this blog post be "Tutorial of 2010-2011 VII International Zhautykov Olympiad"? I guess somebody is just messing around :p
•  » » » » » 6 years ago, # ^ | ← Rev. 2 →   +7 The "someone messing around" theory makes the most sense IMO. I think anyone can create attachments like this (at least I can -- or maybe it's just people with coach mode enabled?)
•  » » » » » » 6 years ago, # ^ |   -13 what is coach mode? and who can enable it?
•  » » » » » » » 6 years ago, # ^ |   +5 A coach can create new contests in the Gym and view others' submissions to Gym problems.For the conditions to have a coach account, see http://codeforces.com/blog/entry/11037#comment-161942 (you have 28 contests, so you'd need 2 more).
•  » » » » 6 years ago, # ^ |   +10 Or it's a bug, probably?There's a blog post that has a similar issue (this post).The attachments to that post aren't related to the post itself, just like this blog post.
•  » » 6 years ago, # ^ |   +14 I have no idea what was the deal with all these. Deleted them anyway.
 » 6 years ago, # |   0 I hope that it will be interesting.
 » 6 years ago, # | ← Rev. 3 →   -21 Topcoder Rating are increse. Codefores Rating are waiting......increse/decrese.
 » 6 years ago, # |   +1 You forgot to thank MikeMirzayanov for creating Codeforces and Polygon systems :D Fingers crossed. Lets hope that there are no server errors :P Just kidding, thank you for writing this round, your previous contests were also good.
 » 6 years ago, # |   +9 It seems the Codeforces Google Calendar is out of sync or the entry for this contest has not been added to it. It is kind of sad as I will not be able to participate because of that.
 » 6 years ago, # |   +9 Time to dreamoon.
•  » » 6 years ago, # ^ |   +131 Preparing the contest is exciting partly because you know all the decent coders out there will try their best to solve your problems; it's a pity to know that some of them prefer to opt out of fair competition.
•  » » » 6 years ago, # ^ |   0 What's wrong with dreamoon's account?
•  » » » » 6 years ago, # ^ |   0 See his rating graph
 » 6 years ago, # |   +2 The last Endagorion contest was a failure for me! I hope it will be different today! :D
 » 6 years ago, # | ← Rev. 3 →   0 Hi!Endagorion thanks! your last contest had nice problem :))
•  » » 6 years ago, # ^ |   -10 Hi! Endagorion thanks! your last contest had nice problem :))
•  » » » 6 years ago, # ^ |   0 Oh...I typing very fast so I'm Careless!
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   +3 Me too... I type too fast and im very very careless because of that http://paste.ubuntu.com/9551585/ EDIT: this is just a joke dont take it seriously guys
•  » » » 6 years ago, # ^ |   0 "Hi!" must be in a new line :P
 » 6 years ago, # | ← Rev. 2 →   +47 All of your contests were Div1 + Div2. And you prepared all the problems alone. Today, There are a lot of contests that there is a team with 7 members for preparing problems but the contest is just Div2. Thank you so much.
 » 6 years ago, # |   0 I hope all Specialist be Expert and all Expert be master !
•  » » 6 years ago, # ^ | ← Rev. 3 →   -31 deleted
•  » » » 6 years ago, # ^ | ← Rev. 2 →   -26 deleted
•  » » 6 years ago, # ^ | ← Rev. 2 →   +8 Then to balance it, each Pupil will become Newbie and each Newbie's rating will decrease :(
•  » » 6 years ago, # ^ |   +5 I think it is very difficult to make a jump from Expert to Master.
•  » » » 6 years ago, # ^ |   +10 Look at this profile: mhadih Look at his red dot. It's not from Expert to master but it's very close.
•  » » » 6 years ago, # ^ |   +1 impossible is nothing :) --> Ibragim
 » 6 years ago, # |   -34 hello every bodydis like me plz
•  » » 6 years ago, # ^ | ← Rev. 2 →   +11 are you sure? Link :p
•  » » » 6 years ago, # ^ |   -6 He needs to be more original if he wants to break that record!
•  » » 6 years ago, # ^ |   0 lol, it has been a while since "Dislike Me" posts have been made in a round. Not that the absence made it any better...
 » 6 years ago, # |   0 The contest will begin at 0:30 am in China, luckily, i have no courses tomorrow :)
 » 6 years ago, # | ← Rev. 2 →   +5 Hope for high rating.
•  » » 6 years ago, # ^ |   0 Everyone does.
•  » » » 6 years ago, # ^ |   +76 Except dreamoon.
•  » » » » 6 years ago, # ^ |   +14 Too bad worse gave up...
 » 6 years ago, # |   0 Hopefully this contest increase my rating and also others rating ;)
 » 6 years ago, # |   +6 Speed of internet is so slow when there is a ten minutes to the contest
 » 6 years ago, # |   +14 The age of unusual score distribution.
 » 6 years ago, # |   +4 All of us second division participants, this is our last chance to win (as dreamoon has almost arrived !)
 » 6 years ago, # |   +3 Note to self: avoid geometry =(It comes down to segment vs ellipse (possibly degenerate) intersections, right?
•  » » 6 years ago, # ^ |   +8 Yes, in fact it's segment vs. circle intersections.
•  » » » 6 years ago, # ^ |   0 It would be a circle if they rotated in different directions. Unless you mean you get a circle after squeezing the ellipse along one of the coordinates.
•  » » » » 6 years ago, # ^ |   0 Well, I believe that it's circle when they rotate in the same direction. And with this approach I passed pretest, so it might be correct.
•  » » » » » 6 years ago, # ^ |   0 Uh if you consider the movement a point X on the second polygon relative to P, you will notice that Q rotates around P counter clockwise, and X around Q clockwise. If you add these two movements, you will get an ellipse (assuming |XQ| != |PQ|, otherwise it will be a segment).
•  » » » » » » 6 years ago, # ^ |   0 Well, in frame of reference where A isn't moving point Q rotates around P CCW, but as the frame of reference is rotating CW itself, X will not rotate around Q at all.
 » 6 years ago, # |   0 was div1 C bipartite matching? or could something like sorting and 2 pointers work? :\
•  » » 6 years ago, # ^ | ← Rev. 2 →   +10 Sorting and two pointers. Assign the scenes greedily (take the ones with lowest A that satisfy the conditions). Good luck with bipartite matching when you have 10^5 nodes and 10^10 edges ;p
•  » » » 6 years ago, # ^ |   0 Did something similar.. pretest 5 :\
•  » » » » 6 years ago, # ^ |   0 I had an issue with it too, because I was sorting by the wrong coordinate (forgot to pass my comparison function).
•  » » » » » 6 years ago, # ^ |   0 Would you mind telling the order of each parameter you used for sorting?
•  » » 6 years ago, # ^ |   0 greedy is enough
 » 6 years ago, # |   0 When will system testing begin?
 » 6 years ago, # |   0 Your contest have nice problem :)thanks Endagorion
•  » » 6 years ago, # ^ |   0 I'm surprised that div.2 problem is hard for everyone, this is the first time I made to the top 3 in my contest room eventhough I only solve one problem lol. I can't believe it >.<.
•  » » » 6 years ago, # ^ |   0 nice problem != hard problem !
 » 6 years ago, # |   0 I think it is time for me to say "Goodbye Expert".
 » 6 years ago, # |   +9 What is the solution of B problem? It was harder for me than C :D
•  » » 6 years ago, # ^ |   0 Simple bruteforce
•  » » 6 years ago, # ^ |   0 Bruteforce all possible shifts and increasing by 1.
 » 6 years ago, # |   0 How to solve Div1B/Div2D
•  » » 6 years ago, # ^ |   +10 Go through the list from left to right to get all possible values of T. For every value, you can 'simulate' the match by using binary search to find where the sets end (calculate partial sums of the number of wins of each player), and check whether you get a valid match (and obtain S in the process). It will work quickly enough because you only try each T once, and the complexity of each simulation is (n/T)*log(n). If you add them together, you will get (n+n/2+n/3+...)*log(n) = n*log(n)*log(n).
•  » » » 6 years ago, # ^ |   0 I did the same thing. Can you please take a look at my soln ?http://codeforces.com/contest/497/submission/9176658
•  » » » 6 years ago, # ^ |   +3 actually binary search is not necessary. you can just store at what index does your ones (twos) become wanted value. so complexity becomes n * log(n)
•  » » 6 years ago, # ^ |   +5 I stored the first position of a particular number of games won and simply simulated for all values of t from 1. This would be O(nlogn)
•  » » 6 years ago, # ^ |   0 You can fix the T in the interval 1, n. Now, you are going to see for each set where does it and and where does it begin.Also, you have maximum N / T sets. You can determin this intervals using binary search. So you have Nlog^2N.
 » 6 years ago, # |   0 The fact that in Div2 there are less than 10 successfull hacks from current top500 is not good
 » 6 years ago, # |   0 Nice problems thanks a lot authors
 » 6 years ago, # |   0 if cnt[1] == cnt[2] cout << 0; <- i wrote it in the beginningok kill me pls :(
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 Welcome to the club. 9178079 9176101
•  » » 6 years ago, # ^ |   0 Any test case for contradiction of ( if cnt[1] == cnt[2] cout << 0; ) ??
•  » » » 6 years ago, # ^ | ← Rev. 3 →   +2 Sorry, wrong probem O:-)
•  » » » 6 years ago, # ^ |   +3 The number of total points doesn't mean much. For example, the person that won less points may be the final winner.Example: s = 4, t = 2 18 2 2 2 2 2 2 1 2 1 1 2 1 1 2 1 1 2 1 2 wins 10 serves, 1 wins 8 serves and 1 wins the game. Kind of unfair, isn't it?
•  » » » » 6 years ago, # ^ |   0 Even simpler:8 2 2 2 1 1 2 1 1
 » 6 years ago, # |   +3 What was the tricky #8 case in D?
•  » » 6 years ago, # ^ |   0 I have no idea, but did you consider the case, when a segment crosses a circle, while both its ends are outside of it?
•  » » » 6 years ago, # ^ |   0 As far as I remember, not considering this gives WA6.
•  » » » 6 years ago, # ^ |   0 Yes, I did. But considering it was pretty long "if", I hope it was correct, I've read it many times xd.
•  » » » 6 years ago, # ^ |   0 OK, my solution just contained many bugs (what is funnier, not in formulas) and this test was one of the first test checking anything :P.
»
6 years ago, # |
-18

Hey @admin : I submitted the code when there were 7 seconds left. It didn't accept my code.Please evaluate it :( Problem D

include

using namespace std; int n,a[100000],f[100000],x=0,y=0,ans[10000000],ac=0; int fact(int o) { for (int i=1;i<=f[n-1];i++) { if (o%i==0) {

       ans[ac]=i;
ac++;
}
}
return ac;


} int main() {

cin>>n;
for (int i=0;i<n;i++) cin>>a[i];
for (int i=0;i<n;i++) {
if (a[i]==1) x++; else y++;
f[i]=max(x,y);
}
int z=fact(f[n-1]);
if (x==y) {
cout<<"0";
} else {
cout<<ac<<endl;
for (int i=0;i<ac;i++) {
cout<<ans[i]<<" "<<f[n-1]/ans[i]<<endl;
}
}


}

•  » » 6 years ago, # ^ |   0 You will get WA for this: a player can get some points in sets he didn't win, so his total wins don't have to divide equally by T.
•  » » » 6 years ago, # ^ |   +4 Yeah , your correct. That makes me feel better :PThanks :)
•  » » 6 years ago, # ^ | ← Rev. 2 →   +5 7 seconds might be wrong time synchronization in browser...
 » 6 years ago, # |   +61 http://codeforces.com/contest/497/submission/9163878 dreamoon, you are so cute...
•  » » 6 years ago, # ^ |   +30 tourist makes a new account, dreamoon 2nd on division, a programmer shot himself in a mystrious incident. sad short story :D
•  » » » 6 years ago, # ^ |   0 Or he may just try one more time:)
•  » » » » 6 years ago, # ^ |   0 Not with the newly increased rating.
 » 6 years ago, # | ← Rev. 2 →   +24 As always I finish debugging my E code on examples 2 minutes after round end...I'm actually hoping it's wrong now, would make me less angry :KEdit: Yay, TLE! :)
 » 6 years ago, # |   0 System test started early, but, it is slow. There is always a catch huh...
 » 6 years ago, # |   0 How to solve Div2B?
•  » » 6 years ago, # ^ |   +5 Just try all possibilities...
 » 6 years ago, # |   +4 bitagi97 submitted all 3 problems (A, B, C) in time 00:41 interesting...
 » 6 years ago, # |   0 Why is the system testing so slow??
 » 6 years ago, # |   +16 Dear CodeforcesPolice , Look what SaDDaS did during contest time !
 » 6 years ago, # |   +24 The rating update is so fast. Maybe the fastest I've ever experienced.
•  » » 6 years ago, # ^ |   0 Still waiting for Div 2 update.
•  » » » 6 years ago, # ^ |   +11 Updated on the moment you write this comment :)
•  » » » » 6 years ago, # ^ |   0 Hey Bro, I can't change the downvote to the upvote. Sorry for that.
 » 6 years ago, # |   +20 accidentally fell asleep during the contest for half an hour :D , and solved problem C after waking up
•  » » 6 years ago, # ^ |   0 Still better, than sleeping 10 minutes and then submitting A :-D Especially when no reason for that...
•  » » 6 years ago, # ^ |   +33 Being relaxed during a contest — i guess you are doing it wrong)
 » 6 years ago, # |   +3 Yeah, purple again C:
 » 6 years ago, # |   0 Solved B and C, and couldn't get A to pass the pretests (was giving wrong answer on Pretest-7)! Did anyone face the same issue?
•  » » 6 years ago, # ^ |   0 You didn't set variable Difficulty to -1 at the start of for loop which means that it will not reset when you delete new element from array and it will use an old value. I just did that and your code passed.
 » 6 years ago, # |   +2 Finally, I became blue. Next stop: purple :)
•  » » 6 years ago, # ^ |   0 wow your line is motivated.welcome to bule!
 » 6 years ago, # | ← Rev. 6 →   +40 I'd like to talk about time limit in problem D (div 1). I'm really sad, because I spent about 50 minutes on solving this problem and submitted it during last minute of contest just to get TLE on test 30. And, what is even worse, I changed my code just a bit after the contest and got AC.As you can see, the main difference is that the new code is less legible. Complexity is the same as in codes of others — O(nm), but the constant is just a bit worse. I don't think that making such time limits in geometrical problems is a good idea.I'm not the only person with this problem — AstroConjecture also has tle on 30.So I'd like to write my reflections here: 1) Time limit could be less strict when there is no solution with worse complexity that could work with given constraints.2) There should be one maxtest in pretests. In such problems people often try to write legible codes (it helps with debugging) and they focus less on constants (of course they still focus on complexity). So I think that here lack of maxtests in pretests is a huge mistake.
•  » » 6 years ago, # ^ |   +10 Fully agree. I always emphasize that constraints should be as small as they can be, so no solution with worse complexity can pass. Here there were simply no other solutions, but on the other hand, 1000 is in fact already very small limit...But 2) still stands, receiving a random TLE on systests, because our code runs for sth like 1.5xTL is really a terrible feeling, I experienced that few times here and it always costed me sth like 150-200 rating >_<.
 » 6 years ago, # |   +15 welcome dreamoon to div 2
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 welcome DmitriyH to div 2 too :D
 » 6 years ago, # |   +3 Hello purple! Thank you for a great contest :D
 » 6 years ago, # |   0 Div2 C, what is it that I'm doing wrong in this codehttp://codeforces.com/contest/496/submission/9178659
•  » » 6 years ago, # ^ |   0 I have the same problem, test 15 didn't go through. To me, the test case seems to have clearly more than 4 columns to be removed in order for the rows to be ordered lexicographically. Or did I misunderstood the problem somehow???http://codeforces.com/contest/496/submission/9174356
•  » » » 6 years ago, # ^ |   0 The rows must be ordered lexicographically from top to bottom that is the problem. And yes the answer can be more than 4.
•  » » 6 years ago, # ^ |   0 as rajateuler said, one has to go from row to row, not column to column. else it's getting to complicated to decide either the column has to be removed (here is the error).
 » 6 years ago, # | ← Rev. 2 →   0 EDIT: Ignore this post.
 » 6 years ago, # |   0 I really wanted my name written here but sadly i got the sixth place in the last 3 minutes...
 » 6 years ago, # |   0 in round #283 div 1 I am not able to understand for which test case my problem fails. http://ideone.com/My5SeW it gives WA in test case 15
 » 6 years ago, # |   0 Hi. Can anyone please help me understand why test 2's answer is 2 instead of 3?case care test codeShouldn't all columns except the second one be deleted? Because the 1st, 3rd and 4th columns all have irregularities in terms of lexicography. Or did I misunderstand the question completely? :|
•  » » 6 years ago, # ^ |   0 Read the definition of lexicographic order carefully. Even though the strings in column 4 e e t earen't in order, the strings ae ae et oeare, so it's a valid solution.
•  » » » 6 years ago, # ^ |   0 Hey Kynit, i don't understand the definition of lexicographic order.Even i don't understand the second test case how output 2 comes instead of 3. Would you please explain with another example for understanding the definition of lexicographic order ? Thanks in advance.
•  » » » » 6 years ago, # ^ |   0 Let's say that you have string a and b. And for example a=abcd, b=acde.In string b char on position 2, char 'c', is greater than char on position 2 in string a, char 'b' (c come after b in english alphabet), which means that b is lexicographically larger than a. They don't need to have same length, only one char is enough to one string be lexicographically greater than other. For example string b=s. Char 's' on pos 1 is greater than char on pos 1 in string a, char 'a', so string b is lexicographically greater than string a.
•  » » » » » 6 years ago, # ^ |   0 I thought all character must be greater than the previous one. that's my fault. thanks Yosemite. Your explanation are awesome.
•  » » » » 6 years ago, # ^ |   0 Yosemite got it right — it's basically dictionary order.
 » 6 years ago, # |   0 My code for div1B failed on test45 during system testing, and that test case works perfectly on my machine. Can anyone help, what might be the issue?
 » 6 years ago, # | ← Rev. 2 →   +4 Dear CodeforcesPolice I got this message during the contest. I've noticed that after the end of contest. Of course, it is not allowed to ask someone the solution or something like that. Is there anyone who get this type of message from hamidrezah during contest?
•  » » 6 years ago, # ^ | ← Rev. 3 →   +11 Do you know Hamidreza Hedayati?I just know this handles of him:TyperX , hrh2020 ,hamidreza004 , hamidreza.dev , hamidreazshr ,hamidrezah.I know that he has some more handles but i don't know them. I think your next target should be him.
 » 6 years ago, # |   0 Is the editorial in English ready yet? :) Thanks for posting.
 » 6 years ago, # |   0 Waiting for English verison of Editorial.:D
 » 6 years ago, # | ← Rev. 2 →   -29 .
•  » » 6 years ago, # ^ |   +6 Notice the "#" sign beside his name. That means this rank is unofficial since he took a "Virtual Contest". Just remove the tick from "show unofficial" above the standings page, and he will disappear.
•  » » » 6 years ago, # ^ |   +5 Probably someone who cannot read well: If you've seen these problems, a virtual contest is not for you — solve these problems in the archive.If you just want to solve some problem from a contest, a virtual contest is not for you — solve this problem in the archive.Never use someone else's code, read the tutorials or communicate this other person during a virtual contest. Above are "Terms of agreement" when one want to start virtual contest...
 » 6 years ago, # |   +13 Are Petya and Gena from 497B - Tennis Game Petr and tourist? XD
•  » » 6 years ago, # ^ |   +24 Yep; actually, both of them are quite adept at table tennis which I had a chance to witness at TCO14 finals. =)
 » 6 years ago, # |   0 Can anyone tell me why my submission 9186328 for problem C div 2 is failing the system test. Here is my algorithmStarting from the first column, I check if it's sorted, if it's not sorted I mark it for removal and move on to the next column. If it is sorted, I group the rows with the same value at that column and I move on to the next column within each group.
 » 6 years ago, # | ← Rev. 2 →   0 Can anyone please tell me why 1 15 1 is not an answer for following test case in problem 496D - Tennis Game 20 1 1 2 2 2 2 2 2 2 2 2 2 1 2 2 1 2 2 2 1 
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 Ignore this answer.
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 Why? in testcase 7 judge's output is 0. I can not understand why 1 15 1 is not an answer.
•  » » » » 6 years ago, # ^ |   +1 If it would be answer, second player would win earlier than game has ended (testcase is entire game, from start to someone's win).
•  » » » » » 6 years ago, # ^ |   0 How would second player win earlier? When the game ends first player wins 5 sets while 2nd player wins 15 sets. As score is 1, they are completing 20 sets together, and 2nd player wins his last set at the last serve of the game, isn't it?
•  » » » » » 6 years ago, # ^ |   0 I got it. Thanks for explaining. I missed last "1"
 » 6 years ago, # |   0 Hi there. I'm trying to solve 496C but I'm stuck on test 20.Can someone point me in the right direction? [http://codeforces.com/contest/496/submission/9372508](http://codeforces.com/contest/496/submission/9372508) Thanks in advance!
 » 6 years ago, # |   +3 a very bad and unpleasant round