Автор awoo, история, 4 года назад, По-русски

Привет, Codeforces!

В 25.06.2020 17:35 (Московское время) состоится Educational Codeforces Round 90 (рейтинговый для Див. 2).

Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.

Этот раунд будет рейтинговым для участников с рейтингом менее 2100. Соревнование будет проводиться по немного расширенным правилам ICPC. Штраф за каждую неверную посылку до посылки, являющейся полным решением, равен 10 минутам. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.

Вам будет предложено 6 или 7 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.

Задачи вместе со мной придумывали и готовили Роман Roms Глазов, Адилбек adedalic Далабаев, Владимир vovuh Петров, Иван BledDest Андросов и Максим Neon Мещеряков. Также большое спасибо Михаилу MikeMirzayanov Мирзаянову за системы Polygon и Codeforces.

Удачи в раунде! Успешных решений!

Поздравляем победителей:

Место Участник Задач решено Штраф
1 Geothermal 7 130
2 ksun48 7 143
3 300iq 7 147
4 vepifanov 7 168
5 Radewoosh 7 175

Поздравляем лучших взломщиков:

Место Участник Число взломов
1 EduPeres 40
2 Grey_Matter 39:-3
3 lx430621 26:-1
4 killa_vanilla 25:-5
5 checkingagain 17:-1
Было сделано 351 успешных и 375 неудачных взломов.

И, наконец, поздравляем людей, отправивших первое полное решение по задаче:

Задача Участник Штраф
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: Разбор опубликован

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

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

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

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

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

I have a question about educational rounds. tell me if I'm true: I think in the educational rounds people get scores due to the number of problems solved + penalties. and it does not matter which problem(A or F) you solve and people are only scored bye the number of problems solved. am I right?

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

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 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

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

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

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

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

        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 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 года назад, # ^ |
        Проголосовать: нравится -8 Проголосовать: не нравится

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

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +10 Проголосовать: не нравится
        **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 года назад, # |
  Проголосовать: нравится +385 Проголосовать: не нравится

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

CF4

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

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 года назад, # |
  Проголосовать: нравится +604 Проголосовать: не нравится

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

:D

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

Pretty excited for this contest !!

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

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

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

cf5

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

hope to get a decent rank this time

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

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 года назад, # |
Rev. 3   Проголосовать: нравится +57 Проголосовать: не нравится

When I find People Cheating in Rated Rounds

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

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

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

Excited for vovuh div2 round after a long time.

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

Good luck everyone

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

IMG-20200625-165915

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

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

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

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

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

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

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

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

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

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

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

Nobody:

Problem A in every Educational Round ever:

  • 1 < t < 1000

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

Seriously?

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

Again B is easy than A -_-

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

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

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

      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 года назад, # ^ |
          Проголосовать: нравится +9 Проголосовать: не нравится

        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 года назад, # ^ |
        Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

        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 года назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    idea was simple but problem statement could have been worded better

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

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

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

(

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

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 года назад, # |
Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

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

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

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

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

      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 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    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 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

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

    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 года назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

How to even think about the problem E.

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

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

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

      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 года назад, # ^ |
    Rev. 4   Проголосовать: нравится +6 Проголосовать: не нравится

    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 года назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

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

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

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

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

    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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

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

How to solve E?

Thanks in advance

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

Test case 3 for E?

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

    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 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

How to solve problem D?

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

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

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

How to solve E?

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

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 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Or prefix sums while maintaining min

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

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

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

      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 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

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

        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 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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 года назад, # ^ |
              Проголосовать: нравится +8 Проголосовать: не нравится

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

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

        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 года назад, # ^ |
          Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

          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 года назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

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

            Feels so good to to see it getting accepted.

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

    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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

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

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

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

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

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

did anybody get a flow solution to pass for F?

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

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

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

      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 года назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

        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 года назад, # ^ |
          Rev. 2   Проголосовать: нравится -10 Проголосовать: не нравится

          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 года назад, # ^ |
    Rev. 3   Проголосовать: нравится +15 Проголосовать: не нравится

    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 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

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

How to solve D ? give some hints

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

For me today B < A and D < C.

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

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 года назад, # |
  Проголосовать: нравится -50 Проголосовать: не нравится

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

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

    But isn't 'overflow' in your name?

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

    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 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I have same feeling with you

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

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

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

Was not able to solve C..any help?

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

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 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Problem D was really cute.

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

    Can you share how you solved it?

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

      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 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

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

          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 года назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      you can find a detailed explanation here in the video

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

How to solve F?

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

Toughest Most confusing A ever.

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

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

Why NlogN TLE'd on D?

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

Submission

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

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

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

    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 года назад, # ^ |
        Проголосовать: нравится -18 Проголосовать: не нравится

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

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

        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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve D??

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

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

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

    85011757

    Spoiler

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

    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 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

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

    You can check out my video editorial here

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

Индусы: делают ответами на задачи сложно читаемые ники
vovuh:

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

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

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

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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

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

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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

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

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

      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 года назад, # ^ |
        Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

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

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

when will the official analysis ?

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

Is there anyone who feels B was easy than A?

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

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 года назад, # ^ |
      Проголосовать: нравится +103 Проголосовать: не нравится
    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 года назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

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

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

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

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

      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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

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

Fucking D . Any solution? Waiting for help.

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

    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 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      thk you

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

      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 года назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится

        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 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Some Hints:

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

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

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

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

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

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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What was the complexity of intended solution of F?

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

It's really annoy :(

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

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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 года назад, # |
Rev. 3   Проголосовать: нравится +17 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

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

    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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Here's a simple logic for D:

Notice that, if you reverse an odd-sized subarray the relative order of even and odd doesn't change. What I mean is number's which were in odd position will remain in odd position, and even position will also remain the same. So we have to reverse a subarray with even size. Now make all elements negative which were in even positions. When we reverse an even-sized subarray the odd and even position's number will interchange their place. So any subarray sum with even size will give the difference between odd numbers and even numbers. This is the extra value which we can add to our original array's answer if we reverse this particular subarray. So we have to find an even-sized subarray which has maximum sum, and add that to our original array's answer.

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

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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Does there exist a testcase that ans%10+k>99? I just iterate 0-99-k for the last two digit in ans

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

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 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

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

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

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

      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 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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 года назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    Could you explain your solution?

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

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 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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 года назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    sorry, i think its wrong

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

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

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

        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 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

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

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

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

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 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

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

      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 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

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

      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 года назад, # |
Rev. 3   Проголосовать: нравится -21 Проголосовать: не нравится

Enjoyed solving the problems :)

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

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 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

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

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 года назад, # ^ |
      Проголосовать: нравится +31 Проголосовать: не нравится

    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 года назад, # ^ |
      Rev. 3   Проголосовать: нравится +24 Проголосовать: не нравится

      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

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

      Thanks!

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

What is the correct solution for A. Many people are getting A hacked.

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

.

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

I have a physical proof of problem F at https://codeforces.com/topic/79862/

Let us consider a circle segmented to n arcs with n nodes N1, N2, ... Nn. the length between Ni ans Ni+1 is ai(the number of households in the i-th city.) and there is a small ring in arc_i, note as Ci. there is a rope with origin length bi between Ci and Ci+1. the rope can be stretched if neccesary.

Now if we can arrange all the rings so that no rope need to be stretched, there is a solution.

We just let all rings move freely. if no rope are stretched, it is ok. If some ropes are streched. there are 2 conditions:

a. all ropes are streched, it is condition 1; b. some continues ropes are streched, while the rope before and after them are not. In this case, the start and end ring of these ropes must be at the node. so it is condition 2.

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

Video Editorial For Problem — D . Hope you like it.

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

In problem D, I multiplied the numbers at even positions by -1 and found the sub array of even length whose sum is largest.Since this will give me the difference between the original sum of elements at even positions and max sum at even positions after reversing,I'll just add the difference to the original sum. But somehow i got WA at tc 3. Can anyone please help me find why it didn't work? I'll really appreciate it. Here is the link to my solution : https://codeforces.com/contest/1373/submission/85045234

PS: It isn't kadane, it's just the name of the functions and was too lazy to change it again.

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

    Maybe because in your function kadane your array dp is int and also the answer is int, but it can be long long (around $$$10^{14}$$$), and so it overflows?

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

      Wow thanks brother,it worked. I don't know why i didn't think of that during the contest.

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

I would like to bring to notice these 2 users who wrote solutions so that their code can be hacked. Please ban these accounts; who create new ids just to disturb the competitive spirit in code forces rounds issafake and orkunisitmak

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

Well I solved D in a different way, I have used dynamic programming ,first we know that only reversing the order of the l,rth border matters where l(mod 2)!=r(mod 2).

Next wherever this is the case we see that the odd positions interchange with the even position upon reversing. That means there is a net change of value of sum of elements in odd indexes — sum of elements of even indexes.

That means we need to find the maximum such value where all elements in range of l,r. To this extent let dp[i] denote the max such value where the right border is the ith index.Now transitions are as follows

if(i%2==0)

dp[i]=max(dp[i-2]+a[i-1]-a[i],0);

else

dp[i]=max(dp[i-2]+a[i]-a[i-1],0);

as a[i] is on odd index in this case, and we need to find the value of sum of elements in odd indexes — sum of elements of even indexes.

finally the answer is max of all dp[i]+ the sum of numbers previously on even indices from 1->n.

q.e.d

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

    Fun fact- Kadane’s algorithm counts as dynamic programming as well!

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

How long before the editorial drops?

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

Solutions to A-F are available at the end of my screencast of the round for people who are interested.

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

Educational round without editorial, how ironic! We need editorial!!

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

Is there a correct greedy solution for F? Without binsearch

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

My solutions for problems A-E.

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

I failed to finish E during the contest, but if anyone's interested, here is a non-bruteforce solution I was working on, the version I tried to make during the contest actually failed only on two test cases in the entire input space lol.

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

Hey please can someone help me out by explaining how to solve E.

Also , are Educational Rounds harder than usual ones ?

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

    I explain it at 2:11:35 here

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

    https://codeforces.com/blog/entry/79277?#comment-650107 I found this easy to understand and easy to implement.

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

    It is possible to precompute the solution for all possible n and k in a separate file and then paste the entire array into your solution and read the answers from it for each test case like this: https://codeforces.com/contest/1373/submission/85074779

    For k = 0, you can use greedy to precompute the answers.

    For fixed k >= 1, it suffices to check x from 0 to 1e9.

    The reason you only need to check x from 0 to at least 1e9 for k >= 1 is because when k = 1 you can use x = 999,999,998 to get a total digit sum of 80 + 81 = 161 > 150 = maxN, and when k > 1 you can achieve an even larger maximum sum. So by checking all x up to 1e9 you can achieve n up to 161, which is enough. I guess it can be proven that you also wont miss any n by not going above 1e9.

    The values of digitSum(x) from x = 0 to 1e9 can be stored in a vector and can be computed in linear time using a simple recurrence relation. To efficiently answer sum queries (f(x) + .. + f(x + k)) you can turn the vector into the vector of its prefix sums.

    In the end, the dp array can be calculated in O(9 * 1e9) time, which takes 10 seconds on my laptop.

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

    The non-bruteforce solution sketch is as follows.

    1. Let's express $$$f(x + 1)$$$ in terms of $$$f(x)$$$: $$$f(x + 1) = f(x) + 1 - 9g(x)$$$ where $$$g(x)$$$ is the number of tail nines in $$$x$$$.
    2. Because $$$k < 10$$$ the set $$$(g(x), g(x + 1), ..., g(x + k))$$$ will contain at most one non-zero item.
    3. Based on these two observations, we can express the sum $$$f(x) + f(x + 1) ... + f(x + k)$$$ as $$$f(x) \times (k + 1) + \sum_{i=0}^k i - 9p$$$ for some non-negative $$$p$$$, and that must be equal to $$$n$$$.
    4. We can rewrite that as $$$f(x) \times (k + 1) = n - \sum_{i=0}^k i + 9p$$$ and find values of $$$p$$$ for which $$$k + 1$$$ divides $$$n - \sum_{i = 0}^k + 9p$$$. From that, we get our candidate $$$f(x)$$$ values, too.
    5. Now $$$p$$$ defines which tail digits we can use. If $$$p = 0$$$, we can use any such digit up to $$$9 - (k - p)$$$. If $$$p \ne 0$$$, we can only use $$$9 - (k - p)$$$. However, this is further limited by $$$f(x)$$$, we can't take a digit that is already greater than $$$f(x)$$$.
    6. After that we just greedily add more digits to the number with one additional thing in mind: this construction requires that $$$g(x + (k - p)) = 1$$$, so we can't have a nine in the second position.
    7. We print $$$-1$$$ when there is no suitable $$$p < k$$$.

    The code is here.

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

Solution to F

For Each network station, at index i
    Fill its left city (city at index i) as much as possible
    If there is still capacity left, fill its right city ( city at index (i + 1) mod n) as much as possible
    
For Each House at index i: 
    fill the house to full using its left station (index (i - 1) mod n) 
        (if unable to make it full now, there is no solution)
    replace as much flow as possible from its right station (index i) with flow from its left station

There is a solution iff all the cities are full at this point

Submission link: 85057681

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

A well coded O(n*sqrt(n)*log(n)) solution could get AC on G?

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

Solution for G using max prefix sum segment tree:

First, note that for each pawn $$$i$$$ we can easily calculate the minimum row $$$r_i$$$ it has to get to. Then, let's pretend that we can place pawns on top of each other, and the question then becomes "how many rows must be added to the board so that all pawns are on the $$$k$$$'th column and no two pawns are on top of each other?" If a pawn can reach $$$(k, r)$$$, it can reach $$$(k, r')$$$ for all $$$r' > r$$$. Thus, it is only of interest to us what the earliest row each of our current pawns can get to is, and then we will simply propagate them all forward until no two are on top of each other.

I think it's easier to think of the new problem in terms of arrays: We can imagine the special column as a vector of length $$$n$$$ containing all $$$0$$$'s. Each time a pawn gets added, we add a $$$1$$$ to the index of the earliest row it can get to (where we add new indices if needed, never going over 2n indices). Now, given some array, how do we tell whether we need to add more rows? Playing around with it a little, if we assume our array is either of length $$$n$$$ or has no trailing 0's (i.e. the last entry is nonzero), then we need to add new rows to our array if there is some suffix sum that exceeds the number of elements contained in the suffix. For example, if $$$n=4$$$, the array $$$[0, 0, 2, 0]$$$ is fine but the array $$$[0, 2, 2, 0]$$$ is not since the suffix $$$[2, 2, 0]$$$ has sum 4, which is greater than the number of elements it has (3). The number of rows we need to add is actually exactly the number that the sum exceeds the number of elements by.

If we reverse the array and look at 1-indexed prefixes instead, then we are essentially looking for any $$$p_i > i$$$. This is identical to looking for $$$p_i-i > 0$$$, so we can actually initialize our array to be -1's rather than 0's and now our problem becomes looking for any $$$p_i > 0$$$! If we can find the maximum $$$p_i$$$ with our segment tree above, then this becomes an easy query.

Now, all we need to do is keep track of the maximum $$$r_i$$$ of all pawns currently on the board to keep track of where our prefixes should start from.

There is also apparently a solution that uses RMQ and lazy segtree, but not sure what the idea is. Anyone care to share?

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

    My solution for G: (I could not AC within contest, ACd after that)

    Every point has a time range when it is active. We load this into a segment tree, and then traverse the segment tree. That way we can simulate adding points for ever query. We need another aditional DS, where we can do Arr[index]++ where we add a +1 to index. We will only add +1 to a previously 0 location, so we also need to have a binsrch thing to find the first 0 position(note that when we go return from a node, we need to do Arr[index]-- as well). Complexity is mlog^2n though.

    click

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

    There is also apparently a solution that uses RMQ and lazy segtree

    I think this is what you are looking for https://youtu.be/Nuym8ejFH_w

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

Where is editorial :/

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

After 6 failed attempts, I am still unable to figure out, why is code for Problem C failing? Can anybody help me. Please!! Here is a link to my submission

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    I think there is some problem with your logic. I am explaining my logic, just crosscheck.
    Basically the terminating condition for the outer loop is not getting negative current, so the number of times the outer loop will run =  (minimum prefix sum (taking '+' as +1 and '-' as -1) + 1).
    The terminating condition for inner loop for each cur = i is prefix sum = (-i-1), because then the cur will go negative .
      So,
      let minimum prefix sum = s
      and index[i] represents the first index where prefix sum becomes -i;
      and ans = 0
      then we can compute the ans as:-
      for(i = 1 ; i <= (-1*s) ; i++) // number of times the outer loop will run
       {
       ans += (sum[index]+1) // number of times the inner loop will run
       }
    also since the terminating condition for the outer loop is not getting negative value of cur, therefore it will run for one more time and this time the inner loop will run completely, therefore we will have to add n(length of string) to ans.
    
»
4 года назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится

common man , still no editorial , do they prepare it after the contest ?

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

Video solutions for A,B,C,D,E....Hope you will like it!!!

Problem A

Problem B

Problem C

Problem D

Problem E

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

Hey, is there any official editorial for this contest?

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

If I uphack some solutions after the open hacking phase, but before systest, will the hacked solutions fail in systest?

upd: Yes they fails

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

    They do fail, but not necessarily by your hack, at least in this Submission it failed systests on test 48 which is not your uphack. So I am not sure that uphacks after the open hacking phase are incorporated to the systests at the end of the contest.

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

After wasting so much time on C, I found that I was using int instead of long long int. Now i solved C and D both. Hope I could solve it during the contest only.

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

i get wa on A and D only for not using long long

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

come on why I can't write more than 1e9 in first problem. :(

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

Does anyone explain why it works? it's my code... but idk why it works.... problem F 85046506

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

For the first time, I'm finally able to solve C problem in a contest XD

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

I like to read cf comments more than FB memes.

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

    Seems like Codeforces Watcher application can help you with this time spending.

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

I can't find the editorial for this contest, Is it just me or everyone?

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

I am a newbie. I solved 3 questions. Still, I got +82. Don't know how the rating works.

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

    Rating changes depend on your rank,not how many questions solved.when the questions are tough,even solving even a few can drastically increase ratings.

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

Anyone tried to solve D using dp approach? I need some idea about it.

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

Why they make A so lengthy?

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

When will the editorial be out ?

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

still no editorial...

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

Yet Another question similar to D

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

Why does editorials always take so much time in Educational Rounds?

I think it should be part of contest preparation so that the editorial is ready before the contest ends.

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

I think they forgot to publish the editorial ..it's so much annoying..

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

Where is the Editorial for this Round??

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

Where is the editorial for this round

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

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

Hola community, ~~~~~

Your code here...

I was developing a software and ran into error, help is highly appreciated .. please reply fast vector<vector<pair<int,int>>> Cluster; for(auto cluster : Cluster){ vector<pair<int,int>> left_data_logins, right_data_logins; for(auto login : cluster){ if(value<mean_of_all_values) left_data_logins.push_back(login); }}

~~~~~ executing the above peice of code is giving SIGSEV error, i do not know if data_types are not compatible . please help!!

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

Why did you change tests after the contest and I've got WA? That's unfair... Is not better to do strong tests?

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

    This is called hacking. Tests didn't change but more tests were added before final testing phase.

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

    In contest time ,any solution judge by few test case to avoid long queue..And After contest always judge that solution by more extra test case. It's the rule.Not unfair at all.

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

Are the problem setters waiting for the corona vaccine to post the editorials?

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

I received a notification that "Your solution 84984892 for the problem 1373A significantly coincides with solutions izhang05/84984892, diegorestrepo68/84988994". I did not share my code with anyone and I did not use any online IDEs such as ideone.com. Given that this is a simple problem that only requires a few lines of code, it's not surprising that there may be multiple submissions that are similar. There's a limited number of possible solutions and implementations for this problem.

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

    I suggest you to use own template to avoid this type of coincides.

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

      I didn't use any templates. This was my code:

      include <bits/stdc++.h>

      using namespace std;

      int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int t; cin >> t; while (t--) { long long a, b, c; cin >> a >> b >> c; if (a < c) { cout << 1 << " "; } else { cout << -1 << " "; } if (c < b * a) { cout << b << "\n"; } else { cout << -1 << "\n"; } } return 0; }

      There are only so many ways to express "a < c" and "c < b * a".

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

        i see both two code..i understood you are not cheater..but system are not human being, they just check code matched or not..so suggest you to use own template..Then so much change happens always from other code.

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

why is the editorial released so late in educational rounds?

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

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).

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

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).