Alex_KPR's blog

Codeforces Beta Round #80
By Alex_KPR, 13 years ago, translation, In English

Hi all!

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

The authors of the contest are: Alex_KPR, winger, RAD, Connector, it4.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 Delinur.
_____________________________________

Tutorial is here.

  • Vote: I like it
  • +208
  • Vote: I do not like it

Comments Comments (69)
| Write comment?
13 years ago, # |
  Vote: I like it +5 Vote: I do not like it
Yes goodluck to all:)
→ Reply
13 years ago, # |
← Rev. 4   Vote: I like it +47 Vote: I do not like it

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

Codeforces Beta Round #9

Codeforces Beta Round #58
Codeforces Beta Round #69


→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Wish you a Happy BirthDay Connector :)
Good Luck Everyone :-)
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Happy BirthDay,Connector
→ Reply
13 years ago, # |
← Rev. 2   Vote: I like it +32 Vote: I do not like it

.. (I am Sorry .. for disturb you ..now this time ..)
..Happy Birthday .~
→ Reply
  • 13 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Outdated comment
    → Reply
    • 13 years ago, # ^ |
      ← Rev. 2   Vote: I like it +17 Vote: I do not like it
      http://codeforces.me/help
      Item 6.

      If some people break the few rules we have here for communication, that's not a valid reason to break them too.
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it -8 Vote: I do not like it
        Я себя каждый раз сдерживал, чтобы не написать то же самое, что написал Vasya. Как приятно читать его сообщение, надеюсь, что такие будут раздаваться после каждого набора иероглифов.
        → Reply
        • 13 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          Учитывая что человек (якобы) из Китая написал по-японски, он явно имел в виду что-то столь же чуждое ему, как и нам... ;-)
          → Reply
        • 13 years ago, # ^ |
            Vote: I like it +21 Vote: I do not like it
          This is English thread, so please do not break the rules you are insisting to enforce so vigourously
          → Reply
    • 13 years ago, # ^ |
        Vote: I like it +18 Vote: I do not like it
      By the way, he just said "Happy birthday".
      → Reply
    • 13 years ago, # ^ |
        Vote: I like it +16 Vote: I do not like it
      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.
      → Reply
  • 13 years ago, # ^ |
      Vote: I like it -37 Vote: I do not like it
    молю бога, чтобы в будущем не было японских или китайских веток.
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it +63 Vote: I do not like it
      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
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it
        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...
        → Reply
13 years ago, # |
  Vote: I like it +40 Vote: I do not like it
Loved the contest :)
→ Reply
13 years ago, # |
  Vote: I like it +4 Vote: I do not like it
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 :)
→ Reply
13 years ago, # |
  Vote: I like it +11 Vote: I do not like it
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?

→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    That is actually written in the blog post itself :D
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      I think he meant the author of problem C.
      → Reply
13 years ago, # |
  Vote: I like it +5 Vote: I do not like it
Nice set of Problems... !!

→ Reply
13 years ago, # |
  Vote: I like it +1 Vote: I do not like it
What's wrong with sys.tests in DIV2?
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I see, only xiaowuc1 problem testing, but for a long time. Why?
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      I've noticed, his solution doesn't have "return 0" in the end. Maybe, the root of the problem are there?
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it -12 Vote: I do not like it
        Java is such a Java. I mean that CF is written in Java.
        → Reply
        • 13 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          Do you think that compilers and scripts used for testing solutions are written in Java?
          → Reply
          • 13 years ago, # ^ |
              Vote: I like it -11 Vote: I do not like it
            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.
            → Reply
13 years ago, # |
  Vote: I like it +16 Vote: I do not like it
Today it's my birthday too (seriously)
→ Reply
13 years ago, # |
  Vote: I like it +25 Vote: I do not like it
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.
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Absolutely agree. The current formula make less stable Div 1
    → Reply
  • 13 years ago, # ^ |
      Vote: I like it +17 Vote: I do not like it
    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! :)
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it +11 Vote: I do not like it
      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.

      → Reply
    • 13 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it


      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.
      → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Yes ,I agree .It would be great idea...
    → Reply
13 years ago, # |
  Vote: I like it +1 Vote: I do not like it
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 ?
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it
    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.
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it
      Thanks. This was too simple and elegant. :)
      → Reply
  • 13 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it
    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 left
    3. check that the resulting graph is a circular, i.e. there are at least 3 nodes and each has degree 2
    → Reply
  • 13 years ago, # ^ |
    ← Rev. 3   Vote: I like it +1 Vote: I do not like it

    if n=m and the graph is connectd return FHTAGN(you can use union-find set)
    else return NO

    → Reply
  • 13 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
    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 :)
    → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    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.
    → Reply
13 years ago, # |
  Vote: I like it +2 Vote: I do not like it
Problemset and statements of last 2 contests have been pretty good,thanks to problem-setters.
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Can somebody explain Div2 Problem. D and Problem. E ??
Thx a lot!
→ Reply
  • 13 years ago, # ^ |
    ← Rev. 2   Vote: I like it -10 Vote: I do not like it

    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.
    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
In Problem D. I don't even understand sample data
5 2 5
1
2
3
4
5
why is it ...XX
this configuration Sasha will have 3/5 probability to lose while .X.X.
being 3/5 to win. why is ...XX the answer?
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    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
    → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    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.
    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
it seems that there are something wrong with Judgement. It cannot judge.
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Are there any data sets in DIV I E like this?
2
2 1 2
2 1 2
-2 -3

Are there any pairs of sets exactly the same?
→ Reply
13 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I am from China.Happy birthday,connector.

生日快乐！

→ Reply
13 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

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

→ Reply
13 years ago, # |
← Rev. 4   Vote: I like it +4 Vote: I do not like it

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

→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    +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...
    → Reply
13 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

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 "New Courier" is better.

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