By awoo, 5 years ago, translation, In English

Hello Codeforces!

On Sep/05/2019 17:35 (Moscow time) Educational Codeforces Round 72 (Rated for Div. 2) will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 6 problems and 2 hours to solve them.

The problems were invented and prepared by Roman Roms Glazov, Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

Our friends at Harbour.Space also have a message for you:

Hello Codeforces,

Harbour.Space University and UTCC are collaborating to offer graduate students from anywhere in the world a once in a lifetime opportunity: fully funded scholarships for our Masters programs in Bangkok.

These scholarships are designed to completely eliminate the barrier between exceptional talents and sophisticated education: they cover the entire tuition fee as well as the cost of living expenses, and furthermore, they provide the student the valuable experience of both studying and working at Harbour.Space University.

We’re looking for the people who are going to change the world.

If you or someone you know are interested in technology, entrepreneurship, or design, and believe you have what it takes, we want to hear from you!

APPLY HERE→

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 Tropical_maid 6 212
2 Return.Hao 6 246
3 xyz100 6 272
4 YangDavid 6 280
5 Lawali 6 300

Congratulations to the best hackers:

Rank Competitor Hack Count
1 VegetableP 116:-14
2 Princ_iple 49:-1
3 racsosabe 42:-1
4 shurongwang 36
5 Megatron_99 29:-1
1432 successful hacks and 1595 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A xyz100 0:02
B talant 0:06
C Laiu 0:06
D IgorI 0:08
E Umi 0:30
F Hasan0540 0:51

UPD: The editorial is out

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

| Write comment?
»
5 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Thanks for round! :)

»
5 years ago, # |
Rev. 2   Vote: I like it -78 Vote: I do not like it

:(( a funny picture. but -64 downvoted. :(( sorry i deleted it

  • »
    »
    5 years ago, # ^ |
      Vote: I like it -26 Vote: I do not like it

    Two funny images, why so heavily downvoted?

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it -28 Vote: I do not like it

      i don't know :(( Why??? i tried with funny comments. but -44 voted? :D what the f* ?

    • »
      »
      »
      5 years ago, # ^ |
      Rev. 2   Vote: I like it -21 Vote: I do not like it

      i think that i will not write a another comment :(( So sad..

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

      because this is codeforces not memes center.. jokes here needs right timing so posting some joke before the round starts is not a good idea unless you're legendary grand master even if you write "potato" you'll get upvoted

»
5 years ago, # |
  Vote: I like it +21 Vote: I do not like it

funny picture always got upvote

»
5 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Would anyone be interested in a round written solely by tourist?

»
5 years ago, # |
  Vote: I like it -21 Vote: I do not like it

Two rounds in two days, the later one must be a good round...

»
5 years ago, # |
  Vote: I like it -22 Vote: I do not like it

Seems like Codeforces wants me to give this contest as a rated one

»
5 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Hope this round will be like last educational

»
5 years ago, # |
Rev. 2   Vote: I like it -24 Vote: I do not like it

[deleted]

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I want to know if I will lost some rating if i dont have time to join this round.....

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

    Certainly not. You will not be considered as an official participant if you don't even make a single attempt.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What will be the difficulty of the problems? I have just started with cp.

»
5 years ago, # |
  Vote: I like it -17 Vote: I do not like it

Hopefully I can gain more rating!

»
5 years ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

Wanna become blue today...

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

when can we upsolve the problems?

»
5 years ago, # |
  Vote: I like it +27 Vote: I do not like it

For E my time complexity was O(q*digits*log(n)) which got TL-5. How to do it better?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Use int instead of long long

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

    My submission 60129750 got 1497 ms (complexity is the same)

  • »
    »
    5 years ago, # ^ |
    Rev. 6   Vote: I like it -10 Vote: I do not like it

    the shortest form of this problem: give you number Heads, list of blows and answer the fastest way to kill it (Heads<=0). There are 2 cases here: Result=1 and Result>1. When Result=1, you just simply pick the blow with the biggest damage value. When Result>1 (2,3...), you will notice that the moment the dragon die is before the the last rivival (Heads increase again) and number Heads become not positive so the last revival will not happen, If you have Result number time of blows, obviously, first Result-1 time you will change Heads by sum of (-damage+rivive), but for last you just change Heads number by minus damage value. So with case Result>1, you just simply pick the blow with the smallest (-damage+revive) for first Result-1 blows, and the last blow you just need to pick the blow with the biggest damage to end the fight. Hope you get it. I also struggled a lots to find out this logic, simple but hard to make it right in the center quickly. EDIT: So sorry, I made a mistake. I saw something about problem B so... Forgive me

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

    I think it's because of digit function in your code. I think it's $$$O(q*digits^2*log(n))$$$ in worst case.

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

    I also had the same complexity https://codeforces.com/contest/1217/submission/60133014 got tle at tc5.. can anybody tell why?

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think it might be due to that combining nodes function(ret in your code). I had same merging function but also extra digit factor in complexity so it got well deserved TL.

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        i optimized it but still the same.. the time limit shouldn't be this strict

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
          Rev. 3   Vote: I like it +5 Vote: I do not like it

          You should pick one. scanf,printf or cin/cout with fastio.

          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Oh F.. I didn't see that. Thanks a lot

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

    I got 1.996s on pretests and didn't realize lol.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem F ?

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

    $$$last$$$ can only be $$$0$$$ or $$$1$$$, so we can make $$$2m$$$ operations and do them offline.

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

      Is there a solution which can handle these types of queries with divide-and-conquer dynamic connectivity method?

      I know it's a strange thing to ask since I am one of the authors of the contest, but nevertheless.

      • »
        »
        »
        »
        5 years ago, # ^ |
        Rev. 4   Vote: I like it +3 Vote: I do not like it

        Assume there are $$$n$$$ vertices, $$$m$$$ edges in graph $$$G$$$, and we need to process $$$q$$$ operations.

        1. Let's denote all the endpoints in these $$$q$$$ operations as important vertices.

        2. Keep all the edges not mentioned in these $$$q$$$ operations in $$$G$$$, and run a linear DFS to find all the connected components.

        3. Remove all the components that contain no important vertices, since they are useless for these queries at all.

        4. Compress each component to a single vertex, and remark all the operations. Let's denote the compressed graph as $$$G'$$$.

        5. Process the first q/2 operations using $$$G'$$$ recursively.

        6. Now we know all the answer of the first q/2 queries, so we can know what the real modifications are. Do these modifications to get a new graph G''.

        7. Process the last q/2 operations using G'' recursively.

        Time complexity is T(q)=2T(q/2)+O(q)=O(q log q).

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But how? I don't really understand.

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

        I think I actually got it, how to use the segment tree trick with DCP in this problem.

        For each edge, there are multiple segments where it may or may not be present (its status may change when we make a query of first type with $$$x, y$$$ or $$$x - 1, y - 1$$$). Let's add these segments in the segment tree just the way we did it in original dynamic connectivity problem, we will have no more than $$$q \log q$$$ additions into the segment tree.

        Then, while we are running DFS in the segment tree, we firstly go into the left subtree, solve the problem recursively. And after we processed all queries from the left subtree, we now know everything about all edges we could add in our right son — this is the key point that allows us to use this approach.

        Originally, when HellKitsune taught me the divide-and-conquer technique to the dynamic connectivity problem, I was a bit disapponted that the sqrt-decomposition trick is kinda useless in this problem — it is harder to code, it runs slower. So I wanted to create a problem that would show that sqrt-decomposition could still be better than divide-and-conquer in some cases of DCP. It turns out I failed.

        But the sqrt-decomposition solution for this problem is much easier. Divide the queries into $$$K$$$ blocks. For each block, we know some edges that are always present no matter what, and each query asks us to use no more than $$$\frac{2q}{K}$$$ edges that may not present in the whole block.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      can you please explain a little bit more?

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I don't understand. Since $$$last$$$ could be 0 or 1 on each query, doesn't that mean that in total there are $$$2^m$$$ possible chains of operations?

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

        Yes, we can have $$$2^{m}$$$ possible chains if we are trying to do it purely offline. But offline dynamic connectivity approaches can be modified in such way that we do not need to know all the queries beforehand. Instead of marking places when edge inclusion changes, we can mark places where edge inclusion might change and when we will have all the information make these decisions in process whether to include edge or not do include edge for future stable segment until this edge might change again.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    u can also solve with using dynamic connectivity

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      There's no such thing as online dynamic general graph connectivity as far as I know :<

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it -10 Vote: I do not like it

        Fuck, i forgot its online queries xd

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

        There is one. It involves some really heavy magic with Link-Cut Trees.

        Some accepted submissions use that approach.

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

          Ok, looked it up. I bow to thee BledBest, I can die at peace, even as a unicorn I'm still totally mindblown by such magic.

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

            Even as a red I am mindblown by it too.

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

          It is called HDT algorithm. It was named after it's inventors Jacob Holm, Kristian de Lichtenberg and Mikkel Thorup. Time complexity is amortized $$$O(log^2n)$$$ per update and $$$O(logn)$$$ per query. There is also an implementation using Euler Tour Trees instead of Link-Cut Trees.

          The best known algorithm for online dynamic connectivity problem runs in amortized $$$O(\frac{log^2n}{loglogn})$$$ per update and $$$O(\frac{logn}{loglogn})$$$ per query using Thorup's randomized data structure.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

getting WA on test 2 in B, whats is the logic or tell me something wrong in my solution please.

link of my solution

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    if all d < h and has no d >= x — result -1

    next chose a=max(di-hi) and b=maxd, last step max(a,b), all steps before last (b)

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      haha lol, I comment d>= x here. but in my contest submission write d>x)

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

    the shortest form of this problem: give you number Heads, list of blows and answer the fastest way to kill it (Heads<=0). There are 2 cases here: Result=1 and Result>1. When Result=1, you just simply pick the blow with the biggest damage value. When Result>1 (2,3...), you will notice that the moment the dragon die is before the the last revival (Heads increase again) and number Heads become not positive so the last revival will not happen, If you have Result number time of blows, obviously, first Result-1 time you will change Heads by sum of (-damage+rivive), but for last you just change Heads number by minus damage value. So with case Result>1, you just simply pick the blow with the smallest (-damage+revive) for first Result-1 blows, and the last blow you just need to pick the blow with the biggest damage to end the fight. Hope you get it. I also struggled a lots to find out this logic, simple but hard to make it right in the center quickly.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How To Solve C..?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How to solve C with out gettin TLE on test 12 ??????????

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

    First of all, if at a given index, s[i] == '1', then the index of the last good substring starting at i is at most (i + 20), otherwise the value of the binary number is larger than the max length of the string. So, for every index, we precompute the next occurrence of '1' and check the next 20 characters. Repeat.

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

      i still don't understand about this one i is at most (i + 20), could you explain why the last good substring starting at i is at most (i + 20) ?

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

        Because a binary number with length 20 and no leading zeroes is at least $$$2^{19}$$$ which is greater than the maximum possible length of the string so it can never be valid.

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

    my solution:

    precalc zeroes-array: how many zeroes before ith element

    next start from first (1) and count zeroes before (from precalc), if (f-length<=number of zeroes) result++. next shift left index to next 1-characker, if length > 20 (i think it is enough) you can break from cycle.

    (for example 000101)

    first step: 000[1]01

    number of zeroes before before = 3, f=1 and 3 enough to add to result (1-1<=3)

    next step go to 000[10]1

    in this case your f=2, length=2, zeroes before=3 => result++

    next step got to 00010[1] — same as first step (except zeroes before = 1, but also enought 1-1<1)

    next step got to 000[101] — f=5, lenght=3, number of zeroes = 3 (5-3<=3) => result++

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks a lot! Nice solution, really easy to code.

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Your implementation and description in comments more clearly, thanks!

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

      Good explanation.
      I upsolved in similar maner using regex, where zeroes-calc are made on the fly. Solution in Perl is quite slow, it passes in 3.6s — 60140161. Regex finds every position starting with '1' and then looks-ahead upto 18 bits.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How do you get the formula if (f — length <= number of zeroes) then result++ I mean logic behind it

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        f — function result that we needed to achieve (for example for 111 = 7)

        length — already achieved length (for 111 = 3)

        good substring when f == length

        it is obviously that we need to add some (may be 0 zeroes) leading zeroes for case when f == l, and if for your suffix of substring which has no leading zeroes can be added some leading zeroes to case when f == l you can increment your result.

        You can check first numbers

        1 = 1 (f = 1, l = 1)

        2 = 10 (f=2, l =2)

        3 = 11 = 011 (f=2, l=2, need 1 leading zero)

        4 = 100 = 0100 (f=4, l=3, need 1 leading zero)

        Sorry for my english, hope you understand

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

how to solve A? hahahahaha

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

    The boundary cases are little convoluted in the problem A, I guess.

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

How to solve D?

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

    Colour every back edge as black and the remaining edges as white. Since any cycle cannot contain all back edges, hence we cannot have a cycle containing all edges of the same colour.

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

    If there is no cycle, answer is 1. Otherwise paint an edge $$$(u, v)$$$ white if $$$u < v$$$, else black.

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it +20 Vote: I do not like it
    • If there is no cycle the answer is 1
    • Else you can use one color for the edges u->v where u < v and another for the edges u->v where u > v so the answer is 2

    To find if there is a cycle in a directed graph, you can do a DFS marking differently vertex currently treated and vertex you finished treating. If you encounter a vertice still in treatment, it means it's an ancestor in the DFS and you have a cycle.

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

    Incoming and outgoing edges colored differently ensures this. Question: Does Upper bound of 2 also hold for undirected given no multiple edges?

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

      For undirected graphs, the edges of one color form a tree so atmost $$$n-1$$$ edges, but the graph can have $$$\frac{n(n-1)}{2}$$$ edges so it is clear the bound of 2 will not hold.

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

    How to solve D if it is a undirected graph

»
5 years ago, # |
  Vote: I like it +33 Vote: I do not like it

Anyone who used binary search for A?

I am a bit nervous about my approach..

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

    You can check my solution, where I used binary serch.

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

    I also used binary search

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

    I also solved using binary search.

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

    me too,binary search is more intuitive than pure math equation to me

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No need for binary search, see my O(1) solution — https://codeforces.com/contest/1217/submission/60107664

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

      I did realize that O(1) solution exists, but for some reasons I thought that it would have more number of cases, hence more chances of some edge case failing.

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

      Problem A 60157777

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        could you explain how you approach the problem?

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          (y+z) — maximum int (int+exp) that can be achieved

          (y+z)-x — difference maxInt — minStr that can be achieved

          ((y+z)-x+2)/2 number of points that we can get from int, and add to str for cases when str <= int (each point from int to str make difference less on two points), if this value < 0 it means str always > int

          i think its better to write right+1 (z+1), because there is (exp+1) options to distribute exp points (you can add from 0 to exp points to str) result = (exp+1)-left > how many options for distribution we have (for cases when str > 1)

          if result <= 0 there is no options => print 0

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

    not much work just find range [lb,ub] and ub-lb+1 is answer.a,b,c is input. x>=a and y>=b and x>y and x+y=a+b+c always which leads to x ranges from max(a,sum/2+1) to sum-b,now range difference are your total solution.

»
5 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Anyone has a solution for problem E with 10*(3 of segment queries) per query passed ?? Is it intended to pass or not ?

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

    I did the same thing got tle

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

    I am very very sad that my solution got accepted now (after the contest) just by using this implementation of segment tree.

    So sad, that the implementation of the segment tree played a role in getting accepted for this problem. Was this intended ???? and why ??

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      my solution with few changes got accepted.. 1) changed long long to int 2) instead of cout/cin fio using scanf/printf 3) optimized ret function

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

    I think you can do 1 query (but complexity remains the same). Just store two minimums for each digit. Constant will be much better than 3 * 10 separate queries.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how to pass test 2 problem C

»
5 years ago, # |
  Vote: I like it +29 Vote: I do not like it

what is the hack for B ?

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

    i think alot of people checked for case where highest damage is more than number off heads but did not check when that it equal.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      nope i got hacked on that one i checked first max difference <= heads return -1, i got hacked there , test cases were pretty weak.actually i didn't check max damage>=head count.most people solution is failing on that.

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it +4 Vote: I do not like it
    • 1
    • 1 1
    • 1 1

    hacked 6 people with the same test case, one candidate master :)-

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve E?

»
5 years ago, # |
  Vote: I like it +6 Vote: I do not like it

I think I am not able to tell how fucking annoying it is to not get A right for an hour or more...and then miss C for like 5 minutes.

What was so hard with A, why did I need 10 submissions?

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I hope there is a simple solution for F. My solution is too complicated.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

"It is guaranteed that each ordered pair (u, v) appears in the list of edges at most once."

What is mean ordered pair in problem D ?

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

    which means (u, v) is considered different from (v,u).

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think it means that u can have an edge in both directions, but u can't have multiple edges from node u to node v in the same direction.

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

    Thank you! I mistook the meaning of "ordered" as "sorted"..

»
5 years ago, # |
  Vote: I like it +10 Vote: I do not like it

In $$$E$$$, what is the best way to know the smallest $$$2$$$ numbers between $$$L$$$ and $$$R$$$ such that they both have a non zero digit at a same position?

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

    I didn't have enough time to submit, but my idea is to build a segment tree for each digit. I planned to fill them in the following fashion: if $$$k$$$-th digit of $$$a_i$$$ is not $$$0$$$, then we put $$$a_i$$$ on place $$$i$$$ in the $$$k$$$-th segment tree, else some huge constant. To get the answer, you could take two minimums on each tree and choose the one with minimum sum.

    Should pass in time, pure $$$O(n \cdot logn)$$$, albeit with a considerable constant.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you.

      I think the complexity should be $$$O(n*log_{10}(max\,value)+m*log_{10}(max\,value)*log_2(n))$$$. Where the term before $$$+$$$ is for trees builds, and the other is for queries.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    for each position, build a segment tree, for each segment, maintain the smallest and second smallest number which both has non-zero digit in that position

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For some reason I was thinking during the contest about maintaining something like merge sort tree for every digit position instead of just a normal segment tree through which you can get 2 minimums, and simulate non-existing numbers by large constants. Thanks all.

»
5 years ago, # |
  Vote: I like it +4 Vote: I do not like it

hack successful test for problem B?

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I did problem C in O(N*logN*logN). Any better solution?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it -14 Vote: I do not like it

    My solution ~ O(N): https://codeforces.com/contest/1217/submission/60132911 if you want to tutorial, inbox for me.

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

    A good substring starting with '1' can be only '1' or '10' (the ones with length $$$x$$$ > 2 are at least $$$2^x$$$ and thus larger than $$$x$$$) — these can be checked with $$$O(N)$$$.

    If a good substring starts with '0', there can be at most one good substring starting at given index (if it is of length $$$x$$$, and equals $$$x$$$, then already the next one will equal at least 2x > $$$x+1$$$). To find these for every given index, you can enumerate possible lengths (length can be from 2 to log2($$$2 \cdot 10^5$$$)), starting from the nearest following '1'. This is $$$O(NlogN)$$$.

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

      Thanks! Did the same afterwards!

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

      This is also what I did, but I assumed there was a simpler solution I was missing. Seems surprisingly challenging for Educational round C.

»
5 years ago, # |
Rev. 2   Vote: I like it +10 Vote: I do not like it
1
1 1
1 1

This is such an obvious hack case for problem B, I wonder why it wasn't in the pretests??

»
5 years ago, # |
  Vote: I like it +38 Vote: I do not like it

very bad pretests for B((

»
5 years ago, # |
  Vote: I like it +17 Vote: I do not like it

indeed a great round at hackforces...

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Poor testcases :(

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem B: What is the output for this input. 1 3 999999911 3 1 11 1000000000 10 9

Jury's answer is 499999951. How ?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hit em with (3, 1) 499999950 times, finally use the (11, 10...) to finish it. Are you suggesting there's a solution with fewer hits?

»
5 years ago, # |
  Vote: I like it +41 Vote: I do not like it

Looks like CF managed to automate Problem Setting

»
5 years ago, # |
  Vote: I like it +24 Vote: I do not like it

The most wrong answer contest I have ever seen hahahahaha.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to Solve D??

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

    If there is no cycles in our graph we can simply use $$$k=1$$$.

    For all other cases we can be done with $$$k=2$$$. Suppose we have edges in form $$$(from, to)$$$, we can paint all edges with $$$from < to$$$ into color $$$1$$$ and all edges with $$$from > to$$$ into color $$$2$$$. If we arrange all vertices of our graph into a sequence, edges that go left are of one color and edges that go right are of another color. Any cycle must start and end in the same vertex, so after making a first step left or right we need to move backwards, but we can only do it with edges of another color.

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

Man, I got like 11 WAs on Problem A, and still couldn't solve it. I used this equation :- str + x > int + y && x + y == exp , then finding all possible values of x and y. Can someone provide a clear implementation for this, i think i messed up in calculating the number of solutions.(or are these equations missing something?)

  • »
    »
    5 years ago, # ^ |
    Rev. 7   Vote: I like it +6 Vote: I do not like it

    If exp + strength <= Intelligence , then there's no solution, answer is 0.

    If exp + Intelligence < strength , then all combinations will work, the answer is exp + 1.

    If exp + Intelligence = strength , all combinations except (strength, intelligence + exp) wil work , answer is exp.

    now for the last case, the minimum exp that can be added to strength without disturbing the inequality strength > intelligence is the solution to:

    Let x be the minimum exp required.

    (strength + x) — (intelligence + (exp — x)) = 1

    x = ceil((1 — strength + intelligence + exp) / 2)

    the answer is exp — x + 1

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks mate!

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      you could solve it pretty obviously.S,I,E is input. now we know that X>=S and Y>=I and X>Y,constraints X+Y=S+I+E=sum => Y=sum-X substituting value we get boundary of X i.e., X belongs [max(S,sum/2+1),sum-b] hence final answer is R-L+1. you could look at my code its just 4 lines. code

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.com/contest/1217/submission/60110076

Please Hack this, this is surely not O(N)/O(NlogN) .

»
5 years ago, # |
  Vote: I like it -24 Vote: I do not like it

Honestly, Educational rounds are not as interesting as they once were.

  • »
    »
    5 years ago, # ^ |
    Rev. 3   Vote: I like it +52 Vote: I do not like it

    Why not to say it from your real account, not fake one? Are you afraid of downvotes? Or afraid of us?

    P.S.: I'm not arguing about the statement itself, just about people who can't honestly state their opinion.

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Problem A was harder than Problem B :(

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please give me a test case on which my solution fails:)

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

    You can easily extract the test case from the online judge. It says that the 73rd number differs, so, resubmit your solution, and print the 73rd query on the console. (Maybe at the start)

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    try 10 0 4

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But in given constraints only third number can zero and first and second are always positive.

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Ok then try 10 1 4 Still the same problem

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    try 100 10 2 Answer is 3 but your output will be 46

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

When I first saw this 1000 liner code, I thought, is this the end of the universe?

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

    Isn't this code very similar to this code: 60123155? Even the strangest of variable names like ee, uuu, vvv, te, etc., in the main code or just before it are the same.

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

      MikeMirzayanov, awoo can u please check. I believe intentional efforts have been made to avoid plagiarism, like performing n = N, when there was almost no use of doing it, and also statements like if(op == 2) op = 2

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        The order of some of the statements or expressions has also been intentionally swapped.

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

          No, it's not. If you look more carefully at my previous submission 60108293, you will see that I have marked “template from https://loj.ac/submission/25943” as comment on the first line. Actually this problem is almost exactly the same as this one on LOJ, except some I/O format and the way of forcing online. So I copied a public submission on LOJ and changed it a little bit to pass this one. According to the rules about third-party code, it's ok to do so, and I believe Return.Hao just copied from the same template.

          Reporting cheating is good, but I'd like to say you had better check more things out before you make your report.

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

            I am extremely sorry for this. I checked the last submission only as they were the ones that would've contributed to the final results and found no attribution on them, and as I said in my previous comment, a few of the statements only differed in a very suspicious way like the case of doing n = N as I mentioned above. That's what made my doubts more concrete. That's why I thought it was a cheating case. Sorry once again.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain me how to solve C please?I dont understand the idea of this problem.

  • »
    »
    5 years ago, # ^ |
    Rev. 3   Vote: I like it +35 Vote: I do not like it

    First let's preprocess the array z, such that:

    z[i] = number of zeroes to the left of i before the first 1.

    For instance:

    v: 0 0 0 1 1 0 1

    z: 0 1 2 3 0 0 1

    What the problem wants is the number of substrings s[l..r] such that the binary number in s[l..r] is equal to its range size r - l + 1.

    Now let's say you're currently at index i and s[i] == '1'. You've already got your first answer, right? because s[i] == 1 and the range size is 1. Let's call our current value X and keep constructing new numbers using substrings that start in this index i and end at some index j (s[i..j]).

    Notice that j < min(n, i+20). Because the maximum range size possible is 2*10^5 and you need less than 20 bits to construct that value.

    Now let's add the next bit (at j'th position) and calculate our new value X, if the next bit is 1, X = 2*X + 1 and if the next bit is 0, then X = 2*X.

    So for this substring to be good, we need it to have size X. Since we started at i and we're now at j, its size is currently j-i+1. But remember we have z[i] zeroes to the left! That means that if we could add those zeroes to its left (which doesn't change the value X) and make a substring of size z[i] + j - i + 1 such that z[i] + j - i + 1 >= X, then we found a new answer.

    Hope that was well explained! :D

»
5 years ago, # |
  Vote: I like it +11 Vote: I do not like it

How would you solve D if the edges were undirected?

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

    If graph is undirected this problem is about finding arboricity of given graph. This goes to matroid theory and is actually graphic matroid partitioning problem.

    UPD: If someone is interested in practical introduction to this stuff, you may check out this tutorial.

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

    UPD: Nevermind :(

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

      Back edges can form a cycle. Example: 5 nodes, dfs tree is 1-2-3-4-5, and there are also edges 1-3, 3-5 and 5-1.

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Holy shit, you are right, sorry.

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

        It depends on what are "back edges". For me, if there is next list of edges: (1,2), (2,3), (3,4), (4,5), (1,3), (3,5), (5,1) and dfs tree is 1-2-3-4-5, then (1,3) and (3,5) are forward edges and (5,1) is back edge. So, coloring only (5,1) is ok.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can we hack our own solution, if its already been hacked by somebody, rip rating, didnt realise the stupid test case, 1 4 5 6 6 6 6 6 6 6 6 this was obvious test case, why was it not included in test case list, most of people got hacked on this.

»
5 years ago, # |
  Vote: I like it +24 Vote: I do not like it

What is intended complexity for E? I did mlogn*10 and it is getting TLE. My implementation of seg tree is pretty not efficient, but why would you give so strict time limit? What is wrong in setting this for 4s?

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

    I've never considered my implementation to be efficient at all. I mean my usual recursive segtree works in 400 ms, so 2 seconds doesn't seem strict. I also think there might have been worse complexity solutions passing if TL was higher.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hm, im confused now. Is intended solution building 10 seg trees for each digit, and then for each query we need to visit all of them so complexity of one query is 10logn?

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes, it is. I think the part I didn't take into consideration is that I update all the 9 trees during the same query, so I'm jumping at lot less around the memory, what makes the runtime much lower.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I haven't managed to get within TL with inefficient segment tree implementation. The "efficient and easy" implementation did the trick, but still only 1.5 s...

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

Delted

»
5 years ago, # |
  Vote: I like it +9 Vote: I do not like it

I think there's a small error in putting "Final Standings" after the hacking phase, but before system tests.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

B pre-test should be made stronger

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

Why my solution 60134423 passed pretest in 1954ms. But after system test it gets TLE on pretest8 ?

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

    The runtime is never exact, I guess it can vary quite a bit (maybe ~100ms), even if running on the same test and on the same server.

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

B have 365 cases at system test lol~

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Interesting binary search solution of problem A: 60157777

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

    This is not binary search, it is O(1). He calculates min and max values for s, named them left and right.

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

I got AC on D with following greedy solution:

Take any edge, if it has unicolored path from one of its ends, to other, take another color.

Is it possible to hack it? I guess that it is possible, but there are no such tests in system testing.

»
5 years ago, # |
Rev. 4   Vote: I like it +10 Vote: I do not like it

Hello Codeforces,

After yesterday's contest(Educational Codeforces Round 72 (Rated for Div. 2)) I have received 3 system messages. For the problems A, B and C. And these are all the problems I have solved during the contest.

Messages say that my solutions are extremely similar to this guy's coderharshit. Actually I have checked and they are identical.

For quite some time now I have been using this github repo to store my solutions.

I always push my code after the contest, actually I usually forget and do it much later.

Yesterday I just didn't think of people would dig google/github to find solutions during the contest and find my code. And I pushed the solutions during the contest. You can see the time of the commit in github.

So this person, apparently a determined soul to find other people's solutions found my solutions and blatantly submitted all of them. Don't know what to think of these people :) .

In the system messages, I was asked to write a comment here if I have evidence that I have published the code publicly and they accessed it, so writing this now.

fyi, MikeMirzayanov

Best, Burak

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

    why do you use public repo during contests?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    bad luck for you.

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

    It is entirely your responsibility to ensure that the code you submit stays private during the contest.

    "I just didn't think of people would dig google" is not a proper justification.

    There were plenty of cases before of people coding on ideone, forgetting to set it on private, and getting penalized.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      yeah can't deny that :), anyway these things happen. I have participated in 44 contests and it is the first time

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I want to say... What is the pretest of problem B made of?

It has $$$364$$$ tests. Is there an official problem with more number of testcases?

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

    I think most of tests added as success hacking attempts (unique I think). You can check, I think most of test have similiar idea.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Many random problems have lots of testcases

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Still waiting for the Editorial :||||||

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

boy, this contest was really tough for me, I was completely discouraged by even first task. however, it's so exciting always (2 times for me heh)

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think it must have been tough on almost everybody. I only solved one problem (as against my normal of 3 or 4) yet maintained my rating of 1539 (0 change in rating).

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

Any ideas for WA on test case 5 for E?