### Alex_KPR's blog

By Alex_KPR, 8 years ago, translation, ,

Hi all!

Now it's time for 80th Codeforces Beta Round.

The authors of the contest are: Alex_KPRwingerRADConnectorit4.kp. I hope all problems will be interesting for you and not extremely hard. ;)

Today is Connector's birthday — so, let's congratulate him together!

Good luck and have fun!
_____________________________________

Thank you for your action! =)

Top 10 participants in the first division are:

 Place Who 1 SergeiRogulenko 2 hos.lyric 3 Romka 4 neal 5 sdya 6 KADR 7 ftiasch 8 niyaznigmatul 9 dolphinigle 10 AleX

There are only two participants who beat problem E: the winner of the contest SergeiRogulenko and MBabin who gets 76th place.

Top 3 participants in the second division are:

 Place Who 1 anrieff 2 zplinti1 3 Efgen

Congratulations and good luck at the next time!

Official tutorial will be added later. But AlexanderBolshakov already wrote the tutorial about most of problems.

Problems were translated by
_____________________________________

Tutorial is here.

•
• +208
•

 8 years ago, # |   +5 Yes goodluck to all:)
•  7 years ago, # ^ |   0 thx buddy!
8 years ago, # |
Rev. 4   +47

first thing i would to congratulate to and say HAPPY BIRTH DAY :)
second if you want to solve problems written by one of problems authors see below contests

### Codeforces Beta Round #58Codeforces Beta Round #69

•  8 years ago, # ^ |   +5 i want to know only one reason for voting negative to previous post .:(
•  8 years ago, # ^ |   -54 You are green
•  8 years ago, # ^ |   +6 И ето говорит тот, кто даже цвета не имеет :D
•  8 years ago, # ^ |   +2 Зато честно.
•  8 years ago, # ^ |   +2 Вы не подумайте, я лично его не минусовал.
 8 years ago, # |   0 Wish you a Happy BirthDay Good Luck Everyone :-)
 8 years ago, # |   0 Happy BirthDay,Connector
 8 years ago, # | ← Rev. 2 →   +32 .. (I am Sorry .. for disturb you ..now this time ..)..Happy Birthday .~
•  8 years ago, # ^ | ← Rev. 2 →   0 Outdated comment
•  8 years ago, # ^ | ← Rev. 2 →   +17 http://codeforces.ru/helpItem 6.If some people break the few rules we have here for communication, that's not a valid reason to break them too.
•  8 years ago, # ^ |   -8 Я себя каждый раз сдерживал, чтобы не написать то же самое, что написал Vasya. Как приятно читать его сообщение, надеюсь, что такие будут раздаваться после каждого набора иероглифов.
•  8 years ago, # ^ |   0 Учитывая что человек (якобы) из Китая написал по-японски, он явно имел в виду что-то столь же чуждое ему, как и нам... ;-)
•  8 years ago, # ^ |   +21 This is English thread, so please do not break the rules you are insisting to enforce so vigourously
•  8 years ago, # ^ |   +18 By the way, he just said "Happy birthday".
•  8 years ago, # ^ |   +16 Don't be so rude! I think it's a pleasure to receive a congratulation from international students. Especially if it's in their native language.
•  8 years ago, # ^ |   -37 молю бога, чтобы в будущем не было японских или китайских веток.
•  8 years ago, # ^ |   +63 Why Russian threads are ok, but not Chinnese or Japannese? Because you do not understand them? By the way, formally this is English thread, so please refrain from using Russian here
•  8 years ago, # ^ |   +1 Respect!I think it is impolite at all to write in Russian anything while here is kept _international_ contest. Especially in the topic about this contest.All foreigners would spent their time trying to check with google-translator whether all these Russian guys are discussing contest problems or chatting about something else...
 8 years ago, # |   +40 Loved the contest :)
 8 years ago, # |   +4 Happy birthday, Connector! :)It was such an interesting contest. The guy called Cthulhu was funny :) Good job! Thanks to the organizers. Keep up the good work :)
 8 years ago, # |   +11 Really love this contest.Especially the Problem C, it is very creative.And the pictures in Problem B & D is so cool! Who is the author?
•  8 years ago, # ^ |   0 That is actually written in the blog post itself :D
•  8 years ago, # ^ |   0 I think he meant the author of problem C.
 8 years ago, # |   +5 Nice set of Problems... !!
 8 years ago, # |   +1 What's wrong with sys.tests in DIV2?
•  8 years ago, # ^ |   0 I see, only xiaowuc1 problem testing, but for a long time. Why?
•  8 years ago, # ^ |   0 I've noticed, his solution doesn't have "return 0" in the end. Maybe, the root of the problem are there?
•  8 years ago, # ^ |   -12 Java is such a Java. I mean that CF is written in Java.
•  8 years ago, # ^ |   0 Do you think that compilers and scripts used for testing solutions are written in Java?
•  8 years ago, # ^ |   -11 I know that only javac is written in Java, but I also know that the source of the error must is in the Java code.
 8 years ago, # |   +16 Today it's my birthday too (seriously)
•  8 years ago, # ^ |   +20 With over 1300 competitors there is a great chance that there are also at least two more people with a birthday today.
•  8 years ago, # ^ |   0 oh, realy?Good story, bro!
•  8 years ago, # ^ |   0 That's true :)
•  8 years ago, # ^ |   +4 I'm another person with a birthday today :D
•  8 years ago, # ^ |   +2 Best wishes :)
•  8 years ago, # ^ |   0 Thanks :)
 8 years ago, # |   +25 First of all - great contest!On an unrelated subject I was wondering whether it is not a good idea to modify either the Div1/Div2 limits or the formula for increasing rating of lower-rated (i.e. blue and below) coders to gain more points by performing well, because now Div1 has around 300 contestants and Div2 has over 1000. In my opinion it would be better if the numbers are more balanced.
•  8 years ago, # ^ |   0 Absolutely agree. The current formula make less stable Div 1
•  8 years ago, # ^ |   +17 Also now I noted that the winner of Div2 has solved more problems than me (since their B, C, D, and E are equivalent to our A, B, C, and D) and gains less rating then I did. That's surely odd.About problem E (in div2) which was the same as D in div 1:Looking at the constraints we can see that N * sqrt(N) solution will pass. Let's for clarity call the queries' pair (a, b) as (start, skip). Now we can divide the problem into two: if skip is more than or equal to sqrt(N) we can use the naive algorithm that just implements the check - then the query has complexity O(sqrt(N)). If skip is less than sqrt(N) we use another algorithm - we precalculate for each possible skip (up to sqrt(N)) and each index from 0 to skip - 1 what is the sum of numbers in positions, that give remainder index when divided by skip. We group each sqrt(N) consecutive values into buckets. This precalculation takes O(sqrt(N) * N) time and memory (which is over the memory limit, but we will fix that later).Now, for each query in which the skip part is less than sqrt(N) we can iterate from start upwards until we reach new bucket (and accumulate the current result). After we leave the bucket, we no longer need to accumulate the answer value by value but we can do it bucket by bucket instead (which is okay, since we want ALL values until the end). So we must iterate at most one bucket in O(sqrt(N)) and at most the rest of the buckets, which is also O(sqrt(N)). So the overall time for the query is also O(sqrt(N)) (after doing the precalculation).By now we have precalculation which is O(N * sqrt(N)), query of type 1 which has complexity O(sqrt(N)) and query of type 2, which has complexity O(sqrt(N)). This is sufficient for solving the problem in the given time limit.The only problem left is what to do with the insufficient memory. If you've ever seen dynamic programming problems with memory optimization done by iterative calculation of values (removing one of the states of the table), then the optimization we can do in this problem is almost the same. We sort the queries by 'skip' (in ascending order) then calculate only part of the table for each skip (thus compressing the memory by sqrt(N)). We then store the answers for each query (using queries of type 1 or 2, depending on the skip value) and in the end just print the results in the correct order.Long description, but hopefully useful for some! :)
•  8 years ago, # ^ |   +11 It seems like I missed one of the best rounds. I really liked the problemset. I think there are too many things that could be improved in Codeforces.  Some Div 2 coders are really good and rating system is really strange.One thing that I would like to see very much is the problem statistics. For example, after each problem they could post the percentage or number of with verdicts "failed pretest" , "hacked", "failed system tests", and "accepted", not only the number of accepted submissions.
•  7 years ago, # ^ |   0 Me Gusta!
•  8 years ago, # ^ | ← Rev. 3 →   0 I tried espr1t's approach with buckets  .. useful to me at least!  :).. but it fails on example 8.Unfortunately I can't reproduce the error, the list of values in the input is truncated.It's correct on several random examples with either b smaller or larger than sqrt(N).link to the C++code.I wonder why it's incorrect.  Does anyone see? Thanks a lot for your help!Update:  Example 8 is the only one which fails.  I added a condition to treat it separately with the naive algorithm, and that passes the tests now.
•  8 years ago, # ^ |   0 Yes ,I agree .It would be great idea...
 8 years ago, # |   +1 I had a query concerning Problem C Div 2. I solved it using the following approach in practice :-1. First find if the graph has a cycle. If not return NO.2. Now try removing a edge each time, and run a bfs to see if there is no cycle anymore. If there is no cycle anymore, try to find the nodes between the two nodes for which you removed the edge. There are our possible roots for the rooted trees. Check if indeed these are roots. If no return NO, else return FHTAGN.Is there a better approach then this ?
•  8 years ago, # ^ |   +13 If a connected graph has n - 1 edges then it's a tree, and adding one edge will result in a cycle with trees going out of each cycle node. So it's enough to check if n = m and the graph is connected.
•  8 years ago, # ^ |   +5 Thanks. This was too simple and elegant. :)
•  8 years ago, # ^ |   +7 I used a topological sort type of algorithm:1. make sure the graph is connected (DFS)2. remove "leaves", i.e. nodes with degree 1 until there are none left3. check that the resulting graph is a circular, i.e. there are at least 3 nodes and each has degree 2
•  8 years ago, # ^ | ← Rev. 3 →   +1 if n=m and the graph is connectd return FHTAGN(you can use union-find set)else return NO
•  8 years ago, # ^ |   +5 One more approach is to use a DFS which counts the number of simple loops in the graph.Having performed it you just check that only one loop was found and that the graph is connected.However, m = n check is surely more elegant way :)
•  8 years ago, # ^ |   0 During contest i just checked two condition ....This graph has a single cycle and every vertices connected...if yes than FHTAGN else NO.I did this through DFS.
 8 years ago, # |   +2 Problemset and statements of last 2 contests have been pretty good,thanks to problem-setters.
 8 years ago, # |   0 Can somebody explain Div2 Problem. D and Problem. E ??Thx a lot!
•  8 years ago, # ^ | ← Rev. 2 →   -10 Can't you just take somebody's working solution and execute it with different tests? Well, it's about problem D. About E I think that you should use segment trees.
•  8 years ago, # ^ |   +5 How to use segment trees in E?
 8 years ago, # |   0 In Problem D. I don't even understand sample data5 2 512345why is it ...XXthis configuration Sasha will have 3/5 probability to lose while .X.X.being 3/5 to win. why is ...XX the answer?
•  8 years ago, # ^ |   0 Actually it' said in problem statement - "Sasha selects any k out of n slots he wishes and puts bullets there. Roma spins the cylinder so that every of n possible cylinder's shifts is equiprobable." This means that after selection the cylinder can be shifted and the position of slots will change
•  8 years ago, # ^ |   0 Your chance to win with .X.X. is 2/5, and not 3/5. You will lose if the roullete stops at some of the two Xs or if it stops at the last position (you will survive the first shoot, your enemy will survive the next one (there's a dot at the first position) and then you will die (there's an X at the second position)). So there're 3 positions out of 5 where the roullete may stop to make you lose.Both configurations give you the same change of surviving, but "...XX" is lexc. smaller.
 8 years ago, # |   0 it seems that there are something wrong with Judgement. It cannot judge.
•  7 years ago, # ^ |   0 which pokemon is your avatar
•  7 years ago, # ^ |   0 Dickimon LOL
 8 years ago, # |   0 Are there any data sets in DIV I E like this?22 1 22 1 2-2 -3Are there any pairs of sets exactly the same?
•  7 years ago, # ^ |   0 No buddy...LOL
 8 years ago, # |   +1 I am from China.Happy birthday,connector.生日快乐！
8 years ago, # |
Rev. 2   +4

8 years ago, # |
Rev. 4   +4

### Since I can't delete my comment, just smile for your attention :)

•  8 years ago, # ^ |   0 +9 (altogether for the previous 3 posts) for double posting with huge font? I have some feeling that if you were a guy (or at least didn't have that picture) it would be a whole different story...
8 years ago, # |
Rev. 2   +4

### I have a suggestion that the window popped-up is too small when viewing others' sources during hacking and the source font is not suitable enough.I think the font "NewCourier" is better.

Sorry for my poor network. I am not on purpose to type it many times.