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

On Oct/25/2018 17:35 (Moscow time) Educational Codeforces Round 53 (Rated for Div. 2) will start.

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

This round will be rated for the participants with rating lower than 2100. It will be held on extented ACM ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

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

The problems were invented and prepared by Roman Roms Glazov, Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov and me.

Good luck to all participants!

Our friends at Harbour.Space also have a message for you:

Hey Codeforces! We want to remind you that the Scholarship for the Master’s in Robotics programme, which starts on January 7th 2019, has an application deadline of November 12th, 2018.

Harbour.Space University and Remy Robotics are collaborating to offer graduate students from anywhere in the world a once in a lifetime opportunity, a fully funded scholarship for Harbour.Space University’s Master’s Programme in Robotics.

The scholarship value is €34.900 and it includes:

  • Complete coverage of the University tuition fee (€22,900)

  • Internship at Remy Robotics (20h per week during 1 year)

  • €1,000 per month during 1 year (Internship earnings)

Apply here

UPD: vovuh and me will be waiting for you on the community Discord server shortly after the contest to discuss the problems.

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 pekempey 7 305
2 ko_osaga 7 578
3 Lewin 6 216
4 fanache99 6 226
5 natsugiri 6 257

Congratulations to the best hackers:

Rank Competitor Hack Count
1 halyavin 238:-15
2 Laggy 64:-14
3 MarcosK 59:-9
4 Mistra 8:-1
5 LordVoldebug 7:-1
482 successful hacks and 684 unsuccessful hacks were made in total!

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

Problem Competitor Penalty
A Dalgerok 0:01
B dorijanlendvaj 0:02
C fanache99 0:10
D bazsi700 0:13
E DAyamaCTF 0:21
F Noam527 0:48
G ko_osaga 0:24

UPD2: Editorial is published

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

| Write comment?
»
6 years ago, # |
Rev. 2   Vote: I like it -39 Vote: I do not like it

...

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

I always have this question:Why Educational Codeforces Round uses extented ACM ICPC rules? I think the rules of CF regular rounds are very good:-) Thank MikeMirzayanov

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

    I wish if they could make another round type with no pretests .. why is it so wrong that if I submit a solution I will get AC or WA instead of pretest passed and then a short sad story

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

I'm sorry. The last comment was not posted by me. I'm not mean to do it.

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

    Yes, awoo became orange a few days ago.

    After 4 years of hard work, nothing is impossible.

    Congratulations, awoo!

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

Hi all! this is my first round here. what should i know about codeforces?

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

    You should know that this is not your first round.

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

    You should know whether or not it is rated.

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

An Educational round after a bad contest, awesome.

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

Educational Round is here, Summon halyavin !!

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

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

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

How to solve Problem C?

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

    Binary Search on length and check the possibility in O(n) by traversing the string.

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

    Two pointer

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

    Binary search on substring size.

    To check if you can get from a position to other in certain number of moves, the sum of absolute differences between positions in both dimensions has to be not bigger than the numer of moves, and be of the same parity.

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

    I did binary search on the length of the subsegment.

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

I'm so sad that I didn't have a code ready for segment tree beats. This would have been the first time I could use it in a real contest (in problem G) :(

Didn't have time to write it either since It once again took me too long to read other problems after getting stuck in one.

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

    I dont think G needs segment tree beats though it is nice if it can solved that way.

    we can compute lcp array and then for each query we can keep 2*query size ranges and perform something like for how many pairs of a and b will particular range be minimum value (its similar to solving sum of minimum over all segments in an array but instead we have weights to elements here).

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

How to solve E?

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

    In general — digits and masks DP. Calculate the following dynamic programming: dp[pos][mask][f], where pos is the current digit of a number (starting from the greater one), mask is the binary mask of used digits and f equals one if prefix of our current number is the same as in the number n. You can calculate the sum of suitable numbers from 1 to n using this DP. Then the answer is calc(r) - calc(l - 1).

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

      I have a confusion. A prefix can be in the range of 64-bit integer. How can I use this big number as a state?

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

        You don't need to use the number as a state. The position in this number is enough. To do some transactions you need to place the new digit in your number and recalculate DP. Ohh, the most important thing — to calculate the sum of numbers you need to calculate two DPs, one for the count of such numbers (this DP is auxiliary) and DP for the sum of such numbers (to calculate the answer).

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

          Hey, why don't you need to keep track of if you have put something greater than 0, for cases like 000124 and k = 3, because you only turn on the 0-th bit if you had put something greater than zero before?

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

            My solution calculates this DP independently for each length from 1 to |n| and says the sum of numbers of exactly such length. But I thought that I can calculate for all lengths at once because where you places leading zeroes, the count of these numbers will be right. The sum will be right also (because 0 doesn't contributes to the sum at all)

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

              Oh nice, jeje I was calculating all at the same time, that's why mine is different. Thanks.

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

      Sorry, I read that wrong.

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

      I can find number of different integer from [l,r] using digit-dp but how to find sum of these integers?

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

        say calculate for num = 78520193
        iterate from left to right, say you are at position 3 (digit -  > 5) right now, then how many times (say T) does 500000 in your answer?
        it is simply number of ways you can form numbers  <  = 520193 which can found by DigitDP ( you also need to ignore if number of digits used are > k , for which you can use mask --> set the bit for the digit you included ) then this sum would be 500000 * T.
        Now this value if repeated for 78520193, 68520193, 77520193... and so on , since prefix upto position 2 can also change , so for that make another dp table and do the same digitDP for this now.

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

    Probably DIGIT DP, however could not implement it ;(

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

      I tried with digit dp too, couldn't define states.

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

    I always try to make something recursive like answer(A, i) that is filling array A from 17 to 0 and i is the position where we can choose a value. Complexity would be 10^18, but if we make these optimizations complexity drops: If the number cannot be in the range [l,r] return 0; if it will always be in a range [l, r] ask the answer from another dp function.

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

the contest ended ?? it was scheduled to start now, did i miss something ?

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

I am having a hard time with Problem B, Please Help.

My code which works on every other online IDE under 0.01s is getting TLE on case 1 here. I have used GNU's policy based ordered tree in it. used G++ 17 to submit.

Here is my submission -- > 44858365

I tried tweaking things a bit, using int instead of ll. Nothing helped. This thing ruined my already not so good rank, had to rewrite a different solution. :(

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it
    stk.erase(x);
    st.erase((*x).S);
    x++;
    

    This is undefined behaviour because you are doing something with an iterator that has been erased.

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

      Yes, you are right, I actually figured this out later after I posted here for help.

      Iterating while erasing should not be done this way either, because even x++ is invalid after calling erase. I read it here on SO.

      Thanks anyway!

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

    Use deque data structure , its pretty fast

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

      Yes it is fast indeed.

      Actually this question was pretty easily solvable without any RB tree like i used. I just wanted to try my hands on that special GNU Policy based DS.

      After i failed to do that with gnu_pbds ordered set, i did that question using a simple vector and a map.

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

how to solve D?

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

    The first booth we can't buy must supply the most expensive candies. So we can simulate this procedure. Calculate the current whole price and find the most expensive booth. Then we can compute how much we will spend before we buy the last candy in this booth. Then we subtract the cost and add the quantity.
    Until None of candies can be bought.
    We can use binary indexed trees or segment tree to compute the cost and the quantity.

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

      D could be solved using SEGTREE descent in n * log(n) without any thought........... But if you observe one can write brute force solution also...that would also fit into time limit because of the fact that for any two numbers a,b ............. a%b <= (a + 1) / 2 its time complexity would also be n * log(n)

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

        how can you say that a%b <= (b + 1) / 2 ?

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

          iff a>b........one can varify that a%b can take values from 0 to a / 2 by taking few examples.

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

            Sorry i still didn't get it. for ex- 15%8>(8+1)/2.

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

              He said <=(a+1)/2, not (b+1)/2.

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

                ohh he changed that now xD.

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

                It was my mistake ....I edited it afterwards...Sorry for that..

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

              Its .

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

                15 mod 8 > 8 implies 7 > 8 which is wrong

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

                  Yes, it is wrong.
                  I just wanted to correct the jonsnow7's comment, where he mistakenly compared wrong values.

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

        Can you please tell me how to do this using segtree descent ?

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

        I think there is a problem with modulo condition.

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

        That’s why I spend about 30 minutes while others only spend 10 minutes solving the problem.XD

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

        Can you please elaborate how can I use segment tree here(like what to keep in node and how to query)?

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

          We can compute the cost and quantity in a interval by SEGTREE. This is my solution 44866016

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

        44935386 What is wrong in my solution??

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

          You are not re-initializing sum=0 in while loop .

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

I tried to use two pointer technique for problem C.

Code

However I got a WA. Can somebody please help me in figuring out where I was wrong.

Idea:- Caluclate the position x and y based on the given string. Calculate the diff in x and y based on goal x and y. Now calculate diff between goal x and x and for goal y and y. Now if the diffs in each dimension are not divisible by 2 or the required characters needed are less than given in the string output -1. Otherwise use two pointer to find the shortest string length.

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

    did you check if diff in x is divisible by 2 and y ?

    because if both is you need 2 chars to cancel each others

    for example if you have RUR and x=1 y=0 then it would be RLR

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

      Yes if you check here lines 75-83 do this.

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

        Idk then I was trying to do it with binary search but coding it was a bit hard

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

    are you failing on test 5 like me(http://codeforces.net/contest/1073/submission/44891148) i also implemented using two pointer kind of thing.

    in test 5 all 'R' are 24 and all 'L are 27 in number and final destination's x coordinate is -59 which is unachievable if we even turn all 'R' to 'L' which will give 51 'L' hence we can at max go to -51 in x direction isn'it test case no 5 is ->

    100 URDLDDLLDDLDDDRRLLRRRLULLRRLUDUUDUULURRRDRRLLDRLLUUDLDRDLDDLDLLLULRURRUUDDLDRULRDRUDDDDDDULRDDRLRDDL -59 -1

    r=24 l=27 d=32 u=17 please comment how it is possible

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

      You can change any operation to any other operation. So you can even change U or D to L

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

I feel like D was much easier than C. Some people wasted too much time unsuccessfully solving C, while they could solve D instead.

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

    I'm not sure, but I don't think there's a rule that difficulty(C) <= difficulty(D)... |-)

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

    The problems aren't always sorted by difficulty in educational rounds, I think.

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

    I figured out C easily and implemented it within 20 min, I had 1.1hrs to do D, but couldn't. :(

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

Dear anyone please try to hack my solution for D 44864411 Thanks :D

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

How to solve C ?

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

    Binary Search for the answer. To check whether you can have a subsegment of length x as the answer iterate over all the subarrays of length x and then all you have to check is whether the difference between the expected position and the actual position is greater than the subarray length or not and also if the difference is less than the subarray length we need to check the parity of the difference between the 2 values.

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

in problem C, when I realized that I used binary search in wrong way, and it took a lot of time to correct my solution but too late. Im now feel a little regret about it, hmm. Hope these experiences will help me grow up in the future. Hope you guys have good rating after the contest <3<3<3

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

    can someone tell me why I get so much dislike, i dont think that my comment is annoying people like this. and I also wonder why my contribution is a negative number (-4). why this happened to me, plz help me, (T-T)

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

can anyone give me a single reason why this solution give tle https://codeforces.net/contest/1073/submission/44874378 and when i change compiler to c++11 it give acc + almost all my friend list got acc with the same code and without fast input and this is my code acc https://codeforces.net/contest/1073/submission/44877617

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

    Nothing strange, since the newer compiler provides better optimizations for your code, therefore better time.

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

      so what

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

        So, your code TLEs and shouldn't get AC ( tho you can get it AC by using static arrays instead of maps and maybe using integers instead of long long since it's not needed)

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

    It seems to me like you didn't "change compiler to c++11" between the two submissions, both of them were submitted with GNU C++11. The difference is one of them uses fast input and int type, while the other one uses "slow" input and long long type. Obviously, the latter one will be slower. No surprises there.

    P.S. your solution is already sub-optimal because it runs in O(n * logn) time. Had you implemented the optimal solution (which runs in O(n) time), then it wouldn't have mattered which types and what kind of input you used :)

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

How do you solve D? I thought of using 2 BITs, however the number of submissions indicates an alternate easier solution.

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

    On each iteration you have some money and sum of remaining candies. Just buy as much of every candy as you can and then, when your remaining money will be less than sum of every candy left, just try to buy them one by one in O(n). Also maintain sorted candies to check if remaining T is enough to buy highest costing candy. If not no need for them and just skip until you have one that is less. During that decrease sum of all candies left.

    Apparently T's decrease is logarithmic so you end up with O(n log(n)). There are possibilities to improve performance in many ways, but none of them are needed to pass the tests, sadly (I did some and now regretting the lost time in implementation).

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

    I solved it with just 1 BIT. You try to buy 1 candy for every booth, if you can't, then you can binary search the position where sum of 1...i becomes greater than T, and you erase it from the bit (you update position i, with -value[i]) and keep doing that until you can buy 1 candy for all remaining booths. At the end, you had to do N Binary search which is O(N*ogN*logN) or O(N*LogN) if you use the trick of binary search on BIT. My submission

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

      Yep, I had a similar idea! How did you keep track of the count of valid booths since you're erasing them from the BIT?

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

        oh, you can use a variable, initially, you have remaining = N, every time you erase one, you do remaining--

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

      or O(N*logN) if you use the trick of binary search on BIT

      Could you please explain or give some resource about this trick ?

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

      Why, you set  - value[i] to i instead of 0? Don't we need to neutralize/erase it?

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

        Yes but remember when I first inserted the value I added value[i] so now I need to subtract that. Remember that BIT is sum of all values lower than i . If you update with 0 you are not doing anything.

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

Can someone please tell me how this O(n) solution TLEd on B? http://codeforces.net/contest/1073/submission/44854424

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

    Your forgot to use your fastread: 44876642

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

      Yeah, that's how I got it to pass. But the input size is not that large. I usually don't fastread for this array size and have never faced this problem before. I guess I've learned my lesson about that!

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

        "Input size is not that large", input parsing has the same time complexity as the solution itself (both O(n)), so (percentually speaking) it can't really get much "larger" than that.

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

    Maybe 'endl' (with flush?) issue? Try to change to "\n" (or '\n'). Reading 4e5 data, maybe use yours 'fastread'?

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

      I have a #define endl '\n' in my template. Using fastread made it pass, but I have not had that problem before.

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

        Alternating cin and cout automatically flushes cout. So it's technically the same as using endl. cin.tie(NULL); separates cin from cout so that it won't flush it anymore. Therefore it's important to use it here.

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

i can't hack with Generator and i get invalid input can you help me

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

    There can be two reasons for invalid input. 1. Make sure you have newline character at the end of the generator output. 2. Make sure the last integer or character or whatever variable of generator output is followed by new line character instead of a space i.e. run loop for n-1 numbers and print last number followed by new line character instead of space followed by newline character

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

Can anyone explain C in detail. What are we exactly doing after applying binary search on the length of a substring?

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

    In C, we can see that if we do change a substring of size k, then it doesn't matter if we change 1 or k elements in the substring. An easier approach would be to change all of them.

    Let's say that we're at (x, y) and we have to go to (a, b). The shortest way between the two points is the Manhattan distance between them. However, if your k is greater than this Manhattan distance, you might want to 'waste' some moves before you reach there. It is easy to see that the number of moves you 'waste' will always be even.

    So, if we do have to change this k subsegment, we can do it only if we can travel the Manhattan distance, and waste some moves if any. More formally, you get k >  = dist((a, b) , (x, y)) and (k)mod2 = (dist)mod2.

    Another observation is that if you get a valid subsegment of size k, you can get it for k + 2 as well. However, we don't know about k - 2.

    So, we would binary search over all the even sizes and odd sizes of k separately and pick the minimum. We can binary search as the function of whether k works or not is monotonic. Or in other words, it's of the form NN...NYY..Y.

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

      can you please elaborate why binary search works here. i didn't get the last part.

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

        The reason we can apply binary search on a sorted array is because of the property that if i > j =  > A[i] >  = A[j]. So, if we are searching for an element k, and it's lesser than the present index, it implies that it would be lesser than all the indices on the right, so we don't need to check there.

        Similarly here, we can observe a similar property, which is that if we can find a suitable segment of size k, we can find it for all k + 2 * c, where c >  = 0. Thus, we could check for a potential minimum on the left. This is because the number of moves we 'waste', will always be even.

        On the other hand, if k it not suitable, it means that all k - 2 * c for all k / 2 >  = c >  = 0 will not be suitable, and thus we need to check on the right.

        You could have a look at the Topcoder tutorial here for a better explanation.

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

Can someone explain it to me why the solution for E got WA on 7? My solution for E I know my solution will calculate wrongly in some big cases but I don't know why.I take mod everywhere. Sorry for my poor english. :)

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

Can any moderators look into this case? Thanks!

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

What are the hack cases on C?

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

What does this error mean?

How to correct the error?


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

    After successfully generating the test data, print out one last endline character.

    (This one is not required in manual hacking, yet mandatory for generator-based ones).

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

A very very nice observation in D of why brute force would pass: The outer loop won't execute more than log(t) times because after each loop, t becomes t%i where i is some number <= t and if i<=t, t%i can take values from 0 to t/2 (proof is easy :) )

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

Can anyone explain why this gave TLE for problem D: https://codeforces.net/contest/1073/submission/44873511

The complexity according to me is O(n * (log n)^2) which should have passed. Is it because of inefficient code?

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

What's special in test case 8 for F problem.Getting "Sum of paths in jury is larger than participant".Isn't it just the two farthest nodes from the respective 2 end nodes of the common vertices path?

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

How to solve F?

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

I'm very sorry of what I've said

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

Editorial?

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

Why is E easier than D and D is easier than C -_-

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

Can any one provide me with nice digit on dp blogs?

Thanks in advance

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

Why E Wa on test8? I'm very confused.

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

Is the editorials published?

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

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

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

The solution of problem F is: use greedy thoughts to find the longest path in the tree. So, we will look for the first point of the common part as root, then dfs () from that root to find the other end

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

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

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

Can anybody describe the solution of the problem G (Yet another LCP problem)?

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

Has editorials been published? If not, can anyone provide me solution to Problem D.