By BledDest, history, 4 years ago, translation, In English

Hello Codeforces!

On Oct/11/2020 12:05 (Moscow time) Educational Codeforces Round 96 (Rated for Div. 2) will start. Note that the start time is unusual.

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 6 or 7 problems and 2 hours to solve them.

The problems were invented and prepared by Adilbek adedalic Dalabaev, Alex fcspartakm Frolov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

UPD: The editorial is here.

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 WZYYN 7 186
2 137_345_2814 7 194
3 jiangly 7 200
4 LayCurse 7 203
5 dreamoon_love_AA 7 258

Congratulations to the best hackers:

Rank Competitor Hack Count
1 ViciousCoder 100:-9
2 ManasG 45:-13
3 Valera_Grinenko 57:-40
4 AhmadEbtihal 36:-3
5 fstzyh 38:-9

858 successful hacks and 2258 unsuccessful hacks were made in total!

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

Problem Competitor Penalty
A sevlll777 0:01
B jkchen 0:03
C alireza_kaviani 0:03
D jkchen 0:12
E MagicSpark 0:05
F LayCurse 0:36
G MagicSpark 0:36

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

| Write comment?
»
4 years ago, # |
  Vote: I like it -14 Vote: I do not like it

This unusual time makes me unusual :(

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

4AM for me :(

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

notice the unusual time getting usual

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

    which can be a good thing for many (and a very bad thing for some)

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

why unusual time for ECF...2AM

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

Hmmm.... from Edu 46, every Announcement blog was authored by pikmike and he was always included in the problemsetters' tab. Did he get angry from all the downvotes from last round? The last round was pretty great problem-wise, learnt a lot, especially from problem G.

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

Note that the start time is unusual, is getting usual to us :)

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

No vovuh , Roms , Neon and awoo! Are they okay?

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

    vovuh, Neon and pikmike are participating officially in the contest this edu is based on.

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

my hope to return a cm

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

Normally unusual timings is due to a live contest happening at the same time. Is there any reason this time?

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

Lunchtime for me :(

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

    Where do you live and what time will be in your country at the contest?

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

ECF and opencup are at the same time, not cool

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

I will be doing online class and contest together. Shouldn't miss a single contest in this quarantine <3

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

    do you have classes on sundays?

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

      Yes, we have class everyday except friday in Bangladesh.

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

        Friday is special day for Muslim. We are majority Muslim in our country. So government make Friday off day for us. Such as Sunday is Holiday in your country.

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

The timing is great for me. Thanks :)

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

Can anybody explain me what does solution hacking means? Thanks in advance.

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

    Once the 2-hour problem solving round is over, participants have the option, to see the solutions submitted by other participants and try to generate possible inputs, upon which these solutions might end up giving incorrect outputs. This is what hacking means. All of this has to be done in a 12-hour hacking phase just after the contest. Once this 12-hour phase is over, solutions are re-judged based on all the hacks generated. Hope this helps!

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

Great start time for chinese participants:D

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

    Same here in Korea.
    it's 18:05 (UTC+9)

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

    For Japanese too. :) (start at 18:05)
    Recently many contests were held at 23:35(UTC+9), in which is difficult for me to participate.

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

2 days Back to Back Contests

10 October 2020 HHKB Programming Contest 2020 Codeforces Global Round 11

11 October 2020 Educational Codeforces Round 96 AtCoder Regular Contest 105

Great for learning

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

I think there should be more contests of this Asian timezone. Maybe there should be two types of contests for Europeans and Asians.

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

11 minutes left time to be ready : )

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

Will BledDest be conducting the future rounds as well ? He's been conducting the last 2 EDU rounds too.

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

    He has actually been conducting the last 79 edus.

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

Please, less ad-hoc.

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

    please graphforces

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

    C and D without educational worth.

    C is just "try it, should work...somehow", D is kind of edgecase hunting.

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

      Nah, C was kinda cute. To minimise the end value, we had to keep as many smaller digits as possible was my conjecture (which I indeed took a few minutes to prove after a guess submission). The solution (I think) was to take the biggest two values and perform the ceiling operation and then continue. D was quite great too if we (at least I) didn't misinterpret what the problem statement. I thought E could be something to do with segment trees and inversions but that didn't end so well for me implementation-wise.

      I looked at your submission for C and it was kinda hilarious to see your struggle in comments. Well done though!

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

        I just recalled those two problems, and still, I think I did not learned anything from them.

        In C you see the intended solution by coincidence, or you do not. If you do not come up with the idea to simply add the two biggest values you'll get stuck at this problem. Or find some other algo which coincidently works, too, like mine. But for somebody who did not solve C the thing you get is "There is nothing you can do. Solve more problems, mayby then someday you'll get the intuition to have the right idea at the right time."

        And problem D is basically the same. You find the right pattern by blindly trying some pattern. Or you do not find it. I found the three points given as hints in the tutorial within like 10 minutes. But still did not found a way to make it a working algo for like an hour. And afterwards, just like in C, absolutely no knowledge of what I could have done differently or better.

        That might be nice riddles, but from my point of view no problems to educate anything.

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

scoring?

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

    all problems have equal weightage in educational round!

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

I am eagerly waiting to see the test case no:2 of problem D,,,huh.

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

Idea behind E?

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

Contest Finished.

Can we discuss the problem before system judge?

I have not too much ideas about F&G

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

How to solve D?

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

How to solve D????

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

    111011 -> [3, 1, 2]

    delete -> minus 1

    remove prefix -> delete first number

    Then try best to maximize the operation

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

    two pointer concept.

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

    Maintain an array of lengths of consecutive elements. If the first prefix length is greater than 1 (>1), then we can remove that prefix and increase the number of operations. Now if the prefix length is equal to 1 (==1), then search for the first length in the array that is greater than 1 and reduce it. If such length is not found, remove the last length from the array (maintain 2 pointers one left and one right and reduce the right pointer).

    Example :- 1 5 10111

    After 1st operation -> 011

    After 2nd operation -> 1

    Thus 3 operations are required.

    A counter example as to why we should reduce from the first large prefix instead of the largest one is here

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

      Now if the prefix length is equal to 1 (==1), then search for the first length in the array that is greater than 1 and reduce it.

      Please tell me wouldn't that make the complexity n*n. It tried the same thing but got tle on test 4.

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

        Just keep pointer to last element that is greater than 1 and shift it right if necessary (do not search for it from the start every time).

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

        You don't have to search starting from the first element always. Suppose your at 2nd element in [1,2,2,3]. Now, after reducing that, you only need to move forward in the array because the previous entries will be <=1. This can be done using a variable to store the current reducing index and incrementing it accordingly.

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

          How can we know that the next value is >= 2?

          Example: [1, 2, 1, 3], if you are at the second element

          then you will decrement the 2nd element and it will be [1, 1, 1, 3] now if you increment it by one it will be on the 3rd element which is 1. But reducing 1 isn't correct, the correct one is to reduce 3.

          So how to increment it?

          Please I am stuck here for several hours.

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

            Suppose your pointer was on the 2nd element, now you have to increase until it becomes >=2. If it is not possible, then u just reach the end of the array.

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

      I used the sae concept but getting WA on 252nd test : https://codeforces.net/contest/1430/submission/95251105

      How do I figure out a test where it fails ?

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

        Try reading the comments to find any test cases that your solution may fail. I don't think there is a way to access that particular test.

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

          I got it. When the current value if "1", I was trying to make up for it by using the element which is the largest in range (i+1,N) which is not always optimal , better option is to use the element closest to the current index (on its right) . Thanks!

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

      Why is it necessary to find the first greater than 1 segment ... If I find the largest segment everytime and reduce it.. won't it work ?

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

      In case of prefix length = 1, instead of looking for the first length > 1, I looked for the largest length substring of the same value and reduced it's length by one but I got WA using this approach. Can you help me? My submission

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

Problems just awesome in this contest.

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

How to solve E?

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

    Have an vector of stack of size 26 where u push each character to respective bucket initially. Now we know that the first character has to reach the end. But the important thing to notice is that only the last occurence of the first character is required to reach end to save operations, that is why we maintain a stack to get last occurence.

    Now if we know that the last occurence of ith character is at position j, we also need to know how many of the characters from j to n-1 have already been push to right and for that we use segment Tree/BIT.

    So at each postion ans += n — 1 — (no. of char in [j,n-1] already pushed) — lastest position of that char

    Heres my Submission

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

      Could you explain why do we need to know the number of char already pushed? And how about handling the chars that has index larger than n/2?

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

        That is because set of character after the last character given in the input are already in reverse and we dont need to consider them. It would be better to explain with an example.

        Lets say we have the string: icpcsguru

        First move: We move the i at postion 0 to the end and get cpcsgurui. moves=9-1-0=8

        Second move: We move the c at position 3 to end(after u) -> cpsguruci. moves=9-1-3=5

        Third move: This is the important one. Here we move the p at position 2 but the moves wont be 9-1-2, instead it would be 9-1-2-1=5.

        This is because the c ahead of p is already moved to end and this is exactly why we need a range query from j to n-1 to get how many are moved to end.

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

          Oh I see it now. You were like try to bubble the chars from the left to right, one by one. Thanks.

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

Why did you not bold 'prefix' in D :(

delete the maximum length prefix consisting of the same characters...

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

    Ah, damn it... This is where most of us went wrong. Most of us did indeed solve a different version of this problem correctly.

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

      I tried for over 1.5 hrs but couldn't come up with a solution for the "different version" of the problem.

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

    wait, I missed that too... :(

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

I misread B and thought that only adjacent swaps were allowed.

(Sorry for the edits)

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

Helps for Problem D please

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

    precompute an array of sizes of chunks of 0s and 1s for [0, 0, 0, 1, 1, 0, 1, 0, 1, 1] -> [3, 2, 1, 1, 1, 2] now in each step first chunk would be removed anyway but we need to remove 1 other element before that, choose the chunk either after it or itself that has size > 1, if theres no such chunk remove the last element

    Since we never delete a chunk of size 1 from middle, it is ensured that two chunks are never merged. Hence we will always get the optimal answer.

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

      I used nearly the same approach. But when there is no chunk of size >1 then I just add (remaining unprocessed elements+1)/2 Here is my submission.

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

      I actually did this exact thing .. You would see if you go through my last two submissions .. I now want to figure out where it went wrong

      Upd : I got the bug .. actually I thought to use the first non one value and hence used a priority queue to keep the minimum next indices avalaible for operation only to realize now that we get a maxheap as a default.. my bad.. Got the same code accepted Now. Thanks for replying and help anyways :)

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

What on earth is Test Case 2 for D ?

UPD : my greedy fails for 5 10111, ans should be 3, not 2. Optimal way is to take 5th character first.

Damn, it seemed so obvious, the guy who set this problem is pure EVIL!

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

    Exactly...Here is my approach.....

    If prefix has more than 2 same characters then 1 operation consists of removing the first character and then the remaining prefix...this way we delete the minimum we can after every operation. Also if s[i]!=s[i+1] then we jump to s[i+2] after deleting si and s(i+1). This can be proved to be true by some casework...but I dont know why this greedy approach is failing.

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

      well i understood why this approach is wrong in last second consider 101111

      according to ur algorithm answer is 2 ! where u can get answer 3 by erasing 3 on first operation and erasing 2 on second operation and then erase 1

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

        so 3 operations in total

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

          My solution gives 3. Can you please have a look at it?

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

            I stress-tested my solution and got some tests where my code fails:

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

    1 7 0100010

    You can try this case, my solution was giving wrong answer on this case. May be you might get your mistake. The correct answer is 4.

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

    I figure what's wrong when my first submission

    I maintain two index, the head and the index of number bigger than 1.

    It's important to notice that the second index must >= the first index.

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

this contest actually had a really good combination of problems ! neither too easy , nor extremely tedious . Thanks BledDest for the contest

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

What hurts more?

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

    If you use O(n^2), you will surely get TLE. I also copied code from GFG though and get TLE on test cae 41 :P https://www.geeksforgeeks.org/minimum-number-of-adjacent-swaps-to-convert-a-string-into-its-given-anagram/

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

    Getting TLE on test case 41 while simultaneoulsy on call with GF with she breaking up wid ya at the same exact moment or vice versa whatever minimizes your mood. My guess is you probably got lucky with both events not happening at the same time....If even luck did not favor you on that...then oh boy.... that oughta hurt (In Matthew Mccounaughey's voice)...good luck xD.

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

      This is what happens when you are already overthinking and you start to overthink your overthinking. PS: You are funny!

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

please tell me why my answer for B is false this is my answer:

include<bits/stdc++.h>

using namespace std;

int main(){

int t;

cin>>t;

while(t--){

    int n,k;

    cin>>n>>k;

    int a[n];

    for(int i=0;i<n;i++){

       cin>>a[i];

    }
    int kk = sizeof(a)/sizeof(a[0]);

    sort(a,a+kk);

    int i=2;

    while(k--){

       if((n-i)>-1){

         a[n-1]=a[n-1]+a[n-i];

         a[n-i]=0;

         i=i+1;

       }

       else{

         break;

       }


    }

    cout<<a[n-1]-a[n-2]<<"\n";
}

}

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

    I think if n=1 then your a[n-2] will become a[-1]. Maybe that might be the mistake. You should only write a[n-1] as the answer because a[n-2] is already zero.

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

    try using long long instead of int, integer overflow takes place if you take int.

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

Is there a greedy approach for D ?

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

why my solution got accepted after changing int to long long https://codeforces.net/contest/1430/submission/95208979

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

Anyone can tell how to solve F & G ?

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

    F is DP

    $$$dp[i][j]$$$ = minimum cost (in bullets) to beat $$$i$$$ rounds (and start the next round) with $$$j$$$ bullets remaining in your magazine.

    Note that since $$$j \leq 10^9$$$ you should use a map/associative array for that dimension.

    The initial state is $$$dp[0][k] = 0$$$. Each state can be the parent of up to two states, one with $$$j < k$$$ (no reload after round) and one with $$$j = k$$$ (reload after round; only transition to this state if you have enough time). A state may also "dead-end" if it is impossible to beat the current round from it; if all states dead-end the answer is $$$-1$$$.

    This fits in $$$O(n^2)$$$ or $$$O(n^2 \log)$$$ as the number of states increase by at most one each round (the $$$j = k$$$ state may create a new $$$j < k$$$ state, while the $$$j<k$$$ states only "move" about or merge into the $$$j=k$$$ state)

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

Can anyone tell me why this O(nlogn) solution for E gives TLE at test 41 solution link

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

D was EVIL :(

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

Is there any other way to solve E without using fenwick tree/ segment tree ?

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

    count inversions any other way (merge sort , set -order_of_key)

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

    use pbds if you are using c++, 95257988

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

      AjaySabarish can you explain the logic of E.

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

        For each position, we know what caharacter should come there, we have the initial string, so each time it is optimal to move that character which comes first, for example cdad, first position should be occupied by d, there are 2 d's but it's optimal to move the d in the second position to first, but string changes when we do that, it becomes dcad, if you notice all elements before the moved position, their index increments.So we can store the positions of all characters and every time we just have to know the changed position, which is just the number of elements greater than the current position that have been already moved, we can solve it using pbds ordered_set

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

    It can be done without segment/fenwick trees. Because its a character string, we can keep prefix/suffix frequency arrays for both initial and reverse strings and maintain the answer. You can look at my code for reference.

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

hi, can anyone tell me, what is hacking? and did it give score also?

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

    not in educational and div.3 rounds.

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

      Does that mean an unsuccessfull hack would have no effect on your final score?

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

        In Educational and Div.3 rounds neither successful nor unsuccessful hack gives you extra points. But in regular Div.2 and Div.1 you get +100 points for each successful and -50 for unsuccessful hack.

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

Can C be solved using heap? This solution gave TLE but I just to know if there is any way to optimise it or if it can't be solved using a heap. This solution without heap worked correctly.

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

    I would give u a better approach .. Just use the max 2 possible values each time and then work yourself on a case or two. You would get to know that you would always end up at 2

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

First I convert 1000111000 to [1,3,3,3] then if the chuck is greater than one than i add one to my ans , if the chuck is equal to one than i remove one from the biggest chuck remaining , 95255021 can someone point out what's wrong with the approach

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

    An example test case is -> 1 13 1010010101111

    Your approach gives 6 while the answer should be 7

    The problem is that we should not remove from the biggest chunk because we may exhaust it early. The ideal way is to remove from the first chunk which is greater than 1. That way we can optimally utilize the chunks. In the example, it exhausts (1111) which could have been used for 6th element while we could have reduced the (00) for the 1st element.

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

      thanks man. should have seen this. at this rate someday my rating will be lesser than the number of contests I participated.

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

Prob C hurts me a lot. I even don't have time to catch up Prob D.

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

    Dude I overcomplicated my C because I thought the solution to C should not be so obvious. Now I see that a brainless greedy works. -_-

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

My screencast of getting 7th place [assuming I don't FST], along with solutions to all problems is being uploaded to my youtube channel. Youtube should finish processing it in 20-30 minutes or so. If you want to see it as soon as they finish processing, you can turn on notifications. Good morning and thanks to the authors for the cool problems! :)

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

Nice Problemset. Was E a standard question of Fenwick Tree ?

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

Why is this brute force wrong? (PROBLEM A)

#include<bits/stdc++.h>
using namespace std;
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--){
        int n, i, j, k;
        cin>>n;
        int flag=0;
        for(i=0; i<=334; i++){
            for(j=0; j<=334; j++){
                for(k=0; k<=334; k++){
                    if(3*i+5*j+7*k==n){
                        flag=1;
                        break;
                    }
                }
                if(flag) break;
            }
            if(flag) break;
        }
        if(flag) cout<<i<<" "<<j<<" "<<k<<"\n";
        else cout<<-1<<"\n";
    }
    return 0;
}
»
4 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

For some reason, I'm really bad at educational rounds...

My last four ed-rounds
And this one will be even worse (expected -64)

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

    The problem for loosing rating in this contest has huge role of your mindset saying that "I will loose rating from previous pattern ,making you feel pressure and under pressure u don't do well". Thinking it to be any normal contest and being cool , you might have performed better.

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

Sweet
Slightly over an hour since the end of the contest and already 500hacks.

I'm not complaining though as it may seem. Just noticing a funny fact

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

Anyone else used Dp for problem A? XD

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

    I thought about something like this initially. But decided that it is quicker and less error-prone to write brute-force that should converge quickly

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

A lot of successful hacking attempts for A & B. It's sad.

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

    My solutions got hacked in both. So sad.

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

      Do you have any reasons why we got tle in B Especially java users? while looping backwards*.

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

Does anybody have proof for the fenwick tree solution of E. Why wouldn't there be a case where we need lesser number of moves than taking it to the last possible position.

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

    So, here is my solution : First take the reverse of the given string and try to get all characters into position starting from the last.

    Some sort of proof for this : It is always optimal to choose the rightmost matching character in the original string to swap and get to the final intended position. Assume it takes X moves for rightmost character to get into final position. Now any other character Y will take X + dist(rightmost character, Y).

    Now, on why it is better to start fixing from the end of the string : When we try to fix some position before fixing the positions to the right of it, then this character might get displaced once again when some other to the left of the fixed character needs to go to the right of it.

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

      is it necessary to move from right to left

      i reversed the string and tried moving from left to right

      getting wrong answer on test 41.

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

        It should work. The logic may slightly change though like you must take the leftmost matching character instead of the rightmost etc.,

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

I want to know D's solution, shouldn't it be traversal string simulation operation? I have seen a lot of AC codes, they all have found a certain pattern, can someone tell me this pattern?

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

    Let's say there are various segments of same elements, so one thing that you can see clearly is that you don't want to merge two segments, right? Now if the segment at front has size 2 or greater you can simply delete one of its element and then delete this segment. But what if our segment at front has size 1. In the first operation you want to delete a number other than this segment, so you can do it by deleting from any segment after this and size greater than 1. It will basically create a suffix with ones only and you just want to find the size of this suffix. the answer will be number of segments initially — (suffix length/2).

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

      mafailure Can you please explain the solution w.r.t to 1000100 ?

      If I first take i = 7 string becomes 00010,

      Now if I take i = 1 string becomes 10

      Now if I take i = 1 string is empty

      ans is 3, but it should be 4, can you help me with that?

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

        make a vector of lengths, in this case it will be v={1,3,1,2};
        now first length is 1 so we need a length>2 ahead in the vector or the last length==2 if any of the condition met then we can reduce that length by 1
        if both these conditions are false then we have to forget about a length
        for clarity see this https://codeforces.net/contest/1430/submission/95243326

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

          what do you mean by "last length is 2" ?

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

            if we encounter with length==1 then we need a length of 3 or more or the last length 2 or more

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

              so in 1000100 I can take i = 7 right? since last length is 2

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

                hmm

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

                  but that would leaves us with string 00010, now when i just take i = 1, string becomes 10, and now the answer is only 3, but when I take i = 2 in the first operation it can become 4, so how does it work ?

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

                  here our vector of length will be v={3,1,1} now first length is 3 so it is safe then we have 1 and none of the condition are met so we have to drop the last length that is so ans will be 2.. idk what do u mean by i

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

                  pinged in DM

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

Not noticing the unusual time made me miss the contest.

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

    10 downvotes for expressing my mistake and feeling sad for missing a contest, ouch.

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

Can someone explain the "flow" solution for G?

I only know the bitmask dp solution.

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

In fact, problem e is not difficult, but I don't have enough time to complete it. The slow hand speed is also one of my flaws. .

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

My solution is a perfect O(N) solution. But it got hacked for TLE. Problem A of this Educational round 96. 1430A - Количество квартир Kindly look for yourself and tell me why this happened @ BledDest adedalic fcspartakm Submission : 95203970

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

    python is too slow, change to c++

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

      Bro I submitted in PYPY3, that's supposed to be faster than Python. And since the complexity is correct there shouldn't be any problem in the language right? Like the setters should make sure it gets submitted in all languages if the required complexity is fulfilled

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

        Your code is taking 1247 ms for t = 1000 and n = 1000 for every t. Try it in Custom invocation.

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

          Exactly my point , given the complexity is correct which is O(N), It's showing TLE ie time taken is above 1 sec. Which shouldn't happen for the given values.

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

        You should calculate dp once for the max value of n = 1000. But you do calculate it every time.

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

          Yes, I thought about ,but considering the situation for T = 1000 and N = 1000 , it should be quite evident that O(N) should work

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

    This solution is O(tN) at best and on each iteration it creates at least six three-element dictionaries. Six million three-element dictionaries are not free

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

      Dictionary with 3 elements can be considered as constant, it occupies O(1) complexity , how does it matter??

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

    Hey, You can check out my PYTHON TEMPLATE for making your Python code run faster.

    Also, I have been a Python Coder for quite some time now, but sometimes even I have to submit a program in C++.

    Mentioned below are some areas for which you should not choose Python as a language to code your solution :

    (1) Recursion with a depth > 1000.

    (2) If you need to apply lower_bound or upper_bound on a set as Python doesn't support it.

    (3) String problems with the length of string > 1e5 and your solution is supposed to have a time complexity of nlogn.

    Hope this helps you.

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

Can somebody prove problem D solution ?

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

In problem D :

Why is it "always" optimal to pick just next chunk with more than one value and not any other chunk with more than one value , whenever we encounter 1 ?

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

    If you don't choose, the just next valid chunk will be erased at some step, thus not better than the solution.

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

Can somebody prove the solution to D ?

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

If someone has got a little free time, can they mind explaining to me dp approach for solving problem A. Thanks.

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

    A dp solution for such a problem would be based on the observation that if we got a solution for some n, then we can simply construct a solution for n+3, n+5 and n+7, each by adding that number to the set of numbers in the soluttion.

    So start at zero and go up to n. Foreach number if there is a solution, construct the next three soulutions and store them.

    This will finish after n loops with solutions to all numbers in range 0 to n.

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

Is there a way for java users to solve problem B, because I used Arrays.sort() and got hacked. Collections.sort() is even slower. If we use a priority queue then it has insertion and deletion time complexity of NLog(n) and is a min-heap so it will only work for some cases. So what is the alternative??

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

    Use mergesort Or sort Array of Object instead of Array of Primitives. Arrays.sort() uses quicksort for which worst case time complexity can be O(n^2) (only in case of primitve data type).

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

    HarnoorSta7 has already pointed out. So, we got a TLE because Arrays.sort(int[]) uses quicksort which can have a worst case complexity of O(n^2) when the array is almost sorted. Now Collections.sort(List) is indeed slow because of non-primitives but it is still O(nlog(n)) in worst case because it uses Tim-sort instead of quick sort. So, I think it would not be a TLE if we used Collections.sort(List) in this question.

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

      Thanks for the link. Java was a lie for me. All the java accepted solutions I saw are using Arrays.sort() for int. Let's see how many java users survive for question B after final testing is completed.RIP java users!!

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

    To avoid worst case of Arrays.sort() function for primitive data types which is O(n^2), first shuffle randomly the elements in the array then use Arrays.sort() function. The function which I use to sort the array is-

    static void sort(int[] A){

    int n = A.length;
        Random rnd = new Random();
        for(int i=0; i<n; ++i){
            int tmp = A[i];
            int randomPos = i + rnd.nextInt(n-i);
            A[i] = A[randomPos];
            A[randomPos] = tmp;
        }
        Arrays.sort(A);
     }
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody please tell me why my solution on problem A doesn't get TLE on a test with 1000 of 1's in input? This is kind of a max text and it's not even close to TLE (around 300ms).

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
    Hi
    Max cases: 1000 & worst test: 1000.
    loop1:
       break at worst case 1000/3 = 330 
       loop2
          break at worst case 1000/5 = 200
    
    • Your code at worst case: 330*200*1000 about 6e7 < 10e8 so it's fine.
    • Note:
    • Expected to be 10^8–10^9 simple operations per second, in C++ or Java.
    • Less for Python, about 10^7.
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But if I have 1 as n, my fors don't break at all.

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

        When u get the answer and b = false, the both loops will break coz of "&& B" in loops.

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

          Yes, but if the answer is -1 it wont

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

            You 're right, My apologies I was wrong. Hope you get the correct answer soon.

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

            When used "long long" instead of "int" in same code got TLE and don't know why. 95291943

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

I'm almost sure the intended solution for problem G doesn't involve Simplex, but if you know this method and you prove (or assume :P) that the coefficients found by the algorithm are all integers, you can get a really quick accepted.

Also, this solution should work fast enough even if $$$n<=100$$$ and $$$m<=n*(n-1)/2$$$

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

95241114 Why is this solution showing unsuccessful hacking attempt even though it shows compilation error in online IDEs?

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

    just so you know, in hell exists a special place for A-problem hackers!

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

      Nd there are some dumb people like you whose A-problem gets hacked...lol

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

        It saying the green pupil. just so you know it is infinity number of the way to hack every problem A solution.

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

95295302 Can someone tell me how to optimize it to have an AC. This gives TLE. I saw solutions of other people with the exact same method having AC. Please help! Thanks!

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

Can someone plz help me why my solution shows TLE for the Barrels problem of today's div 2 B Here's the link-https://codeforces.net/contest/1430/submission/95296320

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

Me after using x / 2 + x % 2 in rounding up in the questions

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

Please, can someone proof C solution? Thanks.

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

    We just need to proof that an answer less or equal to 1 cant exist. If (a+b)/2 rounded up is 1, then 1 <= a+b <= 2. Its impossible to get a+b <= 2 if n>=2, so the minimum possible answer is 2.

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

To not keep you waiting, the ratings updated preliminarily. In a few hours, I will remove cheaters and update the ratings again!

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

    As last contest. This way is really better. Thanks for improve CF continually.

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

    Can I ask a question? What does it mean to remove cheaters? According to my understanding, cheaters should be counted as zero points and kept in the rating change list.

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

    wait removing cheaters ? are you removing them manually or what ?

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

No idea why my submission for Problem B gives TLE (got hacked in the hacking phase)
Can someone please check?

UPD: Got it fixed. Arrays.sort() is the problem here. Aaah, this thing ruined my contest big time. Why you implement it via quick sort java. Whyyyyy? 
»
4 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Please upload the editorial..

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

In Problem A I used two pointer method.Like this

lp(i,mx+1)
	{
		
		j=0,k=mx;
		while(j<k)
		{
			
			if(i*3+j*5+k*7==n)
			{
				cout<<i<<" "<<j<<" "<<k<<endl;return;
			}
			else if(i*3+j*5+k*7>n)
			{
				k--;
			}
			else
			{
				j++;
			}
		}
	
	

But still got WA .Why?

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

    That loop stops to early while(j<k)

    It should be something like while(i*3+j*5<mx) because there is no reason why j must be smaller than k.

    And that is, because it is basically no two pointer problem, but a brute force.

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

editorial?

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

Where are the editorials?

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

Editorials Please BledDest

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

Is it possible to get all the test Cases for the problem from Somewhere. My Solution for D fails on 149th input of test case 2. If not it would be great if someone provides some good cases for checking the fault in my code . I have tried all the cases given in the comment section and all the outputs(from my code) have matched with their expected output.

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

    It's a bit hacky, but you can sniff the test case by hardcoding something like if (test_case==149) and print it out in a submission.

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

      It was a Cool Idea , I got the failing testCase and my error as well. Thanks a lot

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

Very happy to get First-AC at problem E&G.

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

Problem E was awesome.