By awoo, history, 4 years ago, translation, In English

Hello Codeforces!

On Jun/25/2020 17:35 (Moscow time) Educational Codeforces Round 90 (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 or 7 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!

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 Geothermal 7 130
2 ksun48 7 143
3 300iq 7 147
4 vepifanov 7 168
5 Radewoosh 7 175

Congratulations to the best hackers:

Rank Competitor Hack Count
1 EduPeres 40
2 Grey_Matter 39:-3
3 lx430621 26:-1
4 killa_vanilla 25:-5
5 checkingagain 17:-1
351 successful hacks and 375 unsuccessful hacks were made in total!

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

Problem Competitor Penalty
A Geothermal 0:01
B ksun48 0:01
C ksun48 0:03
D Noureldin 0:09
E Geothermal 0:22
F ElOrdyh 0:15
G dario2994 0:29

UPD: Editorial is out

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

| Write comment?
»
4 years ago, # |
  Vote: I like it +335 Vote: I do not like it

»
4 years ago, # |
  Vote: I like it -60 Vote: I do not like it

yeahhh!! vovuh....big fan...so much excited!!

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

can somebody explain me the way of scoring in educational rounds? I think you will only get scores due to the number of solved problems regardless of their difficulty. am I right?

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

    Yes. How many AC, then how many minutes (penalty).

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

      And bye how many minutes do you mean the total time spent to achieve the score or in some other way?

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

        If you solved any problem in 40 minutes.Then your penalty+=40.and every wrong answer penalty+=10 Generally..If both solved same no of problem then standing will be sorted with penalty.

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

    Good to know, I have participated in a few educationals but did not know this one. :O What I noticed about them is that they tend to be harder than normal Div2 rounds.

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

      Can you please tell what's the difference between educational and div-2 round? I'm new here.

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +10 Vote: I do not like it
        **Educational round
        1.Here only have penalties.here a wrong submission give you +10 penalty.you solved a ques in 20 minutes with 1 wrong submission .then penalty is (20(in 20 minutes you solved that)+10(for 1 wrong submission))=30.
        2.Standing firstly sorted by no of problem solved..if that same then penalty(whose penalty less he/she go up than others) .
        
        **Div 2
        1.Every problem have a score and you can gain the score by solved that.Time going and every problem score slightly(2/4/6 per minutes) decrease..and a wrong submission decrease of that problem score by 50.
        2.Standing sorted by your gained score.
        
»
4 years ago, # |
  Vote: I like it +385 Vote: I do not like it

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

CF4

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

Just curious, in educational rounds announcement, why its mostly written like "6 or 7 problems". Is the number of problems and problems itself not decided till few hours before the contest? Or is there something, which I am unaware of?

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

    I think entire blog is almost copy pasted, maybe so

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

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

:D

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

Pretty excited for this contest !!

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

![ ](WhatsApp-Image-2020-06-19-at-6.41.44-AM.jpg)

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

cf5

»
4 years ago, # |
  Vote: I like it -18 Vote: I do not like it

hope to get a decent rank this time

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

I have one question!, Know the Educational rounds are more than the div1 and most of the Educational rounds have 6 or 7 problems It is a good idea to add one hard problems and make educational to div1 ? :)

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

When I find People Cheating in Rated Rounds

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

    But after seeing that there code are same even comments are same my heart like "OOOH LALA";)

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

Excited for vovuh div2 round after a long time.

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

Good luck everyone

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

IMG-20200625-165915

»
4 years ago, # |
  Vote: I like it -6 Vote: I do not like it

More than 20k people registered for this contest! Looks like it will be a fun contest.

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

Who is this vovuh and why are people so excited about him?

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

    Spend some time on cf giving contests regularly and you will be able to answer this yourself.

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

    He is the chosen one who sends all undeserving people like me from specialist to expert.

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

If I get WA1 on A and I can't proceed with the contest, will my rating drop?

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

Nobody:

Problem A in every Educational Round ever:

  • 1 < t < 1000

  • 1 < a, b, c, x, y, z < 10⁹

Seriously?

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

Again B is easy than A -_-

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

    Actually, in Educational round it doesn't matter at all)

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

      matter brother..If a,b swap then my penalty only for A B will be (6+17)=23..But now it was (11+17)=28.

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

        If everyone finds A difficult than B, than it is actually difficult, and if everyone else finds it difficult, then all would take time to do that question and eventually your rank would be good even though you had more penalty

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

        And currently, mine is $$$(6 + 7)$$$ = $$$13$$$, but if they would have swapped $$$A$$$ and $$$B$$$, it would have been $$$(1 + 7)$$$ = $$$8$$$. But that doesn't matter much, rating would have been affected by $$$1$$$. Focus on improving skills brother!

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

    idea was simple but problem statement could have been worded better

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

OK, E is above my level. Go to bed instead.

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

    I would suggest don't give up and keep trying :)

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

      and what are you doing ?

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

        Trying to motivate others. That's a good thing to do I guess. What are you doing?

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

          I am also trying to motivate others.

          If you read my comment properly, I was trying to embrass you so that you go and focus on your work.XD

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

I am feeling that nowadays competiton is increased so much, not able to secure rank under 2k from past 3-4 contest.Contestant now even solving problem D like B, please tell me what do you think.

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

    i feel the same way, contestants are doing much better recently

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

    todays div2D<<usual div2D

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

I wonder how people solved C that easily :/ it was really hard for me

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

    Off-topic:suddenly notice , after a long time you change your profile picture..

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

      I wanted to put it after I reach expert but I guess that will take a long time .. I'm so disappointed about my performance

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

        don't worry brother..be continue your practice your desired day come quickly.Wished you Good luck <3

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    set answer, low , n to 0
    
    iterate the string
    if '+' n++, else n--
    if n < low, answer += string.position, low = n
    
    print answer + string.length
    

    i got WA and spent so many times to realize ans can't be store in int

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

      Thats were im wrong too but i changed the int to long long in the last 8 minutes of the contest

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

    I think with enough practice on this types of problems, it would become intuition. I used to find these types of problems really hard, and after solving and understanding them they become easy to solve.

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

How to even think about the problem E.

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

    Yeah man, the difference between D and E was huge today.

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

      Yeah true I was trying to apply digit dp for 1 hour in the contest .XD and than after the contest i saw that people did it with brute force ...facepalm.And so it became typeforces for most experts.

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

    My solution for problem E: https://codeforces.com/contest/1373/submission/85070127

    The key insight is that K<=9 so you can only overflow at most once. For example if you pick the last digit to be x%10=7 with K=5, then it must look like this:

    (front    ) 7
    (front    ) 8
    (front    ) 9
    (front + 1) 0
    (front + 1) 1
    (front + 1) 2

    So for every fixed starting digit and K, the sum of all digits is:

    sumOfOnesPlace + numNoOverflow * sumOfDigits(front) + numOverflow * sumOfDigits(front + 1) = N

    Where front is the variable we want to solve for and the rest are constant.

    If numOverflow is 0, you can solve for:

    sumOfDigits(front) = (N - sumOfOnesPlace) / numNoOverflow

    If front doesn't end in a 9, you also know that sumOfDigits(front) + 1 == sumOfDigits(front + 1), which again lets you solve for

    sumOfDigits(front) = (N - sumOfOnesPlace - numOverflow) / (numOverflow + numNoOverflow)

    Once you know a target for the sum of digits of front, you can greedy it.

    This isn't complete because I didn't cover all the cases, but I am guessing other cases are impossible via proof by AC. :)

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

    You can check out how to come up with the solution here :D

»
4 years ago, # |
  Vote: I like it -19 Vote: I do not like it

Did 0 based indexing ruined time in anyone's D?

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

    Yeah bro I also initially wrote code for 1 based indexing and after checking for test case 1 I felt something is wrong & and read the question again and realised that it is 0 based indexing

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

I had a hard time trying to crack C, can anyone please explain me their approach?

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

    void solve() { int n,i,j=-1; ll ans=0; string s; cin>>s;

    n=s.size();
    
    vector<int> pre(n,0);
    pre[0]=s[0]=='+'?1:-1;
    
    for(i=1;i<n;i++)
    {
        pre[i]=pre[i-1]+(s[i]=='+'?1:-1);
    }
    
    
    for(i=0;i<n;i++)
    {
        if(pre[i]==j)
        {
           ans+=i+1;
           j--;
        }
    }
    
    ans+=n;
    
    cout<<ans<<endl;
    

    }

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

How to solve E?

Thanks in advance

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

Test case 3 for E?

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

    Nevermind, figured it out:

    Sometimes it is optimal to put an 8 as the first digit after the 9s and 1s digit, rather than the remainder of the excess sum divided by 9.

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

How to solve problem D?

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

$$$O(1)$$$ solution for E.

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

    How did you generate those values?

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

      For $$$k = 0$$$ greedy algorithm. For other $$$k$$$ just check all $$$x$$$ from $$$0$$$ to $$$10^{9}$$$.

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

        That means you checked for all values in your laptop, really clever idea

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

          Yea. Precalc took ~$$$1$$$ minute.

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

            Wow, I couldn't find $$$ans(150, 1)$$$ for twice as long XD

            1e9 operations per second or what?

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

              You can iterate by $$$x$$$ from $$$0$$$ to $$$10^{9}$$$ with fixed $$$k$$$ and store the sum of digits of numbers. If this sum appears first time, you found the answer for this sum and our $$$k$$$.

              This huge brute forse is needed only for $$$k=1$$$, for other $$$k>1$$$ it is enough $$$10^{6}$$$ candidates.

              To speed up the whole brute force, you can do transition from $$$x$$$ to $$$x+1$$$ by $$$O(1)$$$ instead stupid $$$O(log(x))$$$.

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

                So, it's only 1 loop from $$$0$$$ to $$$10^9$$$, I get it. At first I thought you did that for all $$$k$$$, hence the question..

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

    How did you map all the values, did you get any online tool to calculate that ?

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

    How did you generate values?

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

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

    Is that allowed? Or would it be considered cheating

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

      I mean it isn't technically cheating, more of a hacky solution

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

        It is not cheating at all.

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

          Why do i hear your comment in petyr baelish voice in my mind XDXD

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

    Meanwhile setters: Am I a joke to you.

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

    FBI wants to know your location

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

    Codeforces be like :

    371.jpg

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

    Can you prove it?

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

How to solve E?

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

I ended up using Kadane's for both D and F; I feel like it made sense for D, but was there an alternate solution to F that I missed?

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

    Or prefix sums while maintaining min

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

      Isn't that exactly what Kadane's is?

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

        Yes same thing but i used different implementation as Kadane's requires max and current sum

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

    Can you help with some intuition on, how to solve F with kadane's ? Thanks

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

      So, not sure if it is correct, but this was the idea I had: if you consider the bipartite graph of households and connections (NOT cities and stations, i.e. the first sample has 9 households and 9 connections), and have an edge between a household and a connection if their city and station are adjacent, then the problem becomes finding whether or not this graph has a maximum matching equal to number of households.

      The problem is that this graph is way too big to construct (it can have 2e15 nodes), so you need to use some general arguments. First observation is that if there is any subset $$$S$$$ of households such that its neighbor set is smaller than $$$|S|$$$, then it is not possible. If all subsets $$$S$$$ of households have neighbor sets that are greater than or equal to $$$|S|$$$, then we claim that it is possible. I didn't prove this, but it sort of feels like the proof will be similar to Hall's Marriage Theorem if it is true. Someone can correct me if I am wrong about this.

      Now, we obviously cannot check all subsets. However, we notice that if we are trying to find a subset $$$S$$$ such that the size of the neighbor set is smaller than $$$|S|$$$, we will always be able to use all the households from some contiguous set of cities (why? go through the proof, it's a good exercise).

      So, we are trying to find some contiguous group of cities such that the sum of their households is less than the sum of corresponding network connections that cover those houses. I'll leave this as another exercise to make the connection to Kadane's. You have to do quite a few modifications to the algorithm.

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

        I will definitely try to use the hints and to solve this problem. Thanks

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

        How did you know it is guaranteed that the sum over all connections is equal to the sum over all households? I mean, the samples do match the argument but how were you so sure so as to proceed?

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

          Not sure I totally understand your question. The sum of all connections isn't necessarily equal to the sum of all the households; in test 3 on the sample case the sum of connections is greater than the sum of all households, and it is still not possible.

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

            Oh, I misread your comment earlier. I thought it was perfect matching you were talking about. Now it makes sense, thanks.

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

        Using you hint i tried to solve this with kadane's kind of approach, But its getting TLE on test — 9. Can you please help me figure out why is this getting TLE ? https://codeforces.com/contest/1373/submission/85147824

        Thanks in advance for the help.

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

          I fixed your solution by adding one nifty line at the beginning of main:

          85152881

          The idea is that cin is actually quite slow at reading in input, and this only really matters when you are reading in something on the order of ~1e6 elements. It's generally accepted practice to include this line at the beginning of main, or otherwise use scanf for all your reads. If you look at the top 5 people in the standings you'll see they did this.

          If you add this line, though, you should NOT use scanf/printf while also using cin/cout. Choose one and stick to it, because the addition of this line essentially allows these operations to occur asynchronously and it will totally mess up your program in certain instances.

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

            Thanks a ton for the help. I will remember this from now own.

            Feels so good to to see it getting accepted.

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

    my solution: i simply assigned all of the capacity of the i-th edge to the i-th node and greedily give the next node the cumulative excess capacity while paying attention to the capacity of the edge. i traversed through the graph twice since it is a cycle and checked for validity on the third pass. 2 passes might be enough but i was being safe and did not want to waste time on checking for correctness. in all honesty i am surprised this simple solution worked.

    edit: fst :(

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

What was test case 4 in problem D? ;-;

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

I almost took 90 min to solve A question. Soo confusing.

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

My brain: 30 minutes on A and 20 min on B+C -_-

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

did anybody get a flow solution to pass for F?

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

    I completely ignored flow because the limit was so large. Is it possible to pass?

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

      worst case runtime of Dinic is very bad, but it's very often misleading, since it can run wayyyy faster on certain types of graphs. On bipartite graphs, Dinic runs in O(sqrt(|V|)|E|) time in the worst case (edit: jk this is wrong, it still runs quick though), so I thought it was worth a shot. I think you can derive a solution by analyzing the augmenting paths of the graph.

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

        I know that when Dinic's algorithm is applied to bipartite matching, the time complexity reduces. Its called Hopcroft-Karp algorithm. However, I have no idea when it comes to just finding a maximum flow on bipartite graph, not matching. AFAIK, the major reason why such bound holds is because the capacities are unit, which is not the case for this problem.

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

          https://en.wikipedia.org/wiki/Dinic%27s_algorithm

          in bipartite matching, you have both unit capacity edges and a bipartite graph. each of those restrictions individually can speed up Dinic, since each allows you to find blocking flows very fast, which reduces the number of iterations you have to do on the graph.

          edit: oh i see what you mean, the runtime i posted above doesn't always apply. AFAIK it still is true that it runs fast on bipartite graphs though.

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

    Its memory limit gets exceeded anyways with Push Relabel (with gap heurestics). https://codeforces.com/contest/1373/submission/85062675 (Total 2 * n + 2 nodes are needed to model the problem into flow, with capacity taken in long long).

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

Is think explation in C and D can be useful in figuring Problems more easily.

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

How to solve D ? give some hints

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

For me today B < A and D < C.

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

    No way C is more difficult than D, unless you coded some weird solution.

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

    It took me more time to figure out correct solution for C than D.

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

    According to me b < c < a < d

    problem A just ruined my contest ;(

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

Always 'A' makes me so Panick...

Was staring at problems for 1hr 12 minutes. Zero solved! And then solved D->C->B->A. Honestly This was the difficulty for me. As soon as I saw D I got the solution.

»
4 years ago, # |
  Vote: I like it -50 Vote: I do not like it

F*uck int, F*uck integer overflow, int data type should be removed from C++, got AC on D just after the contest

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +26 Vote: I do not like it
    #define int long long
    
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      You better think before writte int or long long.

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

    But isn't 'overflow' in your name?

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

    I always use long long no matter whether it should be.

    Though long long is slower than int and some kinds of problems will return TLE when you use long long instead of int, but the timelimit on CF is far more loose, so I just use long long every time to avoid the integer overflow.

    BTW, I'm very sympathetic to you, I can understand your feeling because I had many times when some stupid mistakes blew my whole contest up just for dropping 50+ ratings.

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

    I have same feeling with you

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

    Also, I got WA in D because of int. Yes, data types can cause havoc.....

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

Was not able to solve C..any help?

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

How do you solve D? I came up with O(N*N) DP but it will TLE and I have no idea how to optimise. One observation I have is that there is no point in reversing a subarray of odd length as it'll yield the same sum. My DP solution was to go through all possible lengths of even subarrays and find the maximum value that can be obtained as sum at even positions upon reversing that subarray (which I do in squared time). Also, E seemed very interesting but apart from a few basic observations I found nothing. So, any suggestions on E are welcome too!

I found the problems very interesting, thanks for the round!

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

    The problem can easily be reduced to maximum subarray problem

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

    We can solve D simply by building (sum of odd indices — sum of even indices) for every prefix, and some simple calculations.

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

    Here is my dp solution to problem D which is very different from Kaden's algorithm.

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

Problem D was really cute.

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

    Can you share how you solved it?

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

      This is the link to my solution... First observation is that the array that you want to reverse has to have even length in order to get the elements swapped. And you can start considering that the initial array is the best..and then you can use kadane's algo for finding the best subarray to reverse. Reversing an even length array means in fact subtracting from the result the elements that were previously in the sum and adding the others.

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

        Can it be solved using two pointers ?? considering the largest even subarray such that the sum of elements at odd position is greater than sum of elements at even position and adding the remaining even sums at both ends ??

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

          I don't really know. Maybe it is possible. That was the only idea i had..and thankfully it worked

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

          I tried to implement the same idea during the contest but failed. If you find someone's code using this method, let me know.

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

      you can find a detailed explanation here in the video

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

How to solve F?

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

Toughest Most confusing A ever.

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

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

Why NlogN TLE'd on D?

After seeing the constraints, I assumed it should have passed.

Submission

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

    You mean why $$$O(n^2)$$$ TLE while $$$O(n)$$$ passes?

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

    Your solution isn't NlogN it is O(N^2) . Since number of even length subarrays is (N * (N + 1))/4 -> O(N^2)

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

      Can you explain why? I was thinking it is NlogN, so wasn't optimizing during contest.

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

        you have commented in your code that " so we can check every len of 2, 4, ... , n using tc = Nlog2N."

        it would have been Nlog2N if it was 2,4,8,16...N but here it is 2,4,6,8,10....N

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

How to solve D??

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

    check this. It's a link to my comment where i explained a little

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

    85011757

    Spoiler

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

    I solved D without kadane. My approach is that store prefix even -prefix odd in one vector and prefix odd indexed values -and prefix even indexed sum values in another vector. and then try reversing maximum difference of odd indexed -even indexed sum values sum even length subarray if the array ends at odd index and vice versa for subarrays ending at even index. Try thinking on building intuitions. My submission link is :- 85056177

    Hope I would be hacked!

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

    Check out the detailed explanation for it here, you can read more about Kadane's algorithm if you have further doubts :)

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

    You can check out my video editorial here

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

I stuck on c for one and a half hour because of forgetting using long long...

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

85052253 is ...weird. Who would if(a==165) that deliberately, if not for other accounts to hack?!

Also some of the other A problem Hacks too. Weird.

This one

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

    And for his first try on problem A he wrote (a==7) but it didn't work :D. I also accidentally reviewed these two solutions in hacks section and was confused :DD

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

    Guess it's the same person with two accounts

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

    Here's another one

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

Fuck it , I need a urgent editorial. Hell yaaa..

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

Could anyone please confirm, Shouldn't the verdict for this would have been Runtime Error signed integer overflow? Instead it gave Wrong Answer

https://codeforces.com/contest/1373/submission/85049895

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

Can someone point out the mistake in my submission for D? 85049220 I used maximum subarray approach. Don't know where its going wrong. Test case is too big to understand.

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

    Is it because you are casting ad to int32_t at the end?

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

      Mistakes like these are always remembered :( Just changed that part and Boom 85058120 Thanks a lot. Would have never figured that out. Also, a silly question, I use: define int long long int because of which I have to use int32_t and stuff. How do you use library functions then? Because when I use max with just ad, it says no matching function calls. So, how do I use (any)library functions on long long int variables?

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

        Just ensure that you typecast the other value to long long int as well.

        For example
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

when will the official analysis ?

»
4 years ago, # |
  Vote: I like it -10 Vote: I do not like it

vovuh I'm curious, was the following solution intended for E:

  1. If $$$k = 0$$$, greedy.

  2. If $$$k = 1$$$, notice some patterns, come up with a rule.

  3. If $$$1 < k <= 9$$$, write a brute force up to something on the order of 1e6 (possibly, with optimizations).

I also noticed many users did precalc (calculated all the answers offline). However, the vast majority did something totally different (idk what), so I wonder, whether the straightforward solution was intended or not. Thanks.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +103 Vote: I do not like it
    1. Iterate over the last (rightmost) digit
    2. Iterate over the number of 9s before it.
    3. Calculate the needed sum of left digits, check it to be non-negative and integer.
    4. Construct left part greedy to fit that sum.

    And find the minimum value among them. No special cases.

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

      Wow, that's totally elegant, thanks a lot!

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

      In your code, how did you know to insert an 8 in the middle when lft is greater than 8?

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

        I need to put as large digit as possible, but I can't put a 9 there since I fixed the number of 9s. So here comes an 8.

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

      As far as I can tell, you don't even need to iterate over the number of 9's

      If the rightmost digit would wrap around from 9 to 0 in your sequence, then the number of 9s before the last digit is always 0

      else the number of 9s is as large as possible

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

If someone want a poorly coded and inefficient DP solution for E : 85057205

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

Fucking D . Any solution? Waiting for help.

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

    Here's one solution — 1.Standard problem to be used. Maximum sum subarray of even size (you can google and first geeks link can help). 2. Observation : reversing an odd sized subarray is useless. Problem is reduced to find a subarray of even size, where sum of odd indices elements are more than even indexed elements . 3. Actual solution - sum all even indexed elements , call it sum_1 , multiply all even indexed value by -1. Find the maximum sum of even sized subarray in this modified array, call it sum_2 . Ans = sum_1 + sum_2

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

      thk you

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

      by the way thank you for aur sharing your approach . but can please explain why "multiply all even indexed value by -1" is done (how is it helpful??).

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

        If after this modification, there exists a even sized subarray with positive sum, that means of you reverse this array, you will get most benefited.

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

    Some Hints:

    Spoiler
    My Attempt
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think after see the solution you understood all.Just Using prefix count

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

Hello!
I am MrPupsik. Help me to solve problems pls.

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

Can anyone help me understand where my attempt to problem C goes wrong?
I think that this might be due to some overflow error, but i am unable to see where it occurs, as almost everything is long long.

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

    I guess that ans = ans+it-vc.begin()+1; causes pointer overflow which leads to undefined behavior? As changing the line to ans = it-vc.begin()+ans+1; (submission 85085422) or ans += it-vc.begin()+1; (submission 85085571) solve the issue.

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

What was the complexity of intended solution of F?

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

It's really annoy :(

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

My solution for the E:

If k = 0 we can build the number, we simply put the largest digit to the left whenever we can.

If K = 1 and n is an odd number, we simply put an 8 at the end of the number, so when putting it together it would be:

XXXXXX9

XXXXXX8

But if N <17 we can check with brute force.

If K = 1 and n is an even number, we simply put 89 at the end of the number, so when putting it together it would be:

XXXXX90

XXXXX89

But if N <26 we can check with brute force.

The last case is when we have k> = 2 in this case we can search for it with normal brute force, because at most it will have 6 digits

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

Did a semi brute-force solution for E and it worked. https://codeforces.com/contest/1373/submission/85047398. Precalculate the answer for all numbers that are I9JK, I99JK, I999JK etc.. Where I,J,K can be any digit and there is a bunch of 9s in between (0 up to 20). Then do lookups,

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

    At the first glance I read the last line as "Then do hookups".

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

I saw the tags for problem F, and I did not see the greedy tag. My solution is only based on a greedy approach. I do not know how to prove its correctness. If it is wrong, feel free to hack it.

The solution is here: https://codeforces.com/contest/1373/submission/85035196

PS: They added the greedy tag.

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

What's the reason, so one has accepted while other not?[submission:85006751][submission:84997771] (Thanks in advance)

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

    Solution is failing due to this line input=sys.stdin.readline At end of each testcase, readline will take newline character '\n' along with input, which gets accepted in else part of logic, increasing value of on. To correct this behaviour, strip the '\n' character at end
    st = st.rstrip('\n')

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

What was the name of website which kept track of all codeforces rounds and show us which questions were solved by us and which are left? It also kept track of rounds by there format. Eg:- Different categories for Educational,Div1,Div2,Global rounds. It tells us for this round we have solved A,B,C and left with D,E,F,G.

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

I really liked problem C as it tests your ability to read, understand and reason about a piece of pseudocode. Very useful practice and skill.

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

    Yes true. If I encounter such piece of code in the industry, I would never think to optimize it. Tried it out here just because I knew there was a solution

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

Can somebody explain me why n*log(n) F solution gets TLE? I think I'm missing something, as I would expect it to easily pass. Thanks

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

    sorry, n*log(b0), but question stays the same

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

    This is what you need: ios_base::sync_with_stdio(0);

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

      Indeed that was the case, now it passed. My main language is java, I only tried c++ because I was confused that I got TLE. That being said I'm not sure how to fix it in java (will try to google it, or if you know, please let me know).

      Explanation: city[n] can get connection only from station[n-1] and station[n] (don't forget about modulo — but that is clear). So if I provide X connections from station[0] to city[1] I need to provide remaining connections for city[1] (city[1] — X) from station[1]. If there isn't enough I need to increase starting X. If there is enough I can take remaining connection from station[1] (call it Y) and give it to city[2] and again get remaining connections for city[2] (city[2] — Y) from station[3] (if there isn't enough start with higher X).

      If I was able to do it for whole cycle I need to check if station[0] has enough free connections (station[0] — X) for remainder of city[n]. If yes it is solvable, if not I have to decrease starting X.

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

        Yes, nice solution, I did something quite different, for each subarray of cities, I checked whether it can be satisfied by the stations which enclose it. Solved it using sparse table

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

    Could you explain your solution?

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

Does there exist a testcase that (the ans)%100+k>99? I just iterate 0~99-k for the last two digits of ans

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

    I checked every possible n and k combination with my solution, and none of them have ans%100 + k > 99, so it doesn't look like it, but I don't have a reason as to why yet.

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

    sorry, i think its wrong

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

      Me too. But I can't find the testcase whose ans%100+k>99 or prove that it doesn't exist

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

        no, your solution is correct (but not sure for larger $$$n$$$), that comment is for my rev. 1

        i also use the same solution and just intuition, now i try to prove

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

i refreshed the page 3 times in problem C .. i thought it was a bug showing the editorial solution xD

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

When you click contests, you can't access it. Only an active contest is visible.

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

https://codeforces.com/contest/1373/submission/85001977 Could someone pls tell me why my code submission 85001977 for C can work perfectly for n=500(testcase4) but for testcase5 n=197, it shows TLE??? How can this happen. I implemented the same code they provided in the question, just a small change I brought was to make an array where I could store previous val of curr and the index where curr ended. And in then next iteration started at that index only, so effectively my code had complexity of O(n). Tell me if I'm wrong also how could that thing happen which I stated above.

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

    that would result in tle brother as the iteration for the string would repeat and would pass the time limit.

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

      No it wouldn't repeat. Only one iteration takes place. From 0 to no. of '-'s. I kept the record of last iteration and carried on from there for the next iteration. Had it been that case, why did my code didn't show TLE for n=500 but shows for n=197

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

    500 and 197 is number of testcases not the string.length

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

      yeah i got that later but I've tested.... and in fact sum of |s| wont go more than 10^6. My algo iterates over this only once. Why should it show TLE??

»
4 years ago, # |
Rev. 3   Vote: I like it -21 Vote: I do not like it

Enjoyed solving the problems :)

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

How the answer for the third test case ( problem E) is 4 . Why not 3?because starting from 3 till 9(3+4+5+....+9) gives me 42 .

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

Wrong ans in C for 2h because 'int' expect 'long long'=))))

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

What's the binary search solution for F? I think the possible amounts of connections that can be given to the first city by $$$b_1$$$ lie in a contiguous range, but I can't think of how to apply binary search to find any number in this range.

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

    Yes. It's possible to do so. You can binary search on how much of the connections from $$$b_1$$$ you assign to $$$a_2$$$. Basically you assign a potential number, and then perform greedy and see if it works.

    The greedy strategy is like this: If you assign $$$x$$$ connections to $$$a_2$$$, then you still need $$$y = \max(0, a_2 - x)$$$ connections from $$$b_2$$$ for $$$a_2$$$. That means you only have $$$y$$$ connections available from $$$b_2$$$ for $$$a_3$$$. Be greedy, so you assign all of those to $$$a_3$$$. Now you need additionally $$$a_3 - y$$$ connections from $$$b_3$$$, and so on...

    I think of it in a flow/pipes analogy. You just push as much water forward to the next one, which then can push more water forward, and so on. Or in the rope interpretation (see a few comments below) fixate on the of the rings and push the others as far as possible.

    Now let's think about the extremes. If you assign $$$0$$$ connections to $$$a_2$$$. Then you will probably be not enough, and at one point you will no be able to fill all required connections.

    The other extreme is exactly the opposite. If you assign all $$$b_1$$$ connections to $$$a_2$$$, then you will do a lot better connections. This is the best case for all the cities $$$a_2, a_3, \dots, a_n$$$ and you will satisfy their needs (unless of course it's not possible at all). The only problem that occurs is that you don't have enough connections remaining for $$$a_1$$$. You might end up with a demand for $$$z$$$ connections for $$$a_1$$$, and you don't have any connections left since you all assigned them all to $$$a_2$$$.

    Now if you assign $$$b_1 - 1$$$ connections from $$$b_1$$$ to $$$a_2$$$. What happens with the demand? It can get one higher, but it also can stay equal (if some of the pushed connections we assigned greedily are unused). Which means in that case we are better, since we still have one unused connection remaining. If we assign less and less connections to $$$a_2$$$, the difference between the demand and the unused connections will shrink, until it is zero (in that case we have found a solution), or until we gone to far and we can't fulfill and demands of the middle cities any more.

    To summarize: if remaining demand for $$$a_1$$$ can't be satisfied with the unassigned connections of $$$b_1$$$, we have assigned too many connections to $$$a_2$$$. Or if the assignment breaks somewhere and some of the other cities miss some connections, we have assigned (pushed) to few connections. Using these rules you can perform a binary search.

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

      Now that I think about it, there is no need for binary search at all.

      First assign all $$$b_1$$$ connections to $$$a_2$$$, and push as much as possible. This leaves the demand $$$z$$$ for $$$a_1$$$.

      Now assign $$$b_1 - z$$$ connections from $$$b_1$$$ to $$$a_2$$$, and push again greedily. This one will be a solution if it exists.

      Solution: 85077333

      • »
        »
        »