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

Автор KAN, 9 месяцев назад, По-русски,

Всем добрый день!

Уже завтра в Москве состоится финал Технокубка 2017 — олимпиады для школьников, проводимой Mail.Ru Group совместно с МФТИ, МГТУ им. Н. Э. Баумана и Codeforces. А для тех, кто не будет участвовать в финале, мы подготовили рейтинговую трансляцию финала для обоих дивизионов. Раунд начнется в 16:05 по московскому времени в воскресенье, 5 марта 2017 и продлится два часа.

Обратите внимание, финалистам Технокубка не нужно регистрироваться на этот раунд, он предназначен только для не участвующих в финале.

Над задачами работали Endagorion, WHITE2302, Alladdin, fcspartakm, Amethyst1, MikeMirzayanov, ifsmirnov и я.

В каждом дивизионе будет предложено 6 задач.

Олимпиада Технокубок 2017 завершена. Поздравляем победителей и призеров. Вот героический топ-3 (апплодисменты!):

  1. Александра Дроздова, Нижний Новгород
  2. Артур Петуховский, Витебск
  3. Владимир Романов, Москва

Окончательные результаты доступны по ссылке.

Разбор тут.

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

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

Why isn't this on the home page?

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

Это вещь рейтинговая?

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

I thought that I will die before I participate in a new round

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

Error 403: this page is not available in your country...

Syrian contestants will relate :( :( :(

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

I have developed a habit of viewing if there is a new round every day...

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

Will the descriptions of the problems in English or in Russian? Thanks a lot.

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

Scoring distribution ?

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

Will it be rated or unrated?

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

    Yes, it will. In Russian it is stated clearly.

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

      @Andrekk, Could you please give me the link of the russian statement?

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

        I can't do it. You switch the language via button in the upper right corner of any web page, but URL isn't changed. Basically, in russian it says, ' А для тех, кто не будет участвовать в финале, мы подготовили рейтинговую трансляцию финала для обоих дивизионов' which was translated just like 'For those who will not participate in the Finals, we prepared mirror contests for both divisions'.

»
9 месяцев назад, # |
  Проголосовать: нравится -62 Проголосовать: не нравится

I am so stupid that I can not be like tourist))). More likes,please. LOLKEKCHEBUREK

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

Slept for 2 hours, went for an ACM training, then a CF round... feel awesome!

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

What are the problem scores?

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

scores distribution?

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

Rating prediction for this contest could be found for div1 & div2
Since today results table sortable, just click on column header to sort by it.

Extensions:

About CF-Predictor

Good luck & high rating for everyone!

»
9 месяцев назад, # |
Rev. 4   Проголосовать: нравится +9 Проголосовать: не нравится

Very weak pretests in problem D. LOL :D

OMG!! MY SOLUTION IS CORRECT!! HOW?! EVEN I DIDN'T READ STATEMENTS FULLY!

»
9 месяцев назад, # |
  Проголосовать: нравится -31 Проголосовать: не нравится

»
9 месяцев назад, # |
Rev. 3   Проголосовать: нравится +8 Проголосовать: не нравится

"В Москве олимпиада началась, вы можете увидеть текущие результаты по ссылке."

Уже не работает. Но хотелось видеть видеть ссылку на итоговые результаты. Спасибо

Update. Открыты итоги по старой ссылке

»
9 месяцев назад, # |
Rev. 5   Проголосовать: нравится -50 Проголосовать: не нравится

I am getting WA on pretest 5, for Div2 C. Can anyone help me? My submission: 25264506

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

Can you solve Div2B using binary search? I tried searching for the time or for the meeting point, but I'm getting WA6. Is the approach wrong or I just screwed up floating-point arithmetic?

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

    I had the same problem. After 5 unsuccessful submissions, I put cout.precision(7); at the beginning of the code and it passed the pretests.

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

      Damn, that did it, I got AC. I feel really stupid now, I'm not even sure why this line matters.

      Thanks.

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

        It's because by default cout precision is low. The problem requires precision upto 10^-6. So, suppose answer is 1.000777, cout without precision setting would round it to 1.001, resulting in WA.

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

    Don't we need ternary search?

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

    No. A unimodal function can't be solved with binary search. You need ternary search.

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

      You can binary search on time, it's monotonic.

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

        yeah, it's monotonic on time, unimodal on distance.

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

        I used Ternary search and got AC. It should not be Binary search bcz then we may choose boundary values(min or max).

        Edit: it's possible follow this (binary search on time)

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

          I used ternary search and got TLE.

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

            Ternary search works perfectly fine. Got AC. Check for boundary conditions. Using iterative method works. Compute log2(MAX_NO_OF_ITERATIONS) and do the search that many times.

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

    I used binary search to solve Div2B, try use double instead of float maybe will work.

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

Test case 6 in Div 2 B ?

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

How did you solve Div2 B?

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

    Binary search the answer.

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

    Binary search a suitable x and find t, take the minimum of all iterations.

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

    Binarysearch

    eps = 0.00000001;
    L = 0; R = 100000007;
    
    while( R-L > eps){
      m = (L+R)/2;
    
      if(canmeet(m) R = m;
      else L = m;
    }
    
    res = (L+R)/2;
    
    
    
    
    
    canmeet(long double meettime) {
    
       each person can go to the left to x[i]-v[i]*meettime , and to the right to x[i]+v[i]*meettime
    
       you have to check if the intersection of all segments [ x[i]-v[i]*meettime , x[i]+v[i]*meettime ] is not empty
    
    }
    
    • »
      »
      »
      8 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Is it possible by applying binary search on distance?

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

      i didn't get, can you explain a bit more about canmeet function ,please?

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

        I'll try to explain.

        In some time 't', any person can be present at positions in range (x[i]-t*v[i] to x[i]+t*v[i]).

        All the persons will be present at a common position 'p' iff 'p' lies in all such segments.

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

How to solve B? I think this it can be solved by ternary search, but I couldn't implement.

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

    I passed pretests using ternary search. I'm not sure it is a correct solution, though.

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

    I make it 10.

    Suppose now we are searching (l,r). Denote t=(r-l)/10, we divide (l,r) into 10 smaller sections(l, l+t), (l+t, l+t*2) ......(l+t*9, r), then compute the result of l+t, l+t*2, l+t*3 .....l+t*9. Suppose l+t*k is the minimum, the optimal answer must be in (l+t*(k-1), l+t*(k+1)).(10 sections -->2 sections)

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

After trying to find a flow solution for problem B, my head is now overflowed...

PS: How to build the flow correctly for problem B?

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

    B -- This can be modelled as a maximum bipartite matching, with all teams sharing the first option having all their first options removed. This is a standard algorithm -- See Hopcroft-Karp for an efficient algorithm.

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

      I feel like an idiot after reading your solution. That's a lot simpler than I thought.

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

        It can be modeled as 2SAT also, but both of these are overkill solutions. I saw some people in my room had done some nifty 30 line solutions...

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

          I bet that all these nifty solutions look like flow algorithms. Nson's for example:

          All teams start with the first option (xxx). Until there's no conflict for some team i, make team i's choice the second option (xx+y).

          That's it. This is the solution. And it reminds me very much the idea "find an augmenting path and send flow through it" (Ford-Fulkerson's).

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

      Can you please explain your graph weights? I tried thinking on the flows solution during the contest, but was unable to find an analogy which completely fits the solution.

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

        This is a maximum bipartite matching (not exactly max flow), but the most efficient popular solution (in contest contexts) is Hopcroft-Karp, which is basically a specialised case of Dinic's algorithm for max flow.

        The maximum bipartite matching is as follows: For each team, if it can possibly use its first option (that is, if no other team starts with the same 3 letters), draw an edge to its first option. Then, always draw an edge to the second option. If you can match all vertices on the left to all vertices on the right, then you have found your solution. Otherwise, there is no solution.

        To convert from maximum bipartite matching (say if you have Dinic's bookcode), simply connect the source to all teams with capacity 1, replace all original edges with capacity 1, and add edges from all abbreviations to the sink with capacity 1.

        (Unfortunately I had a sneaky bug and failed main tests, but that's the implementation, not the idea.)

»
9 месяцев назад, # |
Rev. 4   Проголосовать: нравится +102 Проголосовать: не нравится

A-D: Graphs Graphs Graphs Graphs

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

    B is just tedious implementation, I don't see graphs here.

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

      Well I directly throw some flow models (hope no TLE btw), so it's graph for me :(

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

        If you use Dinic's/Hopcroft-Karp, the complexity should be O(N^(3/2)), so unlikely to TLE.

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

        Funny it can be solved this way. I just looked which teams are forced to have second option (in while loop) and if there are no more than I use first option, that's it. Team is forced to use second option if there is another team with same 3letter prefix (all such conflicts are detected on the beginning) and then in loop I detect conflicts of form that I can't use first option because it is taken.

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

      I used 2-SAT to solve so it's also graph for me.

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

    D is matrix multiplication, I don't see graphs here.

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

Bonus points for those who will come up with a test to D so that longest possible path has length from interval (1018, 260). I think such test will cause many solutions to fail, but maybe such test doesn't exist.

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

Почему при обновлении страницы во время раунда выходит из профиля?

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

i've stuck in B for about 2 hours. What a day!

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

i think B is Ternary Search problem ..i am not sure i couldn't implement it !

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

how to solve D div1 faster than ?

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

    Using bitset.

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

    I was thinking O(N^3 * log (10^18) / 64), where 64 comes from using OR operator to do something like union of sets. But I didn't have time to code it. Besides, I'm curious to know whether there is something faster than O(N^3 * log (1e18)) too.

    Edit: seems like I was beaten to the response.

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

Any ideas for Div2C?

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

    maximum vertex degree + 1

    • »
      »
      »
      9 месяцев назад, # ^ |
      Rev. 3   Проголосовать: нравится -8 Проголосовать: не нравится

      But what about this test?

      5

      1 - 2

      1 - 3

      2 - 4

      2 - 5.

      your answer is 3 but the main answer is 4!

      P.S. oh. sorry! it was my mistake... the solution is correct.

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

        the degs are 2 3 1 1 1 so answer is 3 + 1 = 4

      • »
        »
        »
        »
        9 месяцев назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
        degree(node_2) + 1 = 4
        
      • »
        »
        »
        »
        9 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Why is my answer 3? Highest degree = 3. Add 1, you get 4

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

        first visit current node,then go to current node's child node.For each current node's children,first ensure that it is undiscovered .And then put down perfect color number for this children,start from color number 1,compare each time with children's parent & grandparent,if match,color number increases,is mismatch assign this color number for this children,And mark this node as a discovered node,And goes down from this children :) For total number of color counting,count any noode's total child,then increase it by 1,because node itself is also to be colored :)

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

    It was just a simple one-pass dfs. For each node, you assign it all values to its children which are not equal to itself and its parent.

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

Will greedy work for div 2 D?

I pushed every second option in a vector for the corresponding first option, in a map. For this situation, if answer exists, the answer must be the second option, if size of vector > 1. If size of vector is 1, then we can use the first option for each of these clubs, given this doesn't already appear in our answer.

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

    Of course it work, but when you check if there is at least 1 vector with size 1 we have to use the second option, we have to continue searching until all vector of size 1 can use first option

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

      Yeah. My implementation took n^2. I am scared of looking at my submissions page, as I didn't do very well.

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

That was fast.

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

Thats the fastest system test ever :p

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

How to solve Div1 C?

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

    Put in an array the nodes following the visiting order of a dfs on the graph. Then, for each contiguous block of ceil(2n / k) nodes in the array, assign a robot. If a robot gets no node, just assign any node to it. This works because the dfs spanning tree has exactly n - 1 edges and you visit each of them 2 times (going down and up); hence, 2(n - 1) + 1 nodes will be visited.

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

    consider a dfs tree

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

This is not completely related to the contest itself, but when I go to my room I see a bug in the page title.

It says Room #0 instead of Room #21.

»
9 месяцев назад, # |
Rev. 3   Проголосовать: нравится +97 Проголосовать: не нравится

The test data of Div 1 D is weak.

This solution, which consider starting at any city, passed system test. 25265977

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

    If you don't post this comment, I won't know the starting position is fixed forever though I pass it...

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

      So we're waiting for rejudge? Actually, it's weird. So many people were anxious to challenge. For example, test 2 2 2 2 0 2 2 1 should give the answer 0.

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

        Last time there wasn't a rejudge when a Div 2 D (some rounds ago) have quite weak tests though.

        P.S. I think my solution does consider starting only at vertex 1 though.

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

    System tests are becoming weaker recently, especially in Div 1.

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

    Bad job problemsetters :(

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

    Omg, I can't believe people are creating anti-unordered_map tests when hacking, but nobody create tests against such thing and people get away with it xd.

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

PRO AF Bug Rant

Contest Submission [TLE] : 25255834
After Contest [AC] : 25265826

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

When I tried to view the onsite results, I got an error says "You do not have view access to non-public contest".

Edit: It's available to me now.

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

I tried Div1C with Minimum Spanning Tree and Backtracking. in this solution, searched node of backtracking in MST is no more than 2n-2 then i stored searched node and divided k-set.

...but i got WA. Why?!! T.T

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

    I had exact same problem, can somebody explain what getting WA4 means in terms of solution incorrectness?

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

      Well the answer is somehow I chose a convoluted and wrong order in the DFS to add the vertices. One simply adds the current vertex, and then after every call of dfs adds the current vertex again. Two line change :(

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

        Thank you guys :) was supper easy I don't know how I didn't figure out the answer faster

»
9 месяцев назад, # |
Rev. 3   Проголосовать: нравится -18 Проголосовать: не нравится

Pro AF Bug xD

Contest Submission [TLE in Systest] : 25255834 (How did this shit even pass pretests?)
After Contest [AC] : 25265826

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

    Your codes are not same and have diffs here :

    if ((int) colors.size() == neighbours) { break; } "==" instead of ">=" that when there will be a huge vertices with degree of 1 and ans be huge do You will get TLE.

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

      I know that. I was pointing to the subtlety of the bug, and was surprised as to how it passed the first 47 tests.

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

Problem B — Spend 1 hours and a half, can't come up with a solution

Problem C — Took me 1 minute to come up with a solution.

Moral of today's contest: read all problems' statement first.

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

    Exact same situation :(

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

    Exactly different situation :(

    By Technocup onsite results I took C first

    Problem C — Spend 1 hours and a half, can't come up with a solution

    Problem B — Took me 1 minute to come up with a solution.(Because Binary/Ternary Search is my favorite topic)

    Moral of today's contest: read all problem's statement in first come first solve manner.

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

I got wrong answer on case 16 DIV2 D . Can't find the error . Please help !! http://codeforces.com/contest/782/submission/25264212

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

    me too and it is really making me angry -_-

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

      test case : 3 ABA REF ABD AFG ABD OOO My solution : NO actual solution : YES ABR ABA ABO The error was that all the one length vectors(vector of all strings with same shortname1) need to be checked at the last , since only those vectors has 2 possible options.
»
9 месяцев назад, # |
Rev. 2   Проголосовать: нравится -13 Проголосовать: не нравится
»
9 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

can someone give me a simple implementation for B .. i couldn't implement it well ?

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

    I understood solution from my friends code, maybe it can help you.

    My friends code
  • »
    »
    8 месяцев назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    here is my solution 25259459

    I use ternary search for finding a meeting place

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

      I used Binary Search on meeting place and keep getting WA at test 24? Could it be Binary Search cannot be used for meeting place?

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

        Meeting place will not always be an integer. So yes, you cannot use Binary Search for the meeting place.

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

        Yes, if you take the limits l = minimum x, r = maximum x you can imagine f(position) begin max(left(position), right(position)). left is the maximum time to get here from the positions to the left and right is from the right. This function is the maximum of an increasing funtion(left) and a decreasing function(right), so it is not always monotonic.

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

        Check your answer when all the persons are at the same point. I also applied binary search on the distances. Since my upper limit and lower limit were equal from the beginning, my code was failing on test 24.

        Added an if statement to get AC after the contest.

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

    I did this: Binary search on the answer.

    For each value t, you can examine if all of the friends can meet somewhere within t seconds.

    First, examine what is the minimum xi, such that xi = posi + speedi * t. Then, min(xi) is the best place to meet if we have t seconds of time. Try to examine if everyone positioned after min(xi) can reach min(xi) after t seconds. If yes, it is possible to meet within t seconds; it is not otherwise.

»
8 месяцев назад, # |
Rev. 3   Проголосовать: нравится +20 Проголосовать: не нравится

Why we can't see successful submissions?

UPD: Seems it is fixed

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

Why can't we see the tests ?

»
8 месяцев назад, # |
Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

Why can't I see other people submissions? All, not just ones from today's competition.

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

Когда окончательные результаты будут?

»
8 месяцев назад, # |
  Проголосовать: нравится -18 Проголосовать: не нравится
»
8 месяцев назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

I believe we have waited enough for the ratings to be updated :D

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

what's the solution for Div2D?

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

    Stupid greedy implementation. Try to name the team using the first choice. If you can't, try to name the team using the second choice and rename those that conflict with the new name. If you can't rename those, it means that it is impossible.

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

      implemented by choosing second choice first. WA on 6th pretest :(

  • »
    »
    8 месяцев назад, # ^ |
    Rev. 6   Проголосовать: нравится +11 Проголосовать: не нравится

    Maintain a DSU and place all the teams having same team name [first three characters] in a same component and also maintain the size of each component. Now, if there are two teams u , v (u != v) such that both the teams belong to the same component and the short names formed by using second option for both u and v are equal, then the answer is NO. Now, name all the teams in a component having size > 1 by using second option. Teams having only 1 node in its component has two options, either use first option or second, if both the strings are already used then again the answer is NO, else use either of them which isn't used yet.

    PS- This solution is wrong, test data were weak enough to let this solution pass.

    Test where it can fail :

    ABC DDD

    ABD DOG

    Maximum Bipartite Matching shall be used to assign the shortnames to the teams having only 1 node in its component.

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

      My solution seems correct (it passed). The algorithm is :-

      1. First put type 1 name for all.
      2. If a name has multiple copies, take type 2 name for all in the conflicting name.
      3. If some conflict still exists, change type 1 to type 2 in that conflict. If multiple type 2's in a name, answer doesn't exist.
      4. Repeat 3 till no change made.
      5. Check if every name is unique.

      My actual implementation was O(N^2*log(N)), since I used sets, however with hashing, this will be O(N^2).

      This is so because in step 3, atleast one name is pushed to type 2 for every iteration. Giving maximum N iterations => O(N*(complexity of one iteration)).

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

To administrators and problem designers: I am an OIer from China. (Never asking me why I chose Iceland) Every time I and my friends participated in the round, questions which are written in English worried us greatly. This takes us too much time to understand the meanings . As to myself , in this round , I could have worked C out within 5 more seconds . It takes me too much time to understand B and I could have save the time to work C. So , I request you can prepare questions which are written in Chinese in any form ( a file to download or any else ). Maybe this is not that easy to work , or maybe you haven't the translater , or maybe other countries' participants need questions in their language costs you too much time . It doesn't matter . We wish the problem description can be more clear , terse and easy to understand . This will help us greatly . If you can take my suggestion , I will be deeply grateful.

Yours sincerely Real_EnderDragon

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

    There are so many interesting things about competitive programming in chinese websites I wish I could be able to translate at least to english... And english is not even my natural language :(

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

Can some please help me to find bug in my solution for problem B , why i am getting WA in on test 8 . solution Link

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

ignore

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

I've tried 2-sat in div2-D but got WA. Is enough to test these four cases?

Let option 1 = true, option 2 = false, 'a' and 'b' a team

case 1: first (a) == first (b) -> (¬a || ¬a) && (¬b || ¬b) — both second option

case 2: second (a) == second (b) -> (a || b) && (¬a || ¬b) — a and b must be different

case 3: first (a) == second (b) -> (¬a || b)

case 4: second (a) == first (b) -> (a || ¬b)

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

waiting and waiting for rate change ...

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

Is the ceiling function notation used in the statement of div1.C considered to be general knowledge? I've never seen it before and got a WA on system tests because I thought it was an integer function.

It would be nice if the statement always contained definitions of all nontrivial functions used in it (IIRC, they even provide a definition of bitwise operations in TopCoder SRMs. I don't think it hurts anyone).

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

    I think it's quite common. I've seen it at least in Introduction to Algorithms by Cormen and others and also in Concrete Mathematics by Knuth and others.

    But agree, that statements should contain definitions. Or maybe we can have some extra page Notation on codeforces like some of the books have, that will cover common cases.

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

F looks moderately interesting, and there has been no discussion on it, so maybe I'll start with an idea.

We binary search on the answer D. Hence, we only need concern ourselves with whether it is possible to achieve synchronization with distance D.

Consider the distance between buses 1 and 2 as they around the circuit. Consider a time segment through which neither bus turns a corner. Then the distance function over this segment only has at most 1 turning point, and so will pass D at most twice.

In fact, we know if there is a turning point in this segment: the only difficult case is when the buses are travelling perpendicular to each other, in which case, pretending that the line segments extend infinitely into the past and future, the turning point is precisely the point where the buses are equidistant from the intersection of their lines, with one bus moving towards and one bus away from the intersection. This is the only possible turning point of the function.

Hence, with some effort, we can find the points where f(x) = D, and hence the intervals where f(x)>D. (I'm fuzzy on this front, but binary division seems like it'll run in time.)

Assume we can compute the intervals on which the distance between the 2 buses exceeds D. Then, we can take the union of all these intervals modulo the distance between the 2 buses, ie. treat the time as cyclic with period of (length of route/number of buses). If the entire interval is covered, then D (or at least, D-1e-7) cannot be achieved. Otherwise, D can be achieved, and we can proceed with the binary search.

Checking of unions of interval over a line segment can be done using a set, for example.

Any errors/simplifications?

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

    That's more-or-less what I was implementing, but couldn't find the bugs in time. For each interval where the two buses are moving in a straight line, the vector between them varies linearly, and asking for the two times at which the distance exactly equals D requires solving a quadratic equation. If the determinant is negative then they are never within D of each other, otherwise you get an interval, which then also needs to be clipped to the time interval you're considering.

    I took intersections of intervals when the distance is at most D rather than unions of the complement, but it's equivalent. It also simplifies things to insert breaks at every multiple of the inter-bus separation (i.e. treat those times as if bus 1 made a turn), so that the intervals you get never wrap around.

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

Добавил break в одно место и решение по D div1 зашло... Может кто-нибудь сможет мне объяснить почему.

Максимальная длина L вершины i — это наличие у вершины i пути длиной 2^L, но не пути длиной 2^(L+1).

Первая версия решения — восстановление ответа: для всех вершин, которые находятся на максимальной длине от текущей, запускаю рекурсию, которая ищет для них ответ. Вердикт: TL.

Вторая версия решения — восстановление ответа: для всех вершин, которые находятся на максимальной длине от текущей и обладают максимальной длиной между собой, запускаю рекурсию, которая ищет для них ответ. То есть теперь запускаю рекурсию не от всех вершин, а только от тех, у которых длина максимальна. Вердикт: TL.

Третья версия решения — восстановление ответа: выбираю одну единственную вершину, которая находится на максимальной длине от текущей и обладает максимальной длиной, и иду в неё, игнорирую все остальные вершины, которые обладают такими же параметрами. Ожидаемый вердикт: WA. Вердикт: Полное решение.

Вторая версия решения

Третья версия решения

Разница между решениями лишь в том, что в третьем есть break и, для пущего эффекта, random_shuffle.

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

Div2 B using while(r-l) > 1e-7 failed system test (time limit) http://codeforces.com/contest/782/submission/25253014

using while(r-l) > 1e-6 after the contest accepted http://codeforces.com/contest/782/submission/25265567

life is so cruel

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

    I used 1e-9 in my submission, 100ms. Life is so kind to me then!

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

      i think because you used binary search, you always divide by 2 so you will not face numbers like 0.3333(with infinite threes), but i used ternary search (has dividing by three) which will face this kind of numbers, so it will be truncated then due to the double precision and a high probability that r and l will reach a point that they will not change after it in the loop (so infinite loop occurs)

      this gives me a lesson in the future to include additional check to check that if the calculated numbers (boundaries) in the loop didn't change from the last iteration then break from the loop.

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

        I also had an infinite loop in ternary search, but my lesson is a bit different. Instead of checking absolute error, I'll just do a loop with a fixed number of iterations:

        for (int i = 0; i < 200; i++)
          ...
        
»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Когда вк потестится? раунд 403 давно прошел и результаты известны...

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

Я заметил, что в результатах по ссылке http://codeforces.com/spectator/contest/780/standings у меня стоит 18 место, а в профиле в истории соревнований — 19 место. И такое несовпадение видимо есть у многих участников, например:maxim.shuklin — 165 место реально, в истории соревнований — 181. Соотвественно это влияет на рейтинг, участвовавших официально. Так и должно быть?

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

    Рейтинг для участников технокубка пересчитывался с учетом неофициальных участников.

»
8 месяцев назад, # |
  Проголосовать: нравится -26 Проголосовать: не нравится

Дроздова лучшая, хех

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

I think Dataset for Div2 D is weak. Say for this case

2
ABC DDD
ABD DOG

This submission outputs NO

And The Winner's submission outputs YES.

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

Hi guys, can you explain me, why this Solution has TLE? Sol when I did another using Boolean tab it has compiled program in 140ms, is this really that big difference?

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

    Of course it does. :)

    Your algorithm implemented with a list is O(N^2) for n = 10^5, this will definitely give a time limit.

    The other one is O(N) which passes. If that confuses you read about big oh notation, and then see for what input size you can do each one.

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

Div2 D has a very weak test cases

some ACC soultion output YES and some output NO in this case

3

AAA BBB

AAA CCC

AAD BBB

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

I used ternary search finding derivative tending to zero to solve Div2B 25253744

As F(position)=time has only one local min, then it is the global one so the only point with derivative=0 is the solution (and both left and right parts of the graph are infinite descending and ascending)

Thank you calculus :)

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

Someone with WA16 on Div2D/ Div1B? 25271010

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

How can I implement Div2 B using binary search ?

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

    Let the function f(x) return the time to gather to the point x. The domain is [a,b]. a is the leftmost coordinate and b the rightmost one. It turns out that f is first decreasing and then increasing after some X. The task is to find X, at which f attains its minimun.

    Take the middle point of the current interval.

    Compute f(mid-eps), f(mid), f(mid+eps). Take eps a very small positive number like 0.0000001.

    If f(mid-eps) < f(mid) < f(mid+eps), then the answer is in [a,mid].

    If f(mid-eps) > f(mid) > f(mid+eps), then the answer is in [mid,b].

    Else the answer is mid itself.

    Just simply implement with a while loop.

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

      I have done exactly that 25253744. Only that I called that difference derivative and my goal was to find when derivative was 0.

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

      Good explanation. I managed to get AC based on this. I have some complementary questions though.

      1. When you solved this problem on the contest, did you find exact proof for the fact that "f is first decreasing and then increasing after some X"? Or just viewed some example data and presumed that this will hold for all input?

      2. How to choose proper epsilon? If I choose too big than relative error will be big also. If I choose too small than maybe I can't get differences in the value of the function. Is it possible to bound the relative error in the value of the function based on epsilon. Is there any exact proof?

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

        I just found it intuitive that while you are getting far from the optimal point the time is only increasing. I don't have any idea about the rigorous proof. Regarding the epsilon I usually take it a bit smaller than the relative error.

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

        I think in those cases fixed number of iterations is more predictable, more safe, and more practical. Fix on a number of iterations enough big to avoid precision problems, and enough small to avoid TL. usually around 100 satisfies both with margin

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

    My approach is a little bit different from the other one.

    Do binary search for the point in the interval. For a given point, there will be a friend from the north who reaches the point last of all friends from the north, and similarly a friend from the south. If these two are equally slow, you found the answer. Else move towards the slower one.

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

    Binary search (on doubles) for the minimum time t it takes for all the people to meet.

    For a given time t, note that the set of places person i can reach within time t is the range [pos[i] - v[it, pos[i] + v[it] on the number line. It is possible for all of the people to meet in a given time t if there exists a point inside all the ranges, or if the intersection of all these ranges is not degenerate. To check if the intersection of all these ranges is not degenerate, we can let l be the maximum of the left endpoints of these ranges and r be the minimum of the right endpoints of these ranges. If l ≤ r, it means the intersection of the ranges is not degenerate, while if l > r, the intersection of the ranges is degenerate.

    Code: http://codeforces.com/contest/782/submission/25277237

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

How to solve Div1E?

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

    If you can find quickly, given where each ball starts its fall, which platform it lands on, then the rest of the question is easy. There are at most 3e5 such computations to make.

    Consider processing each of the 3e5 queries from left to right (each query asks, for a starting point, where it ends). For each platform i, there is a maximum height h_i for which it will accept. Consider an array storing h_i's. Then, if we have a ball (index i in array) falling from height H, we simply want to find the minimum index greater than i of the array with entry at least H.

    We just need to support queries of the form: i) Point update ii) Point update iii) Range query of maximum in range

    This can be done using a segment tree. Binary searching to find the minimum such index gives O(lg^2 N) every query, but can be sped up to O(lg N) if we build it into the segment tree.

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

У многих из падает F (из финала, не cf тура) на тесте:

2 1
2 1 0

Даже в топе такие есть...

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

How to solve Div2C with BFS? TIA

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

Can I ask something? I was wondering how my rank became 'pupil' ? I wasn't able to solve any problems on div 2 correctly. I was expecting that my rating would be 'newbie'. Why ?

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

I'm wandering if there will be an official tutorial. Or if anybody could tell me that if is the best time complex for Div1.D? Thanks a lot!

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

    I think many solution have that complexity as well. (at least mine is)

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

not rigorous DATA FOR YESTERDAY'S 781B Innokenty and a Football League THAT SOMEONE USE WRONG PROGRAM TO PASS THE TEST. WE MAY INSERT TWO DATAS THAT CAN SOLVE IT INPUT 1 3 ABC GGG ABG GCC ABD EEE OUTPUT 1 YES ABC ABG ABD INPUT 2 3 ABC DDD ABD CCC ABD EEE OUTPUT 2 YES 3 ABD ABC ABE

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

How to solve Div1D/Div2F?

  • »
    »
    8 месяцев назад, # ^ |
    Rev. 9   Проголосовать: нравится +33 Проголосовать: не нравится

    Let me define it:

    f(0,0) = P;

    f(0,1) = B;

    f(1,0) = f(0,0) + f(0,1);

    f(1,0) = f(0,1) + f(0,0);

    f(i,0) = f(i-1,0) +f(i-1,1);

    f(i,1) = f(i-1,1)+ f(i-1,0);

    ...

    Let DP[u][j][x]= (the set of vertices that the vertex u, on the j-th, x-th state of this function can reach);

    Basically, for each edge u->v,w , you must add: Dp[u][0][w][v]=1; then, for each i until (60) for each vertex u for each i, w of the funcion f , you must calculate the Dp[u][i][w];

    Remember that we have calculated the Dp[u][i-1][w]! Then , for each vertex v , that you can reach on the state(u,i-1,w) , we have to add the set of vertex that the state(v,i-1,!w).

    to implement union of sets efficiently you could use a bitset!

    the complexity: O(n^3*log(10^18)).

    Your code here...
    bitset<501> alcance[61][501][2];
    int n,m;
    // 0 = P , 1=B
    // i-esima string , estando no vertice j, com a string bonita ou nao
    // quem esse estado alcanca :) 
    int main()
    {
        sc2(n,m);
        for(int i=0;i<m;i++){
            int u,v,w;
            sc3(u,v,w);
            alcance[0][u][w][v]=1;
        }
        for(int i=1;i<=60;i++)
            for(int u=1;u<=n;u++)
                for(int v=1;v<=n;v++)
                    for(int w=0;w<=1;w++)
                        // se v e alcancado por u com w;
                        if(alcance[i-1][u][w][v])
                            alcance[i][u][w]|=alcance[i-1][v][!w];
                            
                        
                    
                
            
        
        bitset<501> estado;
        estado.reset();
        estado[1]=1;
        ll resp=0;
        bitset<501> prox;
        int bit=0;
        for(int i=60;i>=0;i--){
            prox.reset();
            for(int u=1;u<=n;u++) if(estado[u]){
                prox|=alcance[i][u][bit];
            }
            if(prox.count()) {
                bit=!bit;
                resp+=(1ll<<i);
                estado=prox;
            }
        } 
        if(resp>1e18){
            pri(-1);
        }
        else{
            printf("%lld\n",resp);
        }
        return 0;
    }
    
    

    I hope it helps ! Sorry for my bad english!

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

Can someone find the mistake in my DIV1 B/DIV2 D , it fails on test case 16 http://codeforces.com/contest/782/submission/25261134

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

    It is very difficult to figure out exact problem but I also got WA in pretest for this case first then I corrected it with some small changes in the code. I guess you must be making similar mistake. The second loop that you are using, I guess it should be used n times rather than only one time. The problem is when you make someone switch from first to second option this may create some new conflicts which you have to correct in next iteration. One more thing I can see is you are using the array taken which I think is not necessary, You can just update the map every time (In your second loop). If you still have some problem, Have a look at my solution it is quite similar to yours.

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

      thanks for the reply, " The problem is when you make someone switch from first to second option this may create some new conflicts which you have to correct in next iteration."

      can u give an example for such situation ?

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

        1 ABB ABD

        2 ABB ABE

        3 ABX ABY

        4 ABF ABX

        5 ABE ABF

        Have a look at this. The first column is first choice and second column is second choice. I guess this is what I am talking.

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

      Why loop N times? How does iterating N times completely remove all conflicts?

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

        In 1 loop you at least fix one of the relation. That relation you will never change again. So after n loops all of them will get fixed value. ( Another intuition to this is it is like we are finding a matching using Ford fulkersons and finding the augmenting path in every loop, So after finding n augmenting path, We find a matching)

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

    Did you find a solution? I'm also struggling with WA on test #16 http://codeforces.com/contest/782/submission/25303767. Did you find a have a simpler failing testset? On:

    5 ABB D ABB E ABX Y ABF X ABE F

    I get (correctly):

    YES ABD ABE ABY ABX ABF

    EDIT: Oh, forget it, think I found it, I go wrong on:

    4 AAA B AAA D AAC E AAD C

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

Ohh thanks :D

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

where I can find the editorial to the DIV 2 problems of this contest. Any help please. Apart from that can anyone explain the solution to the second problem i.e. the meeting place can't be changed.

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

In DIV2 B, I get TLE on test 3 http://codeforces.com/contest/782/submission/25283174

but if i write functions for min and max , it gets AC http://codeforces.com/contest/782/submission/25283217

why is it so ?

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

    Your mistake — double d = 1e-9. If you write, for example, double d = 1e-7 you will get AC with both min/max functions. Also you can use long double, it (probably) takes 16 bytes.

    Double numbers on server (probably) takes 8 bytes, so maximum count of significant decimal digits is about 17.

    Sorry for my english:)

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

Will there be an editorial? Or is there anybody can tell me why simple dfs can work on DIV2-E/DIV1-C and how to prove the correctness? Thanks a lot

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

    Basically the idea is that if you solved the problem for k = 1, then you can solve for k > 1 as well since you just take the solution for k = 1, split it into k equal parts and make sure each part is nonempty.

    To solve for k = 1, you need to go through all vertices in the graph in at most 2n moves. Since the graph is connected, we can find a spanning tree of it. Now, we can just do an euler tour on the spanning tree which contains 2n - 1 vertices. DFS can be used to find the spanning tree.

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

For div2/B is there any solution rather than binary/ternary search?

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

This is the first time to go to blue Expert! Incredibly!!!

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

    And this was my 7th time to become Expert... I wish I could be that excited. :)

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

      I just use codeforces one year! :)

      You dropped down to Expert, I rose to there.... Perhaps next contest will kick my ass dropping down to specialist! ahaha

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

Edutorial please...

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

Is there an editorial for the contest KAN ?

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

In div2D, I want to know the answer of below case. 3 ABC DEF ABD EFG ABE DEF

I think the answer is YES(ABC,ABD,ABE), but my source print "NO" although I got an AC.

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

For people who are having trouble with Test case 16 on DIV2 D, consider this test case:

4

ABD BCD

ABC DDD

ABR CDD

ABR XYY

The answer should be:

YES

ABB

ABD

ABC

ABX

My solution which gives WA on test 16 fails this test too.

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

Solution for Div 1 E ? Anyone ?

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

can anyone help me in understanding of div2B editorial ?

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

can someone please find why i am getting runtime error in python2.7 in problem C div 2?

Here is my code, a big thanks in advance