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

Hello Codeforces!

On Nov/13/2019 17:35 (Moscow time) Educational Codeforces Round 76 (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 extended 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, Maksim Neon Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

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

Attention Codeforces!

Calling on all tech disruptors, data specialists and computer science pioneers.
We are offering fully-funded international scholarships for exceptional tech specialists from around the world. Accelerate your career by becoming an industry expert capable of making key data-driven decisions that add value and drive innovation within tech industries.

Harbour.Space University has partnered with SCG, a leading business conglomerate in the ASEAN region, to offer exceptional tech specialists the opportunity to work and study in two of the most dynamic and vibrant cities in the world. Join our progressive two-year program based in Bangkok, with 6 of the 24 months in Barcelona, to develop the international mindset needed to accelerate your career and redefine how data drives the businesses of the future.

Codeforces and Harbour.Space

Tuition fee:

2 years | €45,800

Education:

3 hours of study per day | 15h per week

Work Experience:

4 hours of internship per day at SCG | 20h per week

Living Allowance:

€16,800 euros | €700 per month living allowance


APPLY HERE→

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 neal 7 182
2 kmjp 7 216
3 saketh 7 218
4 KrK 7 225
5 ivan100sic 7 244
5 pwild 7 244

Congratulations to the best hackers:

Rank Competitor Hack Count
1 Decayed 39:-10
2 liouzhou_101 59:-58
3 dzhiblavi 15
4 Rian_5900 31:-40
5 Fyodor 10:-2
278 successful hacks and 501 unsuccessful hacks were made in total!

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

Problem Competitor Penalty
A amnesiac_dusk 0:00
B Siberian 0:02
C Bohun 0:03
D LJC00118 0:16
E jjang36524 0:23
F TripleM5da 0:19
G black_horse2014 0:19

UPD: Editorial is out

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

| Write comment?
»
5 years ago, # |
Rev. 2   Vote: I like it +26 Vote: I do not like it

Hope to become expert in this contest......

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

Strange that there's only one comment in 14 hours. Anyway, it's a PikMike contest so I'm excited. Hope I can finally get candidate master lmao.

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

hope to become specialist in this contest.

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

    hope to become unranked in this contest)

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

      hope to become headquarters after the round.

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

        Hope to become Batman... after this round...

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

      Hope to find Girlfriend after the round.

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

        Make your handle GF_in_Three_Months

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

        Me too, I made a bet with my friend and I should find a girlfriend in the next 40 days. ;)

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

          It's fair easy for you. Just pass her some solutions :P

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

            And marry her if she could hack them.

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

    Dammit I'm only expert.

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

Hope to become 1500+ this contest.

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

Good Contest.

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

Were Segment Trees necessary in D? I had to do some maximum queries on the monster array, was too scared to try my solution without the tree.

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

    Well, i did a sparse table

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

    we can take the suffix max after sort the hero on the basis of its power and then take lower_bound.

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

      I've done that. I said maximum queries on the monster array

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

    Not necessary, Although I thought about Segment Trees first

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

    Overkill segment trees was not needed at all.

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

    no

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

    I think if you sort heroes' by power, you can calculate the maximum endurance for each suffix in O(m)

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

    I did it without Segment tree. Solution. Just sort, binary search and array for suffix maximum endurance

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

    Not at all. Just sort the heroes by endurance O(MlogM), than in O(N+M) build an array that stored at element i what is the maximum power between heroes with at least i endurance. Then simply loop the monsters array O(N) and with a single lookup it can be found if the current monster could be beaten up during the same day or it is needed a new day

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

    I did not use a segment tree or sparse table for this problem. You can check my solution: http://codeforces.me/contest/1257/submission/64838220

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

How to solve C?_

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

    The answer is the minimal distance between two equal elements.

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

      why

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

        If you check the subarray that is the answer to the task, you will see that it's first and last elements are equal (because it is the most optimal). And all the elements between them are all different.

        Sorry for my poor (maybe) English.

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

        If you look at two equal elements in an array then the only case where it is not dominant is if there is at least another pair of two inside. The equal elements that have the minimum difference between them cannot contain another pair because that would contradict that the elements we found have the minimal difference.

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

        because when you take two elements with minimum distance then between these two other element appear at most one.

        1231 if there is repeated value between two 1 then distance between 1 can't be minimum.

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

        Consider you have two suquences

        1 4 3 2 4 1

        Now here, we can choose the first 2nd and last 2nd element in a segment. That will form the minimum.

        and other,

        1 4 3 3 4 1

        Now here, if we choose the same indexes as an upper example, it would be wrong. Because we can still minimize the segment to {3,3}.

        So we can conclude that all we needed to do is minimizing the difference between equal elements. Hope you understood.

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

          why result is 4, 5, 4 for 4 1 2 4 5 4 3 2 1 and not 4 4 for example

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

            Because choosing a subarray should be contiguous.

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

            ****The subarray of a is a contiguous part of the array a, i. e. the array ai,ai+1,…,aj for some 1≤i≤j≤n.****

            you missed this line.

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

      Wow, I feel dumb now jury-rigging a two-way multimap keeping track of element counts and number of elements with the maximum count

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

    you have to find minimum difference between two repeated value. save the last position you get for each value and when you get it again take difference and update position of last appearence. then take minimum of all diference.

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

    We note that, there is a answer if and only if some number is repeated otherwise ans is -1.

    The shortest such subarray will be |start of that number(x) — another instance of that number(x)| so just count how many repeated numbers are there and print the minimum distance b/w them

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

    I used two pointers which I later realized to be difficult to solve that problem.

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

In question D, codeforces giving different output than other platforms like hackerrank, onlinegdb for the same code. Output on codeforces is coming as 0 and -1 for the 1st test case but it is correct on other platforms. Does someone know why is it so

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

    It's an undefined behavior. For example if you donn't fill a local array explicitly, it doesn't have to be filled with zeros, it may be filled with anything depending of compiler.

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

    See diagnostics in your submission: "Error: attempt to dereference a past-the-end iterator." I had a similar solution with the same bug. That lower_bound returns the end of the map when there's no heroes with energy day or more left.

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

Seems not sorted by difficulty...

RIP my rating.

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

    It seemed very sorted to me. I won't say they were easy though, I might get hacked when I least expect it

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

F is just btuteforce, LOL. 100e9 in 2 seconds))

UPD 1: Hacked.

UPD 2: Added set, Accepted.

UPD 3: Passed final tests in 2.5 seconds.

UPD 4: More stable program with a run time 1.9 seconds: Link.

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

    Can you elaborate a little more please?

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

      Just implement the dumb checking described in the statement with some optimizations (pragma`s, shuffle, set and popcount is enough). Code.

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

    Bruteforce way can be Hacked, test cases are weak.

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

Good test cases on F, I tried my best to make random solutions pass and failed.

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

How to solve D???

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

    Greedy.Every day,choose a hero who can beat most monsters.

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

      Can anyone please elaborate on this? How to choose the hero who can beat most monsters? I did something in my solution but I find that to be too messy.

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

        Binary search on the hero. Solution

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

          I saw people's submissions where they were obtaining the suffix maximums over the max. powers needed for a fixed endurance value. I find that idea to be much less on code. I'd like to know about that idea as I am still not able to think about it.

          UPD: I have mentioned the idea in one of my comments below.

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

        Just sort the {power, endurance} array. Then start with the first monster and check maximum power needed to defeat the dragon(Binary search), also I have maintained a suffix array that will store maximum endurance. If we can defeat the dragon then try to take one more dragon on the same day otherwise start with a new day. Link to my Solution

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

    I implemented O(m*n), and though in worst case scenario there is no way it passes TL, it somehow got accepted.

    I sorted heroes in descending of their stamina, and for each hero in this order I tried to find maximum of monsters he can beat if he enters now (i.e. iterate mosters one by one and increase counter if monster is weaker and hero's stamina is not exceeded). I break cycles if I find a hero with lower stamina than my current maximum.

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

      We still are in the hacking phase, someone might try to break your code so it gives TLE, hopefully not!

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

    My approach is, at first I sort all the heroes in basis on their power and then endurance in decreasing order. Then I try to find out maximum power for every endurance. It always proves that endurance[i]>=endurance[i+1]. Finally, at every step, I just try to pick the longest endurance(using binary search) which can able to kill all the monsters on that range.(I use segment to find out the maximum monster value on that range). If there is any monster whose value is greater than the maximum hero's power then the answer is -1.

    My solution -> https://codeforces.me/contest/1257/submission/64846739

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

    I finally managed to understand the easy way to solve the problem by going through people's submissions. I'll try to explain.

    First, if we are currently at the $$$i$$$th monster, we have to choose a hero that can kill the largest no. of monsters. The only tricky thing is choosing that hero. Let $$$cnt$$$ denote the current no. of monsters that we can kill from the $$$i$$$th position. Initially, $$$cnt = 0$$$. Now, $$$cnt$$$ can be extended to $$$1$$$ iff there exists some hero whose endurance $$$\ge 1$$$ and the power is more than the power of the $$$i$$$th monster. Using this logic, we'll be extending $$$cnt$$$ as much as we can. To extend $$$cnt$$$ by $$$1$$$, we have to check to see whether there exists a hero whose endurance is $$$\ge cnt + 1$$$ and whose power is $$$\ge$$$ power of all monsters within the range $$$[i, i+cnt]$$$. If there does exist one, we can extend $$$cnt$$$ to $$$cnt + 1$$$.

    To check this thing, we can have an array we store the maximum power of a hero whose endurance is $$$\ge i$$$. This can be computed by taking suffix maximums on an array where the $$$i$$$th element is the maximum power of a hero whose endurance is $$$i$$$.

    Also, since we are always extending $$$cnt$$$ by $$$1$$$, we can instead keep a running maximum of monster's powers instead of using a data structure to obtain the maximum within that range.

    Code

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

      Hey roll_no_1, I did a similar thing as well, but in the other direction, so just putting my strategy here as well

      Invariant: If there is a hero with more power and more endurance, he is always better than anyone with both of these lower.

      Steps: Create an array that has the best weapon for each endurance -> update bestHero[endurance] = max(bestHero[endurance], power) and then place the suffix max

      This step would mean that at every value of endurance, the best value of power that is greater than or equal to the power for the range having more endurance is taken. (Greedy choice)

      Move from the back and kill the current monster, if you can't kill the current monster, along with the suffix, add 1, else, keep expanding the array backwards updating the maximum.

      Overall an order of O(n+m)

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

      I did solve with the same concept but with binary searching. keeping a max suffix array is much more cleaner. Thanks for sharing, I learnt something cool.

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

    You can solve the problem without using segment tree or binary search. http://codeforces.me/contest/1257/submission/64838220 Just a map and lower_bound is required

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

    I did a greedy solution. 64832445

    Explanation — sort heros according to endurance and allocate each monster a hero starting from max endurance, than start making maximum group possible.

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

Given the huge TL, I imagine my solution for G is off, but is it something like finding number of solutions to $$$\sum_{i=1}^d x_i = k$$$, where $$$d$$$ is the number of distinct prime divisors and $$$k$$$ is the minimum power of one of the prime divisors?

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

    k is actually floor(n/2).

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

      Upon further thought, it makes sense that it shouldn't be the minimum power of the prime divisors, but it's not at all clear to me why floor(n/2) encodes the proper information. Can you elaborate?

      EDIT: Just tried to verify this on the samples. Unless I'm misunderstanding what you mean by n/2, this doesn't seem to work.

      EDIT2: My implementation was wrong, tried to use stars and bars where I couldn't. My bad.

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

        n is number of prime divisors given in the input.

        Lets say (p1,p2,..,pd) are the distinct prime factors and (a1,a2,...,ad) are the powers of prime factor. Now you can represent these tuple of powers (a1,a2,..,ad) for each divisor as a partially ordered set (poset).

        The goal is to find the longest antichain which is the width of the poset.

        You can notice that sum(ai) represents a distinct level.

        Lets say the number is 2^4*3^2.

        (4,2) represents level 6. (sum=6)

        (4,1), (3,2) represents level 5. (sum=5)

        (3,1), (4,0), (3,1), (2,2) represent level 4. (sum=4) and so on.

        Its kind of intuitive that the poset is symmetric about mid level (level=n/2) and that should have the maximum cardinality. I dont know a proof.

        Thus the answer to the problem is the number of solutions such that sum(ai) = floor(n/2).

        This can be solved by fft.

        My submission

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

          I see; thanks, that explanation makes a lot of sense!

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

Can E be solved using this idea:

1) Iterate from i=0 to n. i is the last problem of first-person.

2) Then do a ternary search for getting the answer among 2nd and 3rd person.

Is this idea correct?

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

    isnt binary search enough? I did not code it, I am a binary search code noob

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

    I don't think this solution is correct. As the cost of distribution between 2nd and 3rd is not necessarily unimodal.

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

I'm not sure if it was intentional, but E could be solved by ordering the three lists, concatenating them, and then running a very well known LIS (Longest Increasing Subsequence) algorithm.

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

    The answer was simply (K1+K2+K3) — N, where N is the length of the longest increasing subsequence.

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

    Can u help me prove it why is it LIS? The idea intuitively seems correct.

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

      LIS size is the most objects you can remain unchange

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

    But why it's working?

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

      Sort each array independently. Given this LIS size, you know maximum amount that are in place. The goal is to get whole array sorted, and each operation increases that number by 1 (place the element out of order to its position), so we will need that amount of operations. This is not a formal proof but an intuition of how I see it

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

      It's actually exactly COCI lista

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

    This is beyond my knowledge. Never knew LIS would be this powerful. This not only works for 3 arrays. The intuition is you want to maximize the amount of element to stay in its segment. What an elegant solution. to restore the steps of the answer, youll simply make the LIS related elements stay and move the rest greedily.

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

      It seems so obvious and easy once we understand the idea.

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

    It wasn't intended (model solution uses some math and prefix sums), but the solution is really cool nevertheless!

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

    Amazing solution!!

    this is a good source for people who dont know LIS to learn how it works.

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

How to solve G?

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it +17 Vote: I do not like it
    Hint: It turns out 'finding' the subset is easy but 'counting' it is hard. Can you prove a certain subset must be maximal?
»
5 years ago, # |
  Vote: I like it +33 Vote: I do not like it

Why has CF started giving T test cases for every problem like codechef does?

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

    Now it's easy for us to run all the sample cases at once

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

      Yeah, but then i need to care about resetting global variables and arrays when problem has T test cases and it increases my chances of making a mistake.

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

        Wouldn't that be caught on the sample cases?

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

        You don't have to use global variables. They are evil.

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

    It's a common solution for ERs (and, it seems, div3) because it's too much burden for the system to check 20-30 tests (and 30 tests are not enough sometimes) per each submit especially on tasks like A, B, C.

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

    I highly prefer it this way. You get to have much better test coverage without insane queues.

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

Good Contest.

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

How to solve problem C?

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

    You just need to find the minimum difference of i and j, of same element. If no such i and j exist ans=-1;

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

      What will be the time complexity? Will it be O(n^2)

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

        Depends how you implement, I did it using pair and map in O(n).

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

English lesson: волшебная палочка — magic wand. :)

(Don't try to look it up on Google — you'l get the wrong idea. :)))

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

Finally gained some confidence, Thank you so much for the contest.

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

    What will you say when all your solutions are hacked? lol

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

only single line error in solution of problem D drop my dream of Expert.

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

    Don't worry. We hope you will expert very soon.

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

how to solve F?

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

    Use meet-in-the-middle, split x into first 15 bits and last 15 bits, and use map to check if there is second half.

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

      Does this fit in time limits?

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

        There will be like 2^15*100*30 operations if you use hashmap.

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

          Done!! thanks

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

          I wonder if it's possible to do a hash collision attack to force lots of deep equality checks if your hash function is deterministic

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

    Simplex!

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

      I also tried to solve the problem by constructing equations and inequations but didn't know how to solve the system. Can you please provide some useful resource to learn the simplex method and also to understand how to code it? Thanks.

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

Can anyone point out what the mistake could be for test-case 2 on problem D ?

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

    Try something like this: 2 6 1 2 3 3 3 3 3 3 3 6 1 1 6 (ans = 2) 6 6 1 2 3 4 5 3 3 3 6 1 1 6 (ans = 4). These tests helped me to find out my mistakes

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

i just have solved problem 1257C - Dominated Subarray — in Greedy solution in just O(n) ; why you did'nt include Greedy tag ! this is my submission : 64830934

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

    std::map works in O(log), not in O(1). So, your solution is O(nlogn)

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

      IWMG my friend did you read my solution !!!?
      i never used std: map in it but just called it . i have used just one loop to read Input and an array to store last position for an element ! why it is O(n log n ) !

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

        Yeah, im sorry for it, i thought you use only maps. Then you're right, your solution works in O(n)

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

In problem D, we have to take input from the users which is O(n). So total TC would be minimum O(t*n) which is the order of 10^12. How is it passing?

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

    It is guaranteed that the sum of n+m over all test cases does not exceed 2⋅10^5

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

I can only solved 2 problems... kinda have feeling my rating will be decreased again XD. I hope I can get better next time T_T. Gotta learn more frequent.

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

Any clue about the 18th sub-test of test case 2 in problem D ?

Edit: I was writing min in place of max in Sparse Table. XD

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

Who else, first, thought of Binary Search for C? xD

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

    :-/

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

    I thought and did it that way only.

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

      Yeah, but you applied binary search to get the index where a[i] occurs next. I was applying it to find the optimal length.

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

        Yes.

        Maybe.

        Submission

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

          Nice solution. I was checking if there exists a subarray of length exactly mid such that it is dominated, if no, I assumed that there will not be any dominated subarray with length less than or equal to mid, which clearly is wrong.

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

Whats the DP solution for E?

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

    dp[i][j]: I'm looking at element i, at group j.

    I can either start the next group -> dp[i][j]=dp[i][j+1]

    or add element i to existing group -> dp[i][j]=(i is not in group j) + dp[i+1][j]

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

For all of you that want something to uphack but can't: 64856439. This shit really shouldn't pass, it should get WA or TLE or both.

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

Try to hack my $$$O(n*2^{30})$$$ solution to F: Link

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

    How does this runs in less than 2 seconds?

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

      It does, my approach takes approx. 3 seconds on the judging server of CF(I used vectors and cins and stuff), yet it took forever to run on my own computer.

      However, I am getting WA 92 for some strange reasons, and since my logic is very similar to his, maybe he will get WA on the same tese(just my guess).

      I went through his judgement protocol and saw that he has only been tested with tests 1 to 83.

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

        Oh, somebody already put into the effort to tinker the constant and break it lol.

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

What on earth is test $$$92$$$ of problem F? I kept getting WA for it using the most naive brute-force algorithm.

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

    You remove duplicates from the vector a but still loop up to n, not to the size of a, accessing elements past its size. It doesn't necessarily segfault since the vector had size n+1 before, but It seems something problematic happens in that test.

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

      I don't think that causes WA though? Although he/she is reading elements out of bounds, no writes were performed so the data should not be corrupted, and more reads (albeit corrupted) could only cause more "bad" cases to show up, hence this issue should not lead to false positive.

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

        I also think so. I mean, well, I am not doing anything to the out-of-bound indexes, and changing it to a.size() causes TLE3

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

Can D be solved using binary search ? If yes can anyone share their approach?

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

    Try greedily defeat more monsters, so we need to binary search how far we can reach.

    Suppose we need to defeat K monsters and the highest power among them is P, we need to have at least one hero with p>=P and s>=K, which could be precalculated, in such a form: maxp_i = the largest power among heros which has s>=i. Thus we could easily check whether maxp_K>=P.

    Binary search such K and get the answer, to find P, is a problem of RMQ,use ST.

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

    Yes, there is a way. First sort all the heroes by power. Then create an array of suffix endurances for the sorted array of heroes. Suppose you have to kill k monsters on a particular day. Then find the maximum of those monsters and do a binary search on sorted heroes to find the suffix which includes all the heroes that have sufficient power to defeat the k monsters. Now, look at the maximum endurance of that suffix which we already calculated. If this endurance is at least k then we can kill k monsters. So you can check for each k whether we can kill k monsters or not in log(N) time.

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

no systest?

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

Help needed in Problem E

My approach is getting WA on test case 6 and I don't know why. Please can someone tell me why it is coming wrong.

My Approach :

I will try to make all possible prefixes for A(first person) i.e. (from 0 to N) where N = k1+k2+k3. I have maintained a set of elements for all three of them. Now suppose prefix of A is "i", so I will remove all the elements less than equal "i" in the set of first, second and third person and for it, I am maintaining the count in a variable name "taken". Now the problem is to solve for B(second person) and C(third person), and this will be equal to the minimum of the count of (elements in C which smaller than the largest element in B) and (elements in B which bigger than the smallest element in C) this can be done using BIT(In which I delete the elements according to the prefix). Note that I don't have to give the remaining elements of A to B and C first and do the computation as we can assume that A was given to them in the correct order.

So the final answer for the prefix "i" = taken + "remaining element in A(as he has to give it to other)" + min(element B give to C, element C give to B). And the minimum of all the prefixes will be our answer.

My Submission

Thanks in advance!!!

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

    Hi, check this case:

    10 10 10
    10 29 14 28 18 9 20 7 23 22
    30 19 2 25 12 17 8 15 11 21
    6 13 5 1 4 16 3 24 26 27
    

    The answer should be 18. Hope it helps.

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

E can be solved using dp.But some people solved it using binarysearch,how to solve it using binarysearch?

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

    And also How to solve using segment tree because I have seen some has done by segmeent tree

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

    using dp mean using LIS or something else?

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

      dp[i][1] means the smallest cost which all [1,i] number return to its correct position and the i-th number(which is exactly i) belongs to the first Programmer.

      dp[i][2] means ... belongs to the second Programmer. dp[i][3] means ... belongs to the third Programmer.

      the ans is the smallest number among dp[n][1], dp[n][2] and dp[n][3].

      if id[i]==1 and you want to let it still belong to the first Programmer, it cost none. Otherwise you will cost 1 unit.

      int id[200005], dp[200005][4];
      
      int main() {
          int A, B, C;
          scanf("%d%d%d", &A, &B, &C);
          for(int i = 1, ai; i <= A; ++i) {
              scanf("%d", &ai);
              id[ai] = 1;
          }
          for(int i = 1, bi; i <= B; ++i) {
              scanf("%d", &bi);
              id[bi] = 2;
          }
          for(int i = 1, ci; i <= C; ++i) {
              scanf("%d", &ci);
              id[ci] = 3;
          }
      
          int n = A + B + C;
          for(int i = 1; i <= n; ++i) {
              if(id[i] == 1) {
                  dp[i][1] = dp[i - 1][1];
                  dp[i][2] = min(dp[i - 1][1], dp[i - 1][2]) + 1;
                  dp[i][3] = min(dp[i - 1][1], min(dp[i - 1][2], dp[i - 1][3])) + 1;
              } else if(id[i] == 2) {
                  dp[i][1] = dp[i - 1][1] + 1;
                  dp[i][2] = min(dp[i - 1][1], dp[i - 1][2]);
                  dp[i][3] = min(dp[i - 1][1], min(dp[i - 1][2], dp[i - 1][3])) + 1;
              } else {
                  dp[i][1] = dp[i - 1][1] + 1;
                  dp[i][2] = min(dp[i - 1][1], dp[i - 1][2]) + 1;
                  dp[i][3] = min(dp[i - 1][1], min(dp[i - 1][2], dp[i - 1][3]));
              }
          }
      
          printf("%d\n", min(dp[n][1], min(dp[n][2], dp[n][3])));
          return 0;
      }
      
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can you plz explain the transitions?

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

          dp[i][1]=dp[i-1][1]+cost(i,1); dp[i][2]=min(dp[i-1][1],dp[i-1][2])+cost(i,2); dp[i][3]=min(dp[i-1][1],dp[i-1][2],dp[i-1][3])+cost(i,3);

          cost(i,j) means the cost if let the i-th problem be solved by the j-th programmer. Easily to know that cost(i,j)=1-(id[i]==j).

          dp[i][1] from dp[i-1][1] means let [1,i] problems all be solved by programmer 1.

          dp[i][2] from dp[i-1][1] means let [1,i-1] problems all be solved by programmer 1, but the i-th problem start to become be solved by programmer 2.

          It means when you start to assign i-th problem to programmer 2, you cannot assign all j-th problem (j>i) to programmer 1.

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

Can anyone confirm whether my approach for D is correct.
Sort the soldiers with inc power. For every ith monster, do B.S and find the soldier whose power >= power of monster, let be at index idx, then I will choose the soldier with maximum strength from index idx to n (as all soldiers after idx have greater power than idx). Let's call this soldier as 'X'.
I will kill as much monsters with this soldier as I can. Now two case arise-
1. Number of monster killed by x becomes equal to its strength, i.e., x.killed == x.strength
2. It's power is less than current monster.

For the first case I will increase the count of day and again iterate as done in first step.
For the second case, I will B.S and find the soldier whose power >= power of monster, and has the most strength(among those having power greater than the monster), let's denote it by 'Y'.
Now 2 conditions arise,
1. x.killed < y.strength For this case I can safely say that instead of chosing X in the first place I could have chosen Y and killed more monsters than X, so I update my current soldier from X to Y (as X.power=Y.power, X.strength=Y.strength).
2. x.killed>=y.strength. For this case I increase count of day , udate my X and iterate forward(X.power=Y.power , X.strength=Y.strength, X.killed=1).
I am getting WA for 2nd test case.
Here is my solution : 64836864

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

The color of the name seems to be wrong

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

Does anybody have a $$$O(n)$$$ approach to solve D?

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

    I don't think an O(n) solution is possible for this problem. O(nlogn) is needed at least.

    UPD: oh there is a clever O(n) solution. watch roll_no_1 's comment.

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

    You are also Chinese, so you can see this.

    https://www.cnblogs.com/KisekiPurin2019/p/11854682.html

    You can use dp to get the highest power of heroes which has at least i endurance.

            scanf("%d", &m);
            for(int i = 1, pi, si; i <= m; ++i) {
                scanf("%d%d", &pi, &si);
                p[si] = max(p[si], pi);
            }
    
            for(int i = n - 1; i >= 1; --i)
                p[i] = max(p[i], p[i + 1]);
    

    p[i] is the highest power which can beat i monsters in just one day.

    and then you can use greedy, each day try to move as more as possible.

            int i = 0, j = 0, rmq = -1, ans = 1;
            while(j < n) {
                ++j;
                rmq = max(rmq, a[j]);
                if(p[j - i] < rmq) {
                    if(rmq > p[1]) {
                        ans = -1;
                        break;
                    } else {
                        i = j - 1;
                        ++ans;
                        rmq = a[j];
                    }
                }
            }
    

    It means you have already beaten i-th monster, and you want to beat the j-th monster, today you move j-i blocks so the highest power is p[j-i], if p[j-1] < a[j], you need to wait until tomorrow and use your highest power hero p[1] to try to beat it.

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

Does anyone know about this anomaly

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

What was the approach for D apart from Segment Trees/Sparse Table ?

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

    Sort by endurance and find for every endurance suffix maximum instead of using segment tree, and just compare maximum of monsters with this suffix maximum

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

    you sort array of pairs <endurance, power>. Then you try to kill in one day as much as possible so you iterate through $$$a_i$$$, count the number of monsters you want to kill this day as $$$cnt$$$ and memorise the most powerful monster this day as $$$max\text{_}pow$$$. You go further and further until there is a hero with $$$s_j \ge cnt$$$ (it can be checked by $$$lower\text{_}bound$$$) and a hero with $$$p_j \ge max\text{_}pow$$$. To check the last condition you can look at max hero power on suffix $$$[j..m - 1]$$$ and you can do it in $$$O(1)$$$ by precalcing an array $$$max\text{_}suf$$$ where $$$max\text{_}suf_i$$$ is the maximum power of hero in suffix $$$[i..m - 1]$$$ in sorted array

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

    Why don't you read above there have been atleast 10 comments about D solution !!!

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

My Screencast for this round.

https://www.youtube.com/watch?v=g5n6eW7uwVY

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

Jesus! Where is the solution(

ok. i just want to know how to solve problem G

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

 UMMMMMM!!! OK XDD

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

I have a question about the problem D. In this question,a special example

Input:

1

5

1 2 3 4 5

3

1 10

2 10

5 1

for this example,the right answer should be 4,not 5.And I found that a lot of the output through the AC code was 5.Why?

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

    I found that some code can't even pass the simple data below: 1 2 1 2 1 2 2 Some of them AC code output -1,I think the background test data is too weak.

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

    s_i should be less than or equal to n, so {1, 10} and {2, 10} are invalid inputs

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

Can anyone explain solution of F briefly? TIA

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

Editorial?

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

When will the editorial of the problems be posted?

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

How about editorials???

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

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

Color display still not fixed ?

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

I can't see my friends standing of this contest. (It's not for sign in problem)

Let me know if I only facing this problem...

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

Why Difficulty of this round in Problemset is None

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

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

Please also include pwild as the 5th place winner, we had the same penalty.

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

    Whoops, sure. Funny enough my script got pwild into the rus version of the table and you in the eng one :D

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

      I was wondering why I got a message saying I was mentioned in some topic, but then not actually finding my name in the text.