Блог пользователя seland

Автор seland, 10 лет назад, По-русски

Всем привет!

Рад сообщить, что скоро состоится Codeforces Round #303 для участников Div.2, автором которого являюсь я. Как всегда, участники Div.1 могут поучаствовать вне конкурса.

Это мой первый раунд, и я надеюсь, что он будет для Вас интересным.

Раунд не состоялся бы без помощи команды Codeforces! Спасибо Zlobober за помощь в подготовке раунда и Delinur за перевод. Отдельное спасибо всем, кто вложил силы в создание и поддержку систем Codeforces и Polygon.

Распределение баллов будет объявлено позже.

Удачи и вдохновения!

UPD Распределение баллов по задачам — 500-1000-1750-1750-2500.

UPD Поздравляем победителей в официальном зачёте:

  1. Bell-sama
  2. anko
  3. BobDylan
  4. Gusheng
  5. Diguised
  6. imyyimdog

И в неофициальном зачёте:

  1. ngfam_kongu
  2. Laakeri
  3. Um_nik
  4. KrK

UPD Ссылка на разбор.

  • Проголосовать: нравится
  • +174
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится -19 Проголосовать: не нравится

Hope the English version won't be from Google translator!!

  • »
    »
    10 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    Come on people,why downvote? I made some prediction here and as you can see the 1st problem really had some sign of google translation: "Little Susie, thanks to her older brother, likes to play with cars." Didn't my prediction work?

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится -12 Проголосовать: не нравится

      People just like to downvote comparatively low rated programmers comments whatever they write.Racist everywhere.

»
10 лет назад, # |
  Проголосовать: нравится +53 Проголосовать: не нравится

World Final for div 2 :)

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится +25 Проголосовать: не нравится

Maybe not so many genius unrated contestants, because most of them are in relaxation mode for tomorrow Div. 1 World Final ;)

»
10 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

  • »
    »
    10 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +16 Проголосовать: не нравится

    Many strong coders won't take part due to world finals . All of the strong coders are in div1 . That's why there are many div1 contests consecutively lined up after the WF ends.

»
10 лет назад, # |
  Проголосовать: нравится +42 Проголосовать: не нравится

When tourist said his team did not feel any pressure for the world finals i thought OK.. But then querty787788 went ahead and registered for this contest as if he has nothing to do tomorrow. Let's see if he actually participates.

»
10 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

I wonder why all the contest at the same time of the day ! It's not suitable and not reasonable at all .. can anyone explain this ?

»
10 лет назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

Score distribution will be announce later :) When??? JUST 10 min. befor contest and no announce :/

»
10 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

Just 5100 participants?? too few! :D

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

who was translating statements??? i hate him with passion.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +69 Проголосовать: не нравится

    Telling what exactly you think is wrong in a translation is a more constructive way rather than just saying you hate someone.

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I thought the translations were totally fine with a few minor mistakes that didn't really matter in understanding the problems.

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      ye sorry for nonconstructive criticism, but some of the problem's statements weren't translated fully, compared to russian statement (example: E's english statement didn't contain that graph is connecte initially, while russian statement did)

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Мне кажется или контест выдался легким :)

»
10 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

The worst Contest EVER!

A,B,C,D,E were all obvious! -_-

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In problem E, using std::set(to implement Prims) gives TLE ?

»
10 лет назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится

Problem C was really hard for third problem(C).

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In E, how to prove that shortest path tree we get using dijkstra is indeed the shortest path tree with least weight ?

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    This solution may be hacked by following test case:

    3 3 1 2 8 1 3 6 2 3 2 1

    Simply doing djikstra — it will output 14; correct answer is 8.

    • »
      »
      »
      10 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Even using dijkstra, we get 8. Ofcourse, the modification if ( dist[X] <= dist[current]+weight of edge )then parent[X]=current is to be made.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Is that always true anyway? At least my implementation of Dijkstra does not have that property, and I spent forever trying to figure out how to modify it to get that property.

  • »
    »
    10 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится
    its wrong, so you cannot prove it :D
    UPD: I wasn't fast enough
    
    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      so, what's the correct solution for E?

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Use Dijkstra and modify (d[v] == d[u] + w);

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится
        i used this method.
        consider the spanning-tree (shortest path ST) with minimum weights.
        delete a leaf from it then it can be prove that the remaining spanning tree is still with minimum weight.
        so remove all nodes then add them one by one, in which you add you shout set it parent the node with minimum edge weight.
        
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    it isnt because i used dijkstra and i got WA. i think you should modify dijkstra so when (d[v] == d[u] + w) happens, you change d[v] to d[u]+w if the trees wieght decreases.

  • »
    »
    10 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

    Let d[x] denote the minimum distance from u to x. Let's construct a tree in G using this approach: 1. Let u be the root. 2. For all other vertex p, we can choose as a parent any node q such that d[p]=d[q]+w[q][p]. The most natural idea is to select the q with minimum w[q][p].

    Since for each vertex we are selecting the edge with minimum weight, the total sum of weights will be minimum. It just remains to prove that for two different vertices, we can't choose the same edge as a link to the parent node (this is a consequence of positive weights)

»
10 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Question similar to E was asked in ICPC regionals this year. Here is the link.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Actually solution algo was directly google-able too :P one can get ready-made algo for E in 2 clicks :/

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Problem C was really hard for third problem(C).

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    It's obvious I think :) But D is easier than C.

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      i think C is the obvious one cuz its a simple DP.

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        i think you can solve it by using greedy approach also.

        • »
          »
          »
          »
          »
          10 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          i would love to hear how.

          • »
            »
            »
            »
            »
            »
            10 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Starting from left, If you can fell a tree left, make it go left else if you can fell it on right make it go right.

            Why this works ? If you are falling left then it is easy to see that you are not spoiling the chance of the next tree. The option for next tree is open.

            If you are falling the tree to right, may be there is a possibility that the right tree can't fall left. Only thing is worst case scenario you have to select only one of this tree.

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится +28 Проголосовать: не нравится

        It was greedy. All problems were greedy :)

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      D easier than A

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Hard ?? why ?? it was a simple implementation .

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится -48 Проголосовать: не нравится

During coding phase,Earthquake at NEPAL-INDIA border ruined everything!! :( :(

»
10 лет назад, # |
  Проголосовать: нравится +93 Проголосовать: не нравится

unexpectedly easy problem set. appears as if we are participating in a DIV 3 contest

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    if the difficulty level was "standard" ANY of problems A,B,C,D could be Div2. A or at most Div2. B.Because no specific algos were needed,and problem C had some tricky coroners and wasn't actually difficult

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Thanks for nice contest for Div.2. There were interesting problems. Maybe pretests could be a bit weaker.

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why am I still unrated after this contest? (It is my first btw)

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What was the 7th pretest for C :(..Kept getting WA

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    It was DP. You should initialize 0th tree at -infinity(-10^14) and n+1th tree at infinity.

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Well, that's obvious. But what about other trees, could you please explain to me? I couldn't code a working solution.

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I did C in a greedy manner: keep 3 arrays(one for trees position, one for trees height and one for where will the rightmost part of the i-th tree be). I initialised the rightmost part of the first element as the position of the first tree and the (n+1)-th with INFINITY. Then for each tree starting from the second to the last i check first if i can make it fell to left(using the rightmost array), if i cant i check if it can fell to right and it is still impossible i move to the next tree without increasing the amount of trees that can be cut.

      PS sorry for bad formating.

      Here is my source code: CODE

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Actually it could be solved in a greedy way without any extra space.

      The first tree is toppled to the left and the last to the right.

      Keep a variable "lastUsed" initially equal to the position of the first tree.

      For trees [2, n-1] try to topple it to the left. If not possible try toppling it to the right and update to x[i] + h[i]. If it couldn't be toppled or it was toppled to the left "lastUsed" gets updated to x[i].

      My code

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

Hmmmm.... either I drunk too little coffee or I have to participate in Div3 contests....

»
10 лет назад, # |
  Проголосовать: нравится +31 Проголосовать: не нравится

It was a GREEDY contest!! :D

»
10 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

A car is good if it turned over in no collision --> RIP English

»
10 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

This was easier than Codechef Lunch time contest, which is supposedly designed for school students.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    Have you actually participated in those, because I certainly feel that overall level of lunchtimes is at par with Div2 contests(old ones when I used to participate :)) and most of the times even difficult than that.

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Yes, I have and I believe that last two problems of Div2 contests are harder than last 2 problems of lunchtime. The level of first three problems are more or less the same. But today first 4 problems were very easy and 5th was direct implementation.

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится +6 Проголосовать: не нравится

        I don't think you can judge the difficulty of problems which you can't solve in contest time. Just because the solution uses a familiar concept or uses less code doesn't necessarily mean it's simple. Have you solved Div2 E or the last problem from Lunch Time contest?

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +14 Проголосовать: не нравится

    IOI is also for school students. Do you think it's easy?

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Codeforces favors C++ over Java too much. I cant make E accepted with Java, got TE all of the time. The algorithm I implemented is exactly same with accepted C++ version.

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Only 3 "Failed System Test" solutions in my room. wow... XD

»
10 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Can anybody explain this?

Task D. Sort and calculate got AC. But in query 1 1 1 1 1 1 1 5 two satisfied. But in query 1 1 5 1 1 1 1 1 1 three satisfied. Where am I wrong?

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Because we sort the array first, so both of them will produce 1 1 1 1 1 1 1 5. The answer should be three: serve the first two, and serve the last person.

    Hope it helps!

»
10 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

what an awful contest ?! Everything depends on problem E!

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What did solve task C? I am build dinamic and found states with binary finder... Why it was not correct: http://pastebin.com/PHVYYqWC ?

»
10 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

The pretest was so strong i got two times WA in problem C&D and at last AC.I scanned the whole c++ coders of my room and there was no sign of mistakes in their codes :D

»
10 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

My room 1016, NO successful hacking, NO system test fail. :|

»
10 лет назад, # |
  Проголосовать: нравится -23 Проголосовать: не нравится

rasoolll and Behnam.B cheated look at their submissions : 11152882 and 11153982 they are also from same university (shame on ferdowsi university of mashhad)

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +28 Проголосовать: не нравится

    Code doesn't look 100% similar. Their outputs on the third test differ also.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    This is Common Problem With Short code. Two code can Have similar Idea ( Even These Code seems to be same but not Exactly Same). And another thing is, Generally Student from same University have closer Idea about many problems.

»
10 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

I am new to this site, and this was my first ever coding contest. I managed to solve 3 problems getting a rank of 1802. However, I cannot see any rating being alloted to me. Can anyone explain the reason for this, and how I can earn a rating.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    System testing wasn't finished. It is finished now. Your rating's 1448, gratz on your first contest!

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      Thanks, I also wanted to know that few people were awarded more marks for certain questions, and I lost out on few points. For example Problem #1 was of 500 points, where as I was awarded only 408 points, even though I didn't fail any submission. I read somewhere about hacking other people's code and some room concept. Can someone explain me my roles about hacking and what am I supposed to do in a room.

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится +4 Проголосовать: не нравится

        you get less points if you take more time to solve. If you are sure of your solution you can press the lock button on the dashboard. Then you can view others' solutions to that problem by clicking the score in the room. If you find a mistake in their code, give a test case which satisfies constraints and gives sub optimal answer wwith their code. You get +50 if their code gives wrong answer and -50 otherwise. Also, if you click the lock, you cant resubmit for that problem.

»
10 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Finally into DIV 1 (purple) after almost a year on CF :D

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Answers to both of my wrong submissions (WA on pretest one in Problem A and Runtime Error in Problem D) is showing correctly on my computer. anything i am missing here?

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    When a[i][j] == 3 || a[i][j] == 1 you should skip entry. i cant understand your code seems like you do the same for a[i][j] == 2 and it give WA.

»
10 лет назад, # |
  Проголосовать: нравится +42 Проголосовать: не нравится

In my opinion, problemset was like A-B-B-B-D, but it's just my opinion.

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone tell me why this solution gave WA for test 11 question C? I used DP where prev=0 means previous tree wasn't cut, prev=1 means previous tree was cut to left, prev =2 means previous tree was cut to rightLINK

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    its simple because you assume tree number 2 will always be cut in code: int ans=1+func(2,1); ans=max(ans,1+func(2,2));

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      No, I am assuming that tree 1 will always be cut to the left (this is optimal, I know). ans=max(ans,1+func(2,2)) means tree 1 is cut to right. func(i,prev) means I am checking for tree i and I have solved for i-1 trees and (i-1)th tree was cut to prev.

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I tried to solve the problem E using Dijkstra modified. It is my aproach:

  • Save the parents of each node using dijkstra
  • create a toposort for the directed graph of parents
  • for each node select the parent with the minimum weight.

I get WA in the 8th case. The test case is very large and I cant debug it...

Here is my code.

I read several comments and found some similar ideas. can anyone help me? (sorry for my poor english) thanks in advance

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Too few successful hacks for A, B, C, D. Problems were so clear and obvious. Also, since I passed too many pretests, I was sure about getting accepted for first four problems!

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

:D

»
10 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

A very nice contest with both easy and medium level questions.

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone plz explain why problem E is not minimum spanning tree? I thought it as MST but I know second test case is not following my observation. So plz elaborate why my assumption is wrong.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    The MST does not satisfy the condition: "shortest-path tree from vertex u" ... " the lengths of the shortest paths from u to any vertex to G and to G1 are the same".

    Make some test cases yourself and you'll realize it. (Sorry for my bad english)

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    You have to find a tree such that each vertex has least-possible distance from an specified vertex of the graph, not just being connected to the tree with least-cost.

»
10 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Since this round was the author's first contest as a writer, I think there should have been a reviewer working with him. The problems were okay, but the complexities didn't match the score. Even though most of the problems were easy, I spent relatively too much time trying to solve them because the translation was not clear enough.

»
10 лет назад, # |
Rev. 3   Проголосовать: нравится +14 Проголосовать: не нравится
»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

My E solution failed because of long long. I legit feel sad now.

11160086: initial submission
11171670: correct submission

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

this round very easy ! =D

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Вам дан связный взвешенный неориентированный граф G и вершина u. Необходимо найти дерево кратчайших путей заданого графа из вершины u, суммарный вес рёбер которого минимален.

Это было архисложно, но я решил Div2E (Div1C), дайте мне красного :)))

»
10 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

has anyone did problem E with MST(kruskal's or prim's )?if yes then please explain the approach?

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

This was my first CF round so I can't compare it with others, but I'd like to give the author some feedback: I enjoyed the round :), although it was an one hour contest for me (A, B, C and D). I couldn't finish E as well, although it was a nice problem, also the only difficult one. I think that C deserved more points than D? or D deserved less points than C?

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hi every one in problem C can explain in test #7 why answer is 5? which trees can cut down? I think tree x=1 to right, tree x=41 to left, tree x=55 to left, tree x=59 to right, and last tree with x=105 to right why my answer is wrong?

  • »
    »
    10 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Your answer is almost right , but always cut the first tree to the left not to the right :)

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I forgot tree x=68 so: tree x=1 to left, tree x=41 to left, tree x=55 to left, tree x=59 to right, tree x=68 to left, and last tree with x=105 to right we can cut down 6 tree and correct answer is 5! what's wrong?

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        If you cut down tree x=59 to right, it takes segment [59;66]. If you cut down tree x=68 to left, it takes sement [61;68]. These segments are intersect, so we can't do this.