Теперь раздел EDU доступен и на английском языке ×

Автор pikmike, история, 10 дней назад, По-русски,

Привет, 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 Андросов и Максим Ne0n25 Мещеряков. Также большое спасибо Михаилу 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: Разбор опубликован

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

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

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

oh! Vovuh back!!

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

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

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

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

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

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

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

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

      Yes.I thought that too

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

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

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

codeforces is the best

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

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

CF4

»
10 дней назад, # |
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?

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

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

:D

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

Pretty excited for this contest !!

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

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

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

cf5

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

hope to get a decent rank this time

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

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

When I find People Cheating in Rated Rounds

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

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

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

Excited for vovuh div2 round after a long time.

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

Good luck everyone

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

IMG-20200625-165915

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

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

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

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

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

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

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

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

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

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

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

Nobody:

Problem A in every Educational Round ever:

  • 1 < t < 1000

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

Seriously?

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

Again B is easy than A -_-

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

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

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

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

      • »
        »
        »
        »
        9 дней назад, # ^ |
        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!

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

    idea was simple but problem statement could have been worded better

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

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

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

(

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

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

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

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

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

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

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

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

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

    I'd be much obliged if you could share the solution logic of C here.

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

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

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

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

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

How to even think about the problem E.

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

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

    • »
      »
      »
      9 дней назад, # ^ |
      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.

  • »
    »
    9 дней назад, # ^ |
    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. :)

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

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

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

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

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

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

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

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

    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;
    

    }

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

    Lets take an example

    --++----+--

    Assume after each '+' sign good sequence start (good sequence = +++--- or +- or ++-- i.e. +++....---...)

    Break it in good and bad sequence(continuous '-' without + before)

    For above example you can break it like [-- (++--) -- (+-) -] (where inside () its good sequence.)

    Suppose good sequence A = (++--) {- sign after that is 3 excluding in good sequence}. good sequence B = (+-) negative sign after B i.e 1

    After analysing it you will see we are incrementing bad sequence 1 by 1 and iterating good sequence in one go.

    so ans due to bad sequence = (n (n + 1) / 2) {i.e 1 + 2 + 3...} = 15 (as n = 5)

    ans due to good sequence = good sequence length * no of '-' after that i.e. ans due to A good subsequence = (4(length of A) * 3(no of '-')) = 12

    ans due to B good subsequence =. (2 * 1) = 2

    Overall ans = (15 + 12 + 2) + (length of string) {because we will iterate our string fully once just before breaking out of infinite while loop}

    = 15 + 12 + 2 + 11 = 40

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

How to solve E?

Thanks in advance

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

Test case 3 for E?

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

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

How to solve problem D?

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

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

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

How to solve E?

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

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

    Or prefix sums while maintaining min

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

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

    • »
      »
      »
      9 дней назад, # ^ |
      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.

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

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

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

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

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

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

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

        • »
          »
          »
          »
          »
          8 дней назад, # ^ |
          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.

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

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

            Feels so good to to see it getting accepted.

  • »
    »
    9 дней назад, # ^ |
    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 :(

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

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

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

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

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

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

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

did anybody get a flow solution to pass for F?

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

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

    • »
      »
      »
      9 дней назад, # ^ |
      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.

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

        • »
          »
          »
          »
          »
          9 дней назад, # ^ |
          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.

  • »
    »
    9 дней назад, # ^ |
    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).

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

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

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

How to solve D ? give some hints

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

For me today B < A and D < C.

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

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

.

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

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

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

    But isn't 'overflow' in your name?

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

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

    I have same feeling with you

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

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

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

Was not able to solve C..any help?

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

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

    The problem can easily be reduced to maximum subarray problem

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

      Crap, yes.... I feel really stupid now. I solved this in squared time and didn't recognise the similarity smh... Thanks!

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

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

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

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

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

Problem D was really cute.

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

    Can you share how you solved it?

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

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

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

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

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

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

      you can find a detailed explanation here in the video

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

How to solve F?

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

I was not knowing that in Educational round, there is no point system. So I skipped A and solved B, C, D. I got a rank below 6500.:(

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

Toughest Most confusing A ever.

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

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

Why NlogN TLE'd on D?

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

Submission

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

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

  • »
    »
    9 дней назад, # ^ |
    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)

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

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

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

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

How to solve D??

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

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

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

    85011757

    Спойлер

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

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

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

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

    You can check out my video editorial here

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

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

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

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

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

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

Today I couldn't solve any of the question, even after trying so hard

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

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

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

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

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

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

    • »
      »
      »
      9 дней назад, # ^ |
      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?

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

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

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

when will the official analysis ?

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

Is there anyone who feels B was easy than A?

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

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

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

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

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

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

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

        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.

        • »
          »
          »
          »