When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

By vovuh, history, 6 years ago, translation, In English

Hello Codeforces!

On January 13, 16:05 MSK Educational Codeforces Round 36 will start.

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

This round will be (traditionally now) rated for Div. 2. It will be held on extented ACM ICPC rules. 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.

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

The problems were prepared by Mikhail awoo Piklyaev, Ivan BledDest Androsov, Sergey sslotin Slotin and me.

Good luck to all participants!

I also have a message from our partners, 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.

Congratulations to the winners:

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

Congratulations to the best hackers:

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

2023 successful hacks and 1300 unsuccessful hacks were made in total!

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

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 ThePilgrim 0:15
G MrDindows 0:19

UPD Editorial

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

| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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

    It is unknown now but we hope so =)

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

    Last 4 rounds are so, so maybe!

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

    From now "Educational Rounds" will be rated for Div.2

    But maybe some rounds will be unrated for Div.2

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

i wish everyone ratings equal to my contribution :)

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

    Me contribution is well er. u not know da wae.

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

      No. Stop it. Get some help.

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

    I don`t wish ratings like my contribution :-) Good luck and peace!

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

      luck and peace are for the weak

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

        maybe, you are right. However, I can't see that you are red, therefore you also need luck and peace)))

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

          shut up green noob im blue im superior

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

            racism

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

            its not about what color do u belong, and who is superior to whom ,its about how much you r trying ,and he is trying his best and has given more contests than u.

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

              this is smurf account fag , i have +20 contests on other account

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

                So what...I don't know what you are proud of.Respect others effort plz

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

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

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

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

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

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

where are polygons???

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

Good luck to everyone :)

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

GL & HF!

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

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

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

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

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

since when GlebsHP is two time world champion?

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

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

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

Timelimit for E is very tight!

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

After the contest ends:

Where is that test #6?

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

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

    Consider the input 543 433. (If you mean the task C. I imagine a correct solution uses backtracking)

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

    For C? Try this : 201 200

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

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).

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

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

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

      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.

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

        use struct and pointer

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

          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.

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

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

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

      Where do you get the second log2 from? Is it an approximation for your lazy?

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

      I did the pragma thing mentioned in some other comment and my tle solution passed!

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

    I did segtree with coordinate compressing, got TL16

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

    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).

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

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

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

        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.

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

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

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

Idea for D ?

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

    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)

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

      I tried this and got TLE multiple times

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

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

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

          Can you show me your pragmas?

          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
            Rev. 2   Vote: I like it +1 Vote: I do not like it
            #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
            
            • »
              »
              »
              »
              »
              »
              »
              6 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              thx

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

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

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

                I don't know too

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

                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")
                
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

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

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

        Code

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

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

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

        No, there are N edges in one cycle at most.

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

        No, because maximal cycle have n edges

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

    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.

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

      There can be only one scc but a clique.

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

      This doesn't work with sample tests.

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

        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.

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

      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

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

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

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

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

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

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

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

              Yup you're right, somehow I missed that ;-;

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

    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).

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

      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

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

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

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

    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?

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

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

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

what can be the test case 6 for C?

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

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

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

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

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

    Yes they do the final systests contains all the hacks

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

      So by hacking you can increase your rank? and get a better rating change?

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

        No, not in edu round

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

          If your hack is something the real sys test won't catch (and only would thanks to your hack), then yes hehe.

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

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.

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

    It is Educational Round so they should allow hacks.

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

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

      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.

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

        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

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

          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.

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

            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.

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

              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.

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

                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.

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

              You can use multitests

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

    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.

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

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

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

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?

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

    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...

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

    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.

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

Logic for C?

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

    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.

  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it
    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.

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

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 awoo

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

Will an unsuccessful hack decrease my points?

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

Check this for C:

9111222 9222000

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

How to solve C?

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

is there any dp solution of C?

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

    simple (dp + bitmask)

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

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

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

        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

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

          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

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

            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()).

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

          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?

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

            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.

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

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

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

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!

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

    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

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

    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.

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

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

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

Does hacking give any points or score?

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

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.

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

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

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

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

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

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".

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

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

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

    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

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

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?

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

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

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

what is wrong with problem B :|

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

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

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

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.

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

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

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

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).

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

    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.

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

      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.

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

        Hacked!

        Test case: 9 6 3 3 — answer: 5.

        When l == r, you can only assume the answer is 2 when the initial position is on tab l/r.

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

Any critical case for C?

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

How to solve Problem D: Almost Acyclic Graph?

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

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

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

halyavin is certainly crazy madman

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

    I don't he is doing it manually, looks like halyavin has automated the whole process!

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

@halyavin Thanks for the early system testing

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

How to solve E, F?

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

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

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

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

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

    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

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

      Good Solution!

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it
      • I think add this line will be beteer.
      • You just need to add one roop's edges.
          int ciclo = 0;
          for(int i = 1; i <= n; i++){
              if(!cor[i]) ciclo = ciclo or dfs(i);
              if (ciclo==1) break; //add this line?
          }
      
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You are right xD.

        Probably i get TLE on some new test.

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

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!

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

    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.

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

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.

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

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.

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

    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.

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

      What about this case : 4000 599

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

        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

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

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!)

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

In case you missed the hack festival:

Update: 725 and counting!

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

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)

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

    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.

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

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

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

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

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

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

    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.

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

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

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

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

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

    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.

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

Does this round have an editorial?

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

When will the rating change be applied ?

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

    Open hacking phase is running. After that system tests will run with hacks. Only after that will ratings be calculated.

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

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

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

When does system testing start?

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

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

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

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

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

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

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

      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.

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

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?

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

    In regular contests (not educational) only the last submssion that passes pretest is considered

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

      So mine should be considered as correct as it is educational, isn't it?

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

        I am not sure, maybe there is no official answer yet. In the announcement of educational rounds and in this very blog we are commenting it is only said that it is held on extented ACM ICPC rules — maybe there is a formal description of such rules that I dont know about, but it is a good question.

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

    I'll look in it tomorrow.

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

When does rating appears ?

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

Good educational round. Very interesting problems.