For technical reasons, some programming languages (Kotlin, C #) will not be available during round 877. ×

KAN's blog

By KAN, 8 months ago, translation, In English,

Hello everybody!

The Technocup 2017 (a competition for high-school students hosted by Mail.Ru Group together with MIPT, Bauman MSTU and Codeforces) Finals is happening tomorrow in Moscow. For those who will not participate in the Finals, we prepared mirror contests for both divisions. The round will start at 13:05 UTC at Sunday, March 5th, 2017 and will last for two hours.

The round was prepared by Endagorion, WHITE2302, Alladdin, fcspartakm, Amethyst1, MikeMirzayanov, ifsmirnov and me.

You can view the current onsite results at link.

There will be six problems in each division.

Editorial is here.

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

»
8 months ago, # |
  Vote: I like it +61 Vote: I do not like it

Why isn't this on the home page?

»
8 months ago, # |
  Vote: I like it +45 Vote: I do not like it

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

»
8 months ago, # |
  Vote: I like it +26 Vote: I do not like it

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

Syrian contestants will relate :( :( :(

»
8 months ago, # |
  Vote: I like it +12 Vote: I do not like it

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

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
8 months ago, # |
  Vote: I like it +9 Vote: I do not like it

Scoring distribution ?

»
8 months ago, # |
  Vote: I like it +9 Vote: I do not like it

Will it be rated or unrated?

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

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

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        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'.

»
8 months ago, # |
  Vote: I like it -62 Vote: I do not like it

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

»
8 months ago, # |
  Vote: I like it +73 Vote: I do not like it

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

»
8 months ago, # |
  Vote: I like it +2 Vote: I do not like it

What are the problem scores?

»
8 months ago, # |
  Vote: I like it +5 Vote: I do not like it

scores distribution?

»
8 months ago, # |
Rev. 2   Vote: I like it +53 Vote: I do not like it

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!

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Amazing! Thank you.

    What is seed? My position in sorted list of competitors ordered by their rating?

»
8 months ago, # |
Rev. 4   Vote: I like it +9 Vote: I do not like it

Very weak pretests in problem D. LOL :D

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

»
8 months ago, # |
Rev. 5   Vote: I like it -50 Vote: I do not like it

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

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Please remove your code, it is covering page, just keep submission link please.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Done.

      I thought that block of code means one can see code only if he clicks on the top of codes, but I was wrong. So I have removed my code.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      Thanks.

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Don't we need ternary search?

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

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

      • »
        »
        »
        »
        8 months ago, # ^ |
        Rev. 2   Vote: I like it +7 Vote: I do not like it

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

      • »
        »
        »
        »
        8 months ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        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 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I used ternary search and got TLE.

          • »
            »
            »
            »
            »
            »
            8 months ago, # ^ |
              Vote: I like it +6 Vote: I do not like it

            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
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Test case 6 in Div 2 B ?

»
8 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

How did you solve Div2 B?

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Binary search the answer.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    8 months ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    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 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Is it possible by applying binary search on distance?

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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)

»
8 months ago, # |
Rev. 2   Vote: I like it +9 Vote: I do not like it

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?

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      8 months ago, # ^ |
      Rev. 2   Vote: I like it +2 Vote: I do not like it

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

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        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 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        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.)

»
8 months ago, # |
Rev. 4   Vote: I like it +102 Vote: I do not like it

A-D: Graphs Graphs Graphs Graphs

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it +19 Vote: I do not like it

        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.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +32 Vote: I do not like it

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

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

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

»
8 months ago, # |
  Vote: I like it +74 Vote: I do not like it

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.

»
8 months ago, # |
  Vote: I like it +15 Vote: I do not like it

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

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    u r not alone my friend. prestest 3 never cleared for me.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Too. Can't even imagine, where I am wrong. Also, I haven't got any changes in my rating. Is it ok?

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think the system is updating the data.

»
8 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    You was right

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      I did it using binary search :/

      • »
        »
        »
        »
        8 months ago, # ^ |
        Rev. 5   Vote: I like it 0 Vote: I do not like it

        Although you failed the main tests.

        • »
          »
          »
          »
          »
          8 months ago, # ^ |
          Rev. 2   Vote: I like it +1 Vote: I do not like it

          I commented before systest was over and thats why the confused emoji was there. Although, it can be solved using binary search. I don't think I said anything wrong there. My implementation maybe wrong but the idea was correct. :)

        • »
          »
          »
          »
          »
          8 months ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          i solved it using binary search and got ac :)

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I used binary search.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve D div1 faster than ?

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Using bitset.

  • »
    »
    8 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Any ideas for Div2C?

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    maximum vertex degree + 1

    • »
      »
      »
      8 months ago, # ^ |
      Rev. 3   Vote: I like it -8 Vote: I do not like it

      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.

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        8 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it
        degree(node_2) + 1 = 4
        
      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 :)

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
8 months ago, # |
  Vote: I like it +4 Vote: I do not like it

That was fast.

»
8 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Thats the fastest system test ever :p

»
8 months ago, # |
  Vote: I like it +10 Vote: I do not like it

How to solve Div1 C?

  • »
    »
    8 months ago, # ^ |
    Rev. 2   Vote: I like it +27 Vote: I do not like it

    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.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Explain to me, please. The total number of verteces, which visited our robots on the basis by K may be < 2 * (n-1), isnt it?

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        No. k*(ceil(2*n)/k) >= 2*n

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    consider a dfs tree

»
8 months ago, # |
  Vote: I like it +9 Vote: I do not like it

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.

»
8 months ago, # |
Rev. 3   Vote: I like it +97 Vote: I do not like it

The test data of Div 1 D is weak.

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

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +117 Vote: I do not like it

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

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +31 Vote: I do not like it

      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 months ago, # ^ |
        Rev. 2   Vote: I like it +13 Vote: I do not like it

        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 months ago, # ^ |
      Vote: I like it +28 Vote: I do not like it

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

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +105 Vote: I do not like it

    Bad job problemsetters :(

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +31 Vote: I do not like it

    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.

»
8 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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.

»
8 months ago, # |
  Vote: I like it +5 Vote: I do not like it

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

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

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

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

»
8 months ago, # |
Rev. 3   Vote: I like it -18 Vote: I do not like it

Pro AF Bug xD

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

  • »
    »
    8 months ago, # ^ |
    Rev. 3   Vote: I like it +6 Vote: I do not like it

    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 months ago, # ^ |
        Vote: I like it -23 Vote: I do not like it

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

»
8 months ago, # |
Rev. 2   Vote: I like it +74 Vote: I do not like it

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.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    Exact same situation :(

  • »
    »
    8 months ago, # ^ |
      Vote: I like it -39 Vote: I do not like it

    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.

»
8 months ago, # |
  Vote: I like it +20 Vote: I do not like it

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

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    • »
      »
      »
      8 months ago, # ^ |
      Rev. 2   Vote: I like it +6 Vote: I do not like it

      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.
      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        But my solution still gives the right answer :(( and I still have no idea what's wrong

»
8 months ago, # |
Rev. 2   Vote: I like it -13 Vote: I do not like it
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    My friends code
  • »
    »
    8 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    here is my solution 25259459

    I use ternary search for finding a meeting place

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 months ago, # ^ |
          Vote: I like it -9 Vote: I do not like it

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

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        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 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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 months ago, # |
Rev. 3   Vote: I like it +20 Vote: I do not like it

Why we can't see successful submissions?

UPD: Seems it is fixed

»
8 months ago, # |
  Vote: I like it +19 Vote: I do not like it

Why can't we see the tests ?

»
8 months ago, # |
Rev. 3   Vote: I like it +5 Vote: I do not like it

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

»
8 months ago, # |
  Vote: I like it +22 Vote: I do not like it

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

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

what's the solution for Div2D?

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    8 months ago, # ^ |
    Rev. 6   Vote: I like it +11 Vote: I do not like it

    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 months ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      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 months ago, # |
Rev. 2   Vote: I like it -38 Vote: I do not like it

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 months ago, # ^ |
    Rev. 2   Vote: I like it +12 Vote: I do not like it

    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 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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 months ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

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 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    On case 4 check your condition again. I think it must be (second(a) == FIRST(b)).

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ops, you're right, I made a mistake in the description but it's correct in the code, thank you! Any other observation?

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    In case 2, when first(a) != first(b), you can choose option1 for both so it should be only (a||b).

»
8 months ago, # |
  Vote: I like it +3 Vote: I do not like it

waiting and waiting for rate change ...

»
8 months ago, # |
Rev. 2   Vote: I like it -8 Vote: I do not like it

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 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 months ago, # |
  Vote: I like it +10 Vote: I do not like it

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 months ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    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 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      8 months ago, # ^ |
      Rev. 2   Vote: I like it +5 Vote: I do not like it

      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 months ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        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 months ago, # |
Rev. 2   Vote: I like it +48 Vote: I do not like it

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 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    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 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Someone with WA16 on Div2D/ Div1B? 25271010

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How can I implement Div2 B using binary search ?

  • »
    »
    8 months ago, # ^ |
    Rev. 3   Vote: I like it +2 Vote: I do not like it

    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 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        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 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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 months ago, # ^ |
    Rev. 3   Vote: I like it +3 Vote: I do not like it

    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 months ago, # |
  Vote: I like it +10 Vote: I do not like it

How to solve Div1E?

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve Div2C with BFS? TIA

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve Div1D/Div2F?

  • »
    »
    8 months ago, # ^ |
    Rev. 9   Vote: I like it +33 Vote: I do not like it

    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 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What is the function f for?

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        I think f(I, 0) is the correct sequence obtained after (I + 1)th step and f(I, 1) is the sequence obtained by changing all P's to B and all B's to P in f(I, 0).

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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 months ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    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 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 months ago, # ^ |
        Rev. 2   Vote: I like it +1 Vote: I do not like it

        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.

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Ohh thanks :D

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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 months ago, # |
  Vote: I like it +5 Vote: I do not like it

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 months ago, # ^ |
      Vote: I like it +25 Vote: I do not like it

    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 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
8 months ago, # |
  Vote: I like it +2 Vote: I do not like it

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

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +27 Vote: I do not like it

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

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      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 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Edutorial please...

»
8 months ago, # |
Rev. 2   Vote: I like it +17 Vote: I do not like it

Is there an editorial for the contest KAN ?

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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 months ago, # |
Rev. 2   Vote: I like it +15 Vote: I do not like it

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 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Solution for Div 1 E ? Anyone ?

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone help me in understanding of div2B editorial ?

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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