Автор Vovuh, история, 3 месяца назад, По-русски,

Привет, Codeforces!

13 января в 16:05 по Москве начнётся Educational Codeforces Round 36.

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

Этот раунд (уже по традиции) будет рейтинговым для Div. 2. Соревнование будет проводиться по немного расширенным правилам ACM ICPC. После окончания раунда будет период времени длительностью в один день, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.

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

Задачи вместе со мной готовили Михаил PikMike Пикляев, Иван BledDest Андросов и Сергей sslotin Слотин.

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

У меня также есть сообщение от наших партнёров, Harbour.Space University:

As we get ready to dive into the second week of the year, we want to update you all on the upcoming Hello India x Russia Programming Bootcamp! So far 25 teams have registered, with more signing up daily.

As a reminder, the boot camp will take place from March 22nd to March 30th, 2018, at the Amrita School of Engineering campus, India. The Coordinator of the Programming Committee, and head coach will be two time ACM-ICPC world vice-champion Gleb GlebsHP Evstropov.

You can find more information and registration, click here

For those of you who need financial support for the boot camp, please fill up the register form, then we will contact you and prepare an official sponsorship request letter for you to present to your University, University’s IT partners or your potential employer.

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

Rank Competitor Problems Solved Penalty
1 JustasK 7 265
2 uwi 7 275
3 KrK 7 277
4 LHiC 7 284
5 latte0119 7 331

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

Rank Competitor Hack Count
1 halyavin 725:-45
2 zscoder 34:-10
3 M3hran 28:-3
4 OlegZubkov 28:-3
5 neelbhallabos 21

Было сделано 2023 успешных и 1300 неудачных взломов.

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

Problem Competitor Penalty
A Dalgerok 0:00
B Rafbill 0:03
C yashar_sb_sb 0:11
D eddy1021 0:25
E bmerry 0:11
F SmsS4 0:15
G MrDindows 0:19

UPD Разбор

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

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

This round will be (traditionally now) rated for Div. 2

Does this Mean that all "Educational Rounds" will be rated for Div.2?

»
3 месяца назад, # |
  Проголосовать: нравится -55 Проголосовать: не нравится

i wish everyone ratings equal to my contribution :)

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

Does this educational focus on classical problems like a good portion of the previous ones, or should I be expecting a regular round?

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

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

    69 hahahahahaha get it its 69!!!!!!!!!! HAHAHAHAHAHAHA :))))))))))))))))))))))))))))))))))))))))))))))))))))))) 6 9 6 9 6 9 soooo funynnnyyyy :)))))))))))))))))))))))))))))))))))))))))

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

    Timelimit for all questions is very tight!

»
3 месяца назад, # |
  Проголосовать: нравится -15 Проголосовать: не нравится

"Thanks Mike" is compulsory!!!!!!!

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

where are polygons???

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

почему индийцы и китайцы переводят этот комментарий, я не знаю

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

Good luck to everyone :)

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

GL & HF!

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

pikmike's and vovuh's rating graphs are very inspiring.

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

Напомните, пожалуйста: тест, взломавший некоторое решение, будет ли пробоваться на всех остальных решениях системой после окончания фазы взломов?

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

    На образовательных раундах мы почти всегда добавляем все тесты из взломов, которые кого-то взломали. Исключение — если таких тестов совсем уж много, но это случается крайне редко.

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

Will you (as a prize) tach the 1st place's spagett? or let them tach yours

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

since when GlebsHP is two time world champion?

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

Iasy round. I wil up my rating. Gud lak to me!

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

shit, solved D but B and C too hard for me(((

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

Timelimit for E is very tight!

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

After the contest ends:

Where is that test #6?

UPD: It is Educational Round so how can we know test #6?

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

Is the intended solution for E a Segment Tree? I am getting Runtime Error on test 18 with mine (Although I'm very close to the time limit too sooo).

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

    Implicit segment tree can do work. But I couldn't find my bug.

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

      Is implicit segment tree a segment tree when you create nodes only when you need them? If so, I did that but couldn't fit it in.

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

        use struct and pointer

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

          if you are creating new nodes in heap try to create it in stack instead

          Node d[15000009]; int curr; // ID of last node I created
          if (root->left  == NULL) ++curr, root->left  = d+curr; // try this
          if (root->left == NULL) root->left = new Node();// instead of this
          

          my first solution I created new nodes in heap and got TLE in test 18, and then after some optimization got MLE in test 32 :D now after creating new nodes in stack instead it finally gives AC.

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

    my seg tree O(Q * log2(N)) solution got TLE, time limit is very tight

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

    I did segtree with coordinate compressing, got TL16

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

    I solved it using just a set (of segments), each time, I erase the segments which are totally inside the new one and cut the ones that intersect and are not totally inside (at most two).

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

      what's the complexity? Especially the part of " I erase the segments which are totally inside the new one" ?

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

        Each query increases the number of segments at most by two, so there are only O(Q) segments. Since each segment can get erased at most once, the total complexity of "erase the segments which are totally inside the new one" over all the queries is O(Q log(Q)), final complexity is also O(Q log(Q)). I'm a bit dizzy today so I might be doing something wrong.

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

      if you don't mind can you please explain how to implement this?

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

Idea for D ?

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

    Is mine correct, please someone check:

    Find any cycle. For each edges in this cycle, delete it and check is condition is true or not.

    (I didn't write it during contest so I'm not sure it works or not)

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

      I tried this and got TLE multiple times

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

        Seems TL is tight, just add pragmas and optimizations to your code and send it again. I'm not sure either.

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

          Can you show me your pragmas?

          • »
            »
            »
            »
            »
            »
            3 месяца назад, # ^ |
            Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится
            #pragma comment(linker, "/stack:200000000")
            #pragma GCC optimize("Ofast")
            #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
            
            #define _CRT_SECURE_NO_WARNINGS
            
            • »
              »
              »
              »
              »
              »
              »
              3 месяца назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              thx

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

              For those who know, this might sound dumb so pls bear with it -: What are pragmas? What do above #pragmas statements do?

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

                I don't know too

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

                xD I don't know most of them also :P

                But this guy turns on "Ofast" optimization which makes your loops faster and does some of them without traversing entire loop like: for(long long i = 1; i <= (long long)1e15; i++) res++;. Try this with this line and it will find answer immediately.

                #pragma GCC optimize("Ofast")
                
      • »
        »
        »
        »
        3 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        I sent your code with pragmas and it got TLE again, TL complexity of algorithm seems correct, but.. I don't know

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

        I tried same idea and passed, but I forgot to erase elements from stack (So I got hacked :'( ). But it should work.

        Code

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

      Won't the complexity be O(m2) then ?

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

    I think we'd have to find the strongly connected components and check if there is more than 1 component with >1 vertices in it.

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

      There can be only one scc but a clique.

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

      This doesn't work with sample tests.

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

        Yes another check needs to be done within the scc. Maybe you can check if all the vertices inside the scc have only a single common edge or not.

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

      I did that. There are two cases: 1) if there is a pair a->b and b->a then we need to remove one of them, so just check both cases. Otherwise 2) there must be just one SCC with >1 vertices, and if we consider a graph with just the SCC nodes, each node must have exactly one in-edge and one out-edge (so it's just a big cycle). This passed pretests but I'm not sure if it's correct. Also, it works in O(N+M) :D

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

        You can have one cycle with one additional edge but still you can remove cycle with only one edge.

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

          Only if the additional edge will be between two adjacent nodes in the cycle, and that will fall under case 1).

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

            Just edge with same direction as cycle. Jump over 4 vertices.

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

    For each cycle that you find, increase the number of cycles for each edge in it. Chech if there are any cycles and if yes, check if there is one edge which exists in every cycle.

    Edit: As it was already mentioned — each cycle has maximum n edges, so the complexity should be something like O(nm).

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

      Your code(and mine) outputs wrong answer on test 4 6 1 2 2 4 2 3 3 1 4 3 3 2

      The expected answer is NO

      The problem seems to be that one back edge can produce more than one cycle, I think

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

    I passed the pretests by checking for every edge if the graph without this edge has a cycle. O(nm). Edit: I'm wrong

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

    I run a dfs on the graph. If there are <= 1 back edges, the answer is yes.

    Otherwise, I try erasing each tree edge. Is this correct? XD obviously I cannot remove all the cycles by removing a back edge if there are more than one back edge... But cross and forward edges shouldn't matter, right?

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

Was O(n*m) intended complexity for D?

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

Was O(n*m) intended complexity for D?

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

what can be the test case 6 for C?

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

for E, time limit is very tight, my Q * log2(N) solution got TLE, i regret it

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

Do hacks get included in the system tests for Educational rounds as well?

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

Why the problem C contains only 10 tests and problem D contains only 12 tests? C contain some corner cases and D is YES/NO problem. I thought in ERs the writer should add full testset and challenges are intended only to find some corner cases of concrete solutions? UPD: The problem B contains only 10 tests!!! It's awful. My solution contains 6 cases, but actually there are 8 cases in that problem.

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

    It is Educational Round so they should allow hacks.

    If he did that there will be no hacks at all.

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

      Of course I missed last 21 ERs, but I think that the goal of them was not to have some hacks but to fully test solutions during round for educational purposes. The hacks was needed to be sure that corner tests was made for each given solution to fail all wrong ones.

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

        If you had very big and effective test set, no one will be able to hack. In Educational rounds hacking is so strong (You can hack without any risk). So the writer can choose any test and that will be OK.

        BTW problem C is almost unhackable

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

          My point is that the purpose of ERs is to teach participants. If the problem contains full testset, the participant will see the fail of solution during contest and try to fix it in BRAIN-IN-CONTEST-MODE. It is much more useful, because some participants will not even check fail of their solutions AFTER the contest and will be disappointed, while they can get good expertise by fixing the solution during short time during contest. Also during contest participants can't see test on which their solutions failed. It's very useful skill to find a bug in solution without knowing the test.

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

            Hey! Thank you for comment. Take in account, that we can't judge many tests during ICPC-like rounds. We have thousands of participants and to prevent long judging queue we can't have more than 6-20 tests on easy problems. One more point, right now we regularly host 2 such rounds per month and we do not have resources to construct perfect testsets. Good news that because of hacks the final quality of testsets is usually about perfect. Strong contest tests will demotivate participants to hack and probably it can reduce the final quality of tests.

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

              I think having full testset is better than having lot of hacks. More than 600 solutions for todays B is already hacked (I guess it will be more than 1000 after full system test) and I think it's bad. I agree with BledDest several tests in one will be good solution to test fast a lot of solutions on a large testset.

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

                In my opinion, the biggest problem with the B pretests is all the pretests are "particular" cases: either l=1 or r=n or the current tab was at the same distance from l and r.

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

              You can use multitests

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

    because problem authorus think like "whatever, we got 24 h of hacking time, couple of yellow/red guys will definitely make some hacks so we will just add their hacks as systests and during round we'll only do standard 10-15 pretests, but now we will call it just tests. Why we do this? because we are lazy trashs"

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

    The main reason why we have small testsets is to speed up testing. The queue on the first rated ER was really awful, so we had to do something about it.

    Maybe a better solution would be adding multitests to each problem. Perhaps we should give it a try when preparing next round.

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

      I also think that multitest is a good solution. Hope I will participate in the next ER and see multitests :)

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

Who else too lazy to work on the detail for the solution using coordinate compressing and segment tree, wrote dynamic segment tree instead and got TLE on E?

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

    It is disappointing that in E dynamic segment tree get's tle. I wanted to implement this structure and thought that this task might be perfect for it...

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

    xuanquang1999 if you are creating new nodes in heap try to create it in stack instead

    Node d[15000000]; int curr; // ID of last node I created
    if (root->left  == NULL) ++curr, root->left  = d+curr;
    if (root->right == NULL) ++curr, root->right = d+curr;
    

    my first solution I created new nodes in heap and got TLE in test 18, and then after some optimization got MLE in test 32 :D now after creating new nodes in stack instead it finally gives AC.

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

Logic for C?

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

    Build the answer from the first to last digit by trying each digit from 9 to 0. Checking if a digit work can be done by trying to put all the unused digit to the right of the answer (from smallest to largest) and check whether the number you get does not exceed b.

  • »
    »
    3 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
    1. Look at the leading digit of b. Call it N. If a has N, then try to form a number from a that starts with N and is less than b without it's leading digit. (you can use recursion) 1a. If you can't form a valid number (formed number>b), continue to next step.
    2. If a does not have N, find the largest digit of a less than N (call it M). Place that digit next, and after that, place the digits of a, sorted, as it will always be less than b.
    3. If M does not exist (which isn't possible at start but if you do it recursively it will be possible), then return some value indicating this route is impossible.

    It is O(N*logN) because there is a max of 1 recursive call per call, and by using binarySearch you can find the elements of a in logN time.

    Edit: On second thought, I think this version is harder to implement than most, so you may want to try using someone else's.

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

After the end of the contest you will have one day to hack any solution you want. You will have access to copy any solution and test it locally. Where is open hacking?

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

I am new on codeforces. I have much question about this bootcamp. I am from bangladesh and I am a school student, Read in 0 Level. I want to participate on this bootcamp.but I didn't understand how? is there any school student's allowed?if allowed then I want to go. But I haven't money to pay for this my family isn't have enough money. and most of I haven't any passport and paypal or anything bank account.But I want to participate on this. But How? please Help me? Vovuh PikMike

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

After the end of the contest you will have one day to hack any solution you want. You will have access to copy any solution and test it locally. Where is open hacking?

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

Will an unsuccessful hack decrease my points?

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

Check this for C:

9111222 9222000

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

How to solve C?

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

is there any dp solution of C?

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

    simple (dp + bitmask)

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

      i tried but could not implement.can you share your idea?what are the state of dp?

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

        dp[msk][lss]

        msk tells which digits of a you have already used, lss is a bit which tells if the new number is already less than b.

        You go from the most significant digit to the least, (you can get the position of the digit from msk, so there's no need to include it in memory).

        Note that there's only really two options to try, put the exact same digit of b (and you solve the rest with the same approach) or put the maximum of the available digits which are less than the correspondent digit of b, in that case, the rest of the number is just the sorted (decreasingly) remaining available digits of a (so no need to recurse in this case). This would work without dp

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

          thank you for your comment.now i got ac.only bug was in my code, i initialized res equal to 0,now i initialize it with LLONG_MIN.Can you say that what is the problem when i initialize res equal to 0(it gives wrong output in sample test 1). http://codeforces.com/contest/915/submission/34157330

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

            By having res = 0, you are making some impossible answers possible.

            for example:

            res = 0
            
            res = max(res, go(xyz)) // i.e. max(0, LLONG_MIN)
            

            when your go() itself returns impossible, then how can res have any other value than impossible (i.e. LLONG_MIN)

            if you still want to use res = 0. You can do that. You can check if go() returned any possible answers or not and then only calculate max(res, go()).

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

          I tried solving C using digit dp , it worked but using memoization gave WA and otherwise was too slow and gave TLE . I used state as dp[index][r] where r is 0/1 which tells if formed number is smaller/greater than b , I suppose the dp state I considered was incomplete there needs to be one more parameter what could it possibly be?

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

            That's usually easy to do. Look for things you use in your function which are not determined by the state. In this case I guess you had something outside the state that told you which digits you have used.

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

Nice problemset, though I couldn't make it through D. Have to study directed graphs better :D

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

the problem statement for B says that "if the cursor is currently at the tab i, then she can move it to the tab max(i-1,a) or to the tab min(i+1, b))" where a an b are just the values of the input (l and r) correct? for me this implies that if i is outside of [a,b] i can always get there in one step? if i < a then max(i-1, a) will be a and if i > b then min(i+1, b) is b therefore in testcase 9 (100 1 100 100) it would take me one step to get to tab 100 and another step to delete all tabs therefore it would only require 2 steps and not 100!

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

    Let's say L=3 R=7 and POS=10.

    You can't move to L=3 in 1 move because max(POS-1,L) = POS-1

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

    No.

    As stated, In the aforementioned expressions a and b denote the minimum and maximum index of an unclosed tab, respectively.

    Therefore, if you move left right on the 1st step, you will still stand at tab 1, since a = 1 (as tab 1 is the unclosed tab with minimum index). As a result, your next delete command will only delete that tab.

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

      ok well i believe i just misunderstood the task... i believe i read a and b as l and r...

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

Does hacking give any points or score?

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

My O(N*sqrt(N)) solution on G got TLE. I'm wondering whether I should optimize it or there exist a O(N) or O(N*log(N)) solution for that.

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

    Take a look at the accepted submissions and you'll find there exists O(nlogn) solution using inclusive-exclusive theorem for Problem G.

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

How soon will the rating changes come out?Can I get points by hacking others?Any dalao?

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

Does codeforces gives extra points for hacking own solution???

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

Is anybody else having trouble with hacking somebody else's solution?

I click on "hack it" on a solution, but the window to insert my input won't show. There is only the button "Hack" when I click "hack it".

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

    The same problem with google chrome, no problem with firefox though :\

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

    Happens to me in chrome, but is fixed everytime if I do ctrl+F5 in that page. I don't know if that works for everyone

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

Off topic.. I thought Christmas Magic is over. But how come this user's (kissu_pari_na) profile is still showing that he's a CM? Is it a bug?

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

You know it's not your lucky day when you go to the mall to focus on the contest in a quiet cafe and it turns out that they have some noisy ass celebration at the same time

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

what is wrong with problem B :|

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

Can someone please explain how to solve problem F and if it can be solved using centroid decomposition?

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

Can one explain Problem E(Approach)?

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

The rating predictions of the predictor seem to be very wrong,don't they? It says that someone who won a div2 round will become yellow,straightaway.

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

Any corner case for B ? lot's of solution of B is getting hacked!!

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

Any corner case for B ? lot's of solution of B is getting hacked!!

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

Questions regarding Problem B. How should solution be interpreted for testcase: 7 3 3 3? Should Luba do any movement? From problem statement it is not clear what happens after closing windows for example from [3,7].

My solution has been hacked, but I found only that difference of my solution with others (likely successful).

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

    As I'm thinking, we will only need 2 actions: delete the tabs to the left, then delete the tabs to the right. We're at tab 3 already, so we don't need to make any movements.

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

      It looks like there should be some movement if I am not wrong. I compared top-ranked person's solution:

      int  n, pos, l, r;
      cin >> n >> pos >> l >> r;
      if (l == 1 && r == n) {
              cout << 0;
              return 0;
      }
      if (l == 1 ) {
              cout << 1+abs(pos-r);
              return 0;
      }
      if (r == n) {
              cout << 1 + abs(pos - l);
              return 0;
      }
      cout << min(2 + abs(pos - l) + abs(r - l), 2 + abs(pos - r) + abs(r - l));
      return 0;
      

      With my solution:

      int n, pos, l, r;
      cin >> n >> pos >> l >> r;
      
      if (l == 1 && r == n) {
          cout << 0;
      } else if (l == 1) {
          cout << 1 + abs(r - pos);
      } else if (r == n) {
          cout << 1 + abs(l - pos);
      } else if (l == r) {
          cout << 2;
      } else {
          cout << 2 + min(abs(r - pos) + (r-l), abs(l - pos) + (r-l));
      }
      return 0;
      

      And only difference in logic is for such type of use-cases like 7 3 3 3. However, I believe it is not clear situation.

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

Any critical case for C?

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

How to solve Problem D: Almost Acyclic Graph?

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

Why do you hack others if you can hack yourself? (2 line)

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

halyavin is certainly crazy madman

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

@halyavin Thanks for the early system testing

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

How to solve E, F?

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

The feeling that Educational contests is more difficult than Div 2(((

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

What was the idea behind D? Was there some fast way to check for a cycle, or something else?

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

    SOLUTION OF D: I search one cycle and check remove each edge of cycle. I do this because the maximum edge in the circle is N, then it is necessary N dfs at most. O( N * (100000). )

    Submission:34164803

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

Although the quality of problems in this round is quite good, I'd like to say that the time limit of E and G are a bit tight(at least for me).

My complexity for E is O(q log q) (segment tree) and complexity for G is O(k(log k+log n)) (inclusion-exclusion principle).

Yet I failed on pretest in both problems, even though I tried to add code like

#pragma GCC optimize("Ofast")

Actually, in my opinion, the time complexity of my solution is the same as that of the intended solution in either E or G.

After the contest, I shortened my code of G(unfolded one function). Then I passed the pretests, finding even this time I almost got TLE(3494ms): 34163831

How did all these happen? Feeling Curious.

[sorry for my poor English]

UPD:

My approach in E and G not only have the same complexity as the author's solutions,

THEY ARE EXACTLY THE SAME!

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

    My solutions have the same complexity and I have no problem with TLE: ~800ms on E and ~1200ms on G. I've done no optimizations in both problems.

    I also think that the TLE for E is a little bit tight but maybe authors tried to fail solutions with dynamic segment tree.

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

I have looked at some solutions for G and all that I have found use inclusion-exclusion or something of that sort. What I did was much shorter and in my mind, simpler.

Here is my submission: http://codeforces.com/contest/915/submission/34164542

Let's say an array has degree i if its largest value is i. What I did was let dp[i] be the number of coprime arrays with degree i. So, for example, dp[2] = 2n - 2. The key observation is that every coprime array of degree i corresponds to an array of degree i·m with a gcd of m. So, to find the array dp you can initialize it to dp[i] = in - (i - 1)n and then go in increasing order of indices, subtracting dp[i] from dp[j] for all 1 ≤ j ≤ k that are multiples of i.

bi is now just the prefix sum dp[1] + dp[2] + ··· + dp[i]. All you have to do now is keep a running sum.

Please leave a comment if you did something like this as well.

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

In problem C how to approach the case where len(b)<= len(a) // considering both of them are in string form The other case is quite simple. But I am having a hard figuring out the logic for this case. UPD: I now understand after trying some test cases by hand.

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

    Is it even possible for len(b) to be less than len(a) ? The problem statement doesn't add this constraint but I don't think a solution is guaranteed if len(b) is less than len(a), since leading zeros are not allowed, a will always be larger in this case.

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

      What about this case : 4000 599

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

        the problem statement guarantees an answer, so it can't give you in an input where length of B is less than length of A because all permutations of A will lead to a number greater than B (and you can't play on leading zeros because they are not allowed), and if the length of B = length of A there must be at least one permutation of A which gives you a number <= B

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

I have submitted the same code twice: 34164987 and 34165069. The first one passed 16th test and got Accepted with 888ms, the second one got TLE right at test 16. Can anybody explain to me why? Thanks! (I know the variability of the judging machines maybe the cause, but the difference should be smaller than 30ms, shouldn't it? ). (UPD: OK, it turns out because of different compilers, and C++14 speciafically optimize the speed of cin cout while C++11 can't do that!)

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

In case you missed the hack festival:

Update: 725 and counting!

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

"and head coach will be two time ACM-ICPC world champion Gleb GlebsHP Evstropov."

Может быть вице-чемпион?)

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

What about this case in Problem C
1230 123

answer should be 0123 but many solutions which are giving answer 1230(wrong answer) ,still accepted. (weak test cases in problem C)

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

    0123 is clearly not a valid answer. As in the problem description No number in input and/or output can start with the digit 0. And also the problem promises that It is guaranteed that answer exists., so 1230 123 is definitely not a valid input.

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

      You can't discard leading zeroes First Line in Note on Problem C. It Means output can start with leading zeros

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

        "The answer can't have any leading zeroes."

        This is quote from output format from the problem statement. Read carefully.

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

    judge validator showed me that this is invalid input.

    hack attempt tool : hacking attempt tool verdict

    in test case4: main test case 4

    why???

    my test case was: 102 100

    validator said that is test case is invalid.

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

      There is not answer for your test case. The minimum permutation of a is greater than b.

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

What exactly is the "Division" in the registration form? It contains three options: A, B, and C.

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

    Division A Designed to prepare students to participate and win medals in the next ACM-ICPC World Finals.

    A large number of teams that participated in Moscow workshops later became ACM-ICPC Finalists and even won medals — to be specific, 8 out of 12 prize-winners of the ACM-ICPC World Finals 2017 participated in Moscow Workshops ACM ICPC!

    Division B Designed to help teams prepare for the next season of ACM-ICPC regionals an international competitions.

    Appropriate as an introduction for teams and students just getting their foot in the door of the world of ACM-ICPC and competitive programming competitions in general.

    Division C Designed for newcomers to the world of ACM-ICPC competitive programming.

    For those with a handle on the basics but want to compete in future competitions and possible regionals, this division is the perfect starting point.

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

Does this round have an editorial?

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

When will the rating change be applied ?

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

I think we don't even need a system tests) halyavin already done that with 700+ hacks)

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

When does system testing start?

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

    So many hacks make it hard to start?So sad...Hope I can change my colour.

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

    System testing has started....and looks like it will take forever to finish.

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

      It would take around 2-3 hours for system testing to finish.

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

      Probably because in educational round system tests happens for every user which includes users who didn't participate in the round but submitted a solution for practice.
      So i guess it's time consuming.

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

I submitted 3 solutions for B out of which last 2 were hacked and first got AC but in standings page it is not showing the AC. Can someone please check?

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

When does rating appears ?

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

I would like to make an appeal on my charge of rewriting. I did not copy other codes. I typed my code without any help, four times I made a mistake until I solved ut. I have nothing to do with paulica. While I was trying to hack others I saw a lot of similar codes, I claim this is just a coincidence and that it was possible for everyone to happen. I had no way to get to his code.

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

can we know the time duration in which these users solved the problems???

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

Good educational round. Very interesting problems.