By awoo, history, 2 months ago, translation, In English

Hello Codeforces!

On Jun/12/2022 17:35 (Moscow time) Educational Codeforces Round 130 (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 6 or 7 problems and 2 hours to solve them.

The problems were invented and prepared by 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:

Harbour.Space

Hey, Codeforces!

We are thrilled to announce an amazing work & study opportunity with Vodafone.

Vodafone Group has partnered with Harbour.Space University to offer Bachelor's and Master’s degree scholarships in Computer Science, Data Science, Cyber Security and Front-end Development as well as MBAs and work experience in one of the leading UK telecommunication companies.

Vodafone Group is opening a new technological HUB in Malaga, an international center of excellence dedicated to research and development of technical solutions, such as Secure Networks, 5G and 6G development, Open RAN, IoT, MPN & MEC and UCC for Vodafone Business, platforms and enterprise solutions.

We are looking for various junior to mid level positions (or senior) to fill in different fields such as:

  • Front-end Development
  • Full-stack Development
  • Backend Development
  • Technical Architecture
  • Enterprise Architecture

Harbour.Space

APPRENTICESHIP REQUIREMENTS

General Requirements:

  • High School Diploma or Bachelor's Degree with prior work experience
  • CV or LinkedIn Profile (your Codeforces rank has to be added to your CV)
  • Proficiency in English (Spanish is a plus)

Requirements for Frontend Developer:

  • At least 1-3 years of experience in Angular.
  • At least 1-3 year of experience working in React.
  • Strong knowledge of web platform fundamentals: HTML, JavaScript and CSS.
  • Design and implementation of low-latency, high-availability, and performant applications
  • Definition / construction of CI / CD pipelines using tools such as Jenkins, Sonar, Kiuwan.

Requirements for Full-Stack Developer:

  • Minimum 3 years of proven experience in platform development (CDI/DevOps based environment). With one or more of the following:
  • Java SE/ Javascript
  • Scripting languages, i.e. python, perl, shell scripts.
  • Proven experience in backend & frontend software systems & web applications.
  • Proven experience with HTPP, MQTT, LwM2M, Kafka, various databases (SQL and non-SQL).
  • Proficiency in cloud-native development.
  • Hands-on experience with CDI tools.

Requirements for Java Developer:

  • Industry experience with Software Platforms in Linux, on-premises and cloud
  • Solid understanding of server technologies
  • Strong academic knowledge and professional experience of software development: Java Enterprise, Oracle, Linux, Windows
  • Good understanding of system monitoring tools and automated testing frameworks
  • Experience with SQL, XML, JSON and CSV
  • Experience of providing and maintaining transformations and APIs for customers and partners
  • Good understanding of Databases – Oracle, MongoDB, ElasticSearch.
  • Good understanding of java frameworks, SpringBoot, Spring technologies
  • Good understanding of container systems (docker) and orchestrators (docker compose, Kubernetes) and messaging technologies, kafka, rabbitmq
  • Good understanding of Unix shell, Perl, python to perform automation and maintenance tasks and CI/CD environments
  • Educated to BSc degree level in telecommunications or related discipline with Software Development experience
APPLY NOW →

Good luck on your round, and see you next time!

Harbour.Space University

UPD: Editorial is out

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

»
2 months ago, # |
  Vote: I like it +53 Vote: I do not like it

Good luck for Everyone

»
2 months ago, # |
  Vote: I like it +14 Vote: I do not like it

Finally a Div2 Edu Round :)

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

    Sometimes the Codeforces community is crazy. Why is this normal comment being downvoted so many times? Can we stop this kind of "insane downvoting"?

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

      People just downvote / upvote like sheeps. If there is a single downvote they start downvoting it more. I dont care about Upvotes and Downvotes anymore :)

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

        Fun fact, a single downvote doesn't show. You need at least 5 for it to show, which is meant to deter sheep-like behavior. Ig your post just didn't resonate with a bunch of people, no clue why.

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

      You're right ! Agree with you

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

Maybe I am gonna be a pupil this time! Hope a nice problems.

»
2 months ago, # |
  Vote: I like it +24 Vote: I do not like it

I don't know why I like educational rounds so much.

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

    I tend to do worse on educational rounds for some reason, probably because I have trouble with 'classical' problems. I think edu is very high quality, and I'm impressed how many good problems they can come up with in such a short time frame.

»
2 months ago, # |
  Vote: I like it +31 Vote: I do not like it

hope for a good contest, not speedforces .

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

Good luck everyone! Удачи всем! Hemmäňize üstünlik!

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

All the best Everyone!

»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Good luck for Everyone

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

Geez, they don`t expect much out of the candidates, do they?

»
2 months ago, # |
  Vote: I like it -29 Vote: I do not like it

Yet, Another speedforces round!

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope to become BLUE at least today.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Do we get solutions of these questions after contest is over anywhere??

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

    Yeah! ...Editorial will be released after the end of contest where you can find the solutions to all the problems!

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, Editorial will be released after the contest :) It will have hints and explanations to each problem, along with the implementation.

»
2 months ago, # |
Rev. 2   Vote: I like it -30 Vote: I do not like it

It's annoying when you passed the given test and it fails on some other test case which you can't even see!!!

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

problem A is very easy but B I can't solve it XD!

»
2 months ago, # |
  Vote: I like it +8 Vote: I do not like it

I'll die doing C

»
2 months ago, # |
  Vote: I like it +32 Vote: I do not like it

C was annoying

but D was very great and nice

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I got C Idea in 30 minutes, then I spent 1:15 hours thinking of D but In vain.

    Could you give me a hint?

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

        I've already calculated this during the contest, what is the next step?

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
          Rev. 4   Vote: I like it 0 Vote: I do not like it
          for every index ask2(1,i-1)<ask2(1,i) you have to know what is this letter at index i ,so ask1(i)
          
          then you have a string like this 
          
          a??c????b???????d???????f?????n????
          123456789..........................
          what do you know about the letters between 2 and 3 ? 
          they are all a !
          
          what do you know about the letters between 5 and 8 ? 
          they are all either a or c !!
          
          and so on .. 
          
          • »
            »
            »
            »
            »
            »
            2 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Wouldn't this exceed the limit of questions if the string is like this?

            abcd...xyzabc...xyzabc....xyzabc...xyz..... and so on

            The generated string after the questions will be abc...xyz????????????.... and more '?' to n which will cause you to search for the 26 possibilities at each time of the n-26 letters.

            How did you overcome this problem?

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

              interactive = binary search

              • »
                »
                »
                »
                »
                »
                »
                »
                2 months ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                I have used kind of similar approach but getting nlogn complexity that is around 9000 query of type 2 which is not allowed how you overcome that.

                160345223: My submission

                Thank you

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 months ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  I think he meant to binary search the 26 steps not the whole string

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 months ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Just binary search on indices of already existing characters. (26). So take last index of each character, then your binary search will run with an upper bound of log(26)=4.7. so making (log(26)+1)*1000 == 5700 queries is enough. One extra query for checking if there is a non repeating character or not.

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

                  Oh okay thanks I don't know why but I have a bad habit that I just think of approach and implement if it works okay if not then I can't think more about the problem. I will try to improve it.

                  Once again thanks

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

    C is not annoying if solve it the right way:

    1) Initially drop all 'b' from both strings – if resulting strings are not equal then answer is NO.

    2) In initial strings find all occurrences of 'a' – k-th occurrence in first string should be less or equal to k-th occurrence of 'a' in second string. And similar to 'c' but it should be more or equal.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      this is exactly the idea i used

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I did exactly the same.

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

      My solution for C has O(Nlog(N)) complexity and it gives tle but some O(N^2) are also passing.

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

        I believe I can help you, I had the same problem on the last Div3 round. lower_bound(set.begin(), set.end(), sus_element) works in O(n) for some reason set.lower_bound(sus_element) works in O(log n)

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          From what I could tell the reason that lower_bound(set.begin(), set.end(), sus_element) works in O(n) is because std::lower_bound uses iterators to find each pivot. Added up, it takes O(n/2 + n/4 + n/8 + ...) = O(n) time.

          I think they explain it better

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Oh it's very important I will remember it. Now it got AC with it.

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Hello, thank you for the explaination. However, I did a similar idea and used set.lower_bound() and not std::lower_bound, but I TLE on subtask 2. May I know what is wrong with my code(https://codeforces.com/contest/1697/submission/160362579) ? Thank you.

    • »
      »
      »
      2 months ago, # ^ |
      Rev. 4   Vote: I like it 0 Vote: I do not like it
      can you explain more ....I solved it and got AC but my sol is not simple in implementation ....
      
      Complexity: O(NlogN)
      

      my solution

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

        Sure, the main idea is to consider operations as moving 'a' through 'b' to the right and moving 'c' through 'b' to the left.

        The logic of the first step is – we can't move 'a' through 'c' and vice versa. So we can initially check if the arrangement of a and c is correct.

        The second step – if there's a k-th occurrence of 'a' in first string that is righter than the k-th occurence of 'a' in the second string then we can't move that 'a' in the required position since we can't move 'a' to the left. Exactly same logic for 'c' and moving it to the right. If we see such occurrences then the answer is NO.

        If neither of 2 conditions above are true then answer is YES – it's because of the same logic from step 2 – we can move each 'a' and 'c' to the required position since we only need to move 'a' to the right and 'c' to the left and it's guaranteed from step 1 that 'a' and 'c' has the same arrangement as in the second string.

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Very nice implementation idea altgifted I thought same but was not able to implement it correctly. Had to go through a tough implementation :)

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

In normal Div.2 contests when I re-submit a problem that was previously accepted, I get penalty and the previous one gets skipped. But in this round it didn't happen when I re-submitted. Can someone tell me why?

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

    Because it's ICPC mode

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

      Does that mean the 2nd solution won't be considered? Sorry I'm not familiar with ICPC rules :(

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

        In ICPC mode contests all your accepted solutions will be judged, If for example you have submitted $$$k$$$ accepted submissions and the $$$i-th$$$ one gets accepted, you will get $$$(i - 1) × 10$$$ minutes penalties.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is today's C related to : https://codeforces.com/contest/920/problem/C ? How to solve C? T_T

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

    First, remove all occurrence of '$$$b$$$' and check if they are same. Second, find each occurrence of each non-'$$$b$$$' character in both $$$s$$$ and $$$t$$$. If it is a '$$$a$$$', it must appear in $$$s$$$ no later than in $$$t$$$. If it is a '$$$c$$$', it must appear in $$$s$$$ no earlier than in $$$t$$$.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What is the insight about deleting "b"'s?

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

        because '$$$a$$$' and '$$$c$$$' can't swap, so deleting '$$$b$$$'s can check if their number and order match.

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          got this one, oh and b's could be simply removed from way either left or right, it's "proved by solution" I guess. Thank you!

          i_emerge16 Thanks!

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

    It's more of a proof problem. I'm not sure tho.

    Hint
    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      can you pls explain your approach?

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        S--->T Because a cannot be swapped for c, each char 'a' in s and t must have the same number of char 'c' on the left and right sides ( sequence wise for every a in s & t) Second, we can't change ba to ab, thus for each a in s and t, no of b in left of a in s <= no. of b in left of a in t (sequence wise for every a in s & t). Finally, because we can't exchange cb to bc, thus for each b in s and t , no of c in left of b in s <= no. of c in left of b in t (sequence wise for every b in s & t).

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

        It's essentially the same with Aging1986's solution. But, I didn't think of deleting the $$$b$$$'s. Observe that $$$a$$$'s can only move to the right, while $$$c$$$'s can only move to the left. This means that when iterating from left to right, the number of $$$a$$$'s in $$$s$$$ must always be greater than or equal to the number of $$$a$$$'s in $$$t$$$. Similarly, the number of $$$c$$$'s in $$$t$$$ must always be greater than or equal to the number of $$$c$$$'s in $$$s$$$. Then, also notice that $$$a$$$'s and $$$c$$$'s cannot swap. Meaning, in between $$$c$$$'s, if they exist, there will always be the same number of $$$a$$$'s. Similarly, in between $$$a$$$'s, if they exist, there will always be the same number of $$$c$$$'s. That is why Aging1986 "deleted the $$$b$$$'s". I had a different way of checking that. Every time both the numbers of $$$a$$$'s or $$$c$$$'s, in $$$s$$$ and $$$t$$$, increases, I must check if the previous numbers of $$$c$$$'s or the previous numbers of $$$a$$$'s, respectively, is the same.

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

    I did it with prefix sum of "a", "b" and "c", and with Upper bound. It works very well. 160360256

    Just kinda sad I forgot if pos from (pos = upper_bound) is out of bounds, to print "NO\n" immediately, so I resubmited, and it got accepted 1 minute after the contest ended.. :( But I am glad anyway, because I learned something new. :D

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

Can anyone help with C?

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

    There seem to be more solutions to C. I'll explain mine.

    First, we need to make a few observations:

    1. both strings s and t should have equal amounts of 'a', 'b', and 'c'
    2. 'c' cannot be moved towards right in string s (So, each 'c' in s should be present towards the right of its counterpart in string t)
    3. 'a' cannot be moved towards left in string s (So, each 'a' in s should be present towards the left of its counterpart in string t) by doing the given operations.

    Let's start with the observation#2:

    To move a 'c' towards the left from index i to j(j < i), the range [j, i-1] should have all 'b's. Try moving each 'c' in s to its correct position in t. If we cannot move a 'c', we cannot convert s to t.

    Now, all 'c's should be in their correct positions(if possible)

    Similarly, with the observation#3:

    To move a 'a' towards the right from index j to i(j < i), the range [j+1, i] should have all 'c's. Try moving each 'a' in s to its correct position in t. If we cannot move a 'a', we cannot convert s to t.

    Now all 'a's should be in their correct positions(if possible)

    Since all 'a's and 'c's are in their correct positions, now we just need to check if all b's are there in their correct positions and determine the answer.

    Implementation:

    To check if a range contains all b's and make point updates while moving a character from one index i to j(the move is a direct swap of s[i] and s[j] and not actual swaps between adjacent characters to reach the destination), we can use Segment Tree with range query and point updates.

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

    hope my implementation using stack give you some hint :-160349549

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

      Can you once check what's wrong with this implementation of mine: here It's failing on 2164th test case in pretest 2.

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        before pushing (a,b)into stack we must check if any pair (b,a),(b,c),(c,b)is present on top then return no otherwise if top contains (a,b) then we can push(a,b). similarly for (b,c) to push(b,c)into the stack we must check (c,b),(a,b),(b,a)if any of these pair present then return no else if((b,c) is present on top then we can push (b,c) pair accepted code of yours:->160388847

»
2 months ago, # |
Rev. 2   Vote: I like it -48 Vote: I do not like it

Worst round since last Month.

Upd. Change my mind:

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Please explain the solution to the problem D; Thanks :)

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

    Double binary search. First binary search to find the point where a new alphabet first shows up in the string (counting from the left), and then, we iterate through the string from left to right. For each character of the string, we save the last occurrence of the letter, and to determine the unknown character, we do a binary search on the array of indexes of last occurrences to find the index at which the unknown character does not contribute to the number of distinct characters. This should yield a $$$O(26logn+nlog26)$$$

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

    We are going to use binary search.

    Imagine you are trying to figure out index ith, and imagine you already know all characters from 0th to (i — 1)th.

    you can add all the right most index of each character that you have found in an index array, this index size is at most 26. You are going to binary search on this index.

    let say you are considering index jth before ith. if from j to i — 1, the index at i already appears, then you have the same count from j to i — 1, and j to i, bc ith doesnt add anything new. So you can binary search the right most position where this is true, then you can find an index j that is the same with i. so each binary search check, you can check the count from mid to i — 1 and mid to i, mid to i — 1 can be updated after every ith, so it's free. If you can't find this then you can use the first query.

    the total used is at max 6 * 10, you only use 5 times in the binary search, at only use the first type when there's a new character.

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

    Shortly, you restore the characters of s from left to right. The first character is restored by query "? 1 1". For each of the next characters, let's ask if this character is new (by query "? 2 1 i"). If it's new, ask "? 1 i"; otherwise, find the previous occurrence of the i-th character with binary search.

    To run only 5 queries of type 2 in binary search, you can see that we are interested in segments of type $$$[last_c, i]$$$, where $$$last_c$$$ is the last occurrence of some character on the prefix we know.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Keep track of known letters and their last positions. Build the string up from the front by querying the entire string up to that position to find out if its a new letter (if it is then use query type 1 to find out what it is) otherwise do a binary search with the array of last positions to work out which letter it is.

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

D << C

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

E was a nice question with 2 parts to it. How to solve F though?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How to solve E?

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

      Connect a line between 2 points if you can possibly colour them as the same colour. Notice that this will result in a graph of disconnected cliques. The clique can either be colored with 1 colour or different colours for each point. Then, we can use DP to colour them.

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

        Will the connected componnets be atmost of size 3? My code gives WA on tc 4 can you tell me why

        Code
        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          Test 4 has a component of size 4 (a square which has its sides parallel to lines $$$y=x$$$ and $$$y=-x$$$).

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          At least put your code in spoiler or something :|

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        thx! I catched my error

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

    F is two sat . You can make some variable : (a[i]<=x) is true or false , (a[i]>=x) is true or false.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh wow, I didn't think of it that way.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I get that you could use $$$a_i <= x - 1$$$ or $$$a_i >= x + 1$$$ to deal with the first operation, but how do you go about the second and third operation?

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

        $$$a_i+a_j \ge x$$$ iff $$$\forall y$$$, either $$$a_i \ge y+1$$$ or $$$a_j \ge x-y$$$ should hold.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve F?

»
2 months ago, # |
  Vote: I like it -90 Vote: I do not like it

Since D requires stupid observations and E,F are unsolveable, todays edu was like speedforces.

Usual edu rounds where mostly implementation based problems, I liked that.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What's the observation for D ?

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

      :v No observation at all! Find the all position such that $$$cnt(1, i - 1)$$$ < $$$cnt(1, i)$$$ and do query of type $$$1$$$ for that position $$$i$$$. After that, do a for loop from $$$1$$$ to $$$n$$$ and take all the last appearance of characters that occur before $$$i$$$ and binary search on it.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    A and B make this round somehow "speedforces". But D has a clean solution and I think it's a good problem. I have no idea whether C has a clean (and PROVED) solution because my solution for C was terrible.

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

How to solve D? was D binary search on last unique characters encountered so far?

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

    That is true, the total number of 2 Query will be less than log(26)*1000, Do you search the last 26 characters[a-z] instead of all the previous characters?

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

      For each character ch encountered, I stored its latest index, then binary searched on that vector indices by quering them. But I'm going wrong somewhere. the vector kind of vector<pair<int, char>> where v[i].second is unique. and v[i].first is latest index where v[i].second appears

»
2 months ago, # |
  Vote: I like it +13 Vote: I do not like it

What is test case 10 of E?

»
2 months ago, # |
Rev. 2   Vote: I like it -58 Vote: I do not like it

A and B are TOO EASY as Div.2 AB.

But for Div.2 level contests you don't expect this kind of easy problems so you will spend some time on thinking again about A and B before submitting them, but this will cause your ranking become low and it is VERY disturbing.

  • »
    »
    2 months ago, # ^ |
    Rev. 3   Vote: I like it -36 Vote: I do not like it

    Never downvote a post due to the reason "there are already many downvotes and I would like to add more". If you downvote a post you should really have a "good reason" otherwise it's only making this community crazy and unfriendly.

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

      I think this is more about just a lack of self confidence in your skill or a lack of contest experience to notice the problem is actually easy or a trick question imo.

      EDIT: I removed the joke.

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I somehow agree with your serious point but your first two sentences are a little bit offensive in my opinion.

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Hmm, it was supposed to be a joke and I didn't mean to encourage downvoting, but I suppose I could remove that bit if you find it offensive.

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

            Thanks. Maybe I shouldn't care about downvotes at all.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What's wrong with my sol of problem D. It's showing WA on tc 9 160357208

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there a way to solve D without bsearching at every iteration? Feels like there should be an easier way to do it.

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

    I guess no, as the query limit is an obvious indication to do a binary search.

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

      How do you deduce this from query limit that binary search is to be used?

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

Someone hack my C, https://codeforces.com/contest/1697/submission/160337496, I think it should give tle for large test case

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

This was a nice round, but what I don't understand completely is that my solution of Problem B passes in C++, but does not pass in Python (due to Time Limit). I think that in educational rounds it should not matter which language is used if the idea is correct. But, yes, probably, it is too difficult to check it for multiple languages.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Probably due to slow I/O in python. It's better to load / write data at once.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you! Looking at the solutions, I realised that my solution makes some unnecessary work, and that just by removing those things, it would have passed.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    My solution passed in Python but TLE'd in PyPy.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    same bro, even I submitted in Python and got TLE

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What's the testcase 8 in problem D :(

»
2 months ago, # |
  Vote: I like it +11 Vote: I do not like it

Problem C & D, Easy to come up with the solution but frustrating to implement it !!!!!

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

solved

»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

is problem D inspired from this ?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

When and where can I get the solutions?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Just wait until the announcement post gets updated. It should have a hyperlink "Editorial" by then.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there an option to see rank among rated participants?

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

[deleted]

»
2 months ago, # |
  Vote: I like it -54 Vote: I do not like it

I don't really see the benefit to require 6000 operations in D instead of 27000, from an algorithmic point of view it seems a bit weird to ask for a constant factor <10, as for the quality of the problem the answer is obviously binsearch, so it adds no more thinking but only risks of missing it, and potentially more time and WA spent for the same problem. That will either prevent you from ACing it or spending more time on more interesting problems.

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

    With 27000, you don't need binary search at all.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it -38 Vote: I do not like it

      That's what I'm saying, moving the constraint to 6000 only "artificially" adds an obvious binsearch which is a bit annoying to code

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

        This would make the problem too easy, perhaps easier than C, and the gap between D and E would be enormous.

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it -40 Vote: I do not like it

          Well I think we should not balance problemsets by making implementation artificially harder but rather by finding problems that are harder to solve, but that's only my opinion. Plus I'm kinda bored with "obvious binsearch interactive problems" tbh

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

            But if the interactive problem is not a typical binary search, I feel like it tends to be very adhoc/implementation heavy

  • »
    »
    2 months ago, # ^ |
    Rev. 4   Vote: I like it -19 Vote: I do not like it

    (misunderstood the point, so deleted)

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

      binary search is actually "THE algorithm" here

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

      How is binary search not an algorithm?

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

        I never say "binary search is not an algorithm".

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

        I assume the solution is binary search and I would like to see how to optimize a naive binary search to make it fit in 6000 (or at least pay attention to some implementation details to avoid exceeding 6000). My "naive" binary search didn't pass.

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I thought the crux of this task seems to design a algorithm with query complexity $$$O(n \log |\Sigma|)$$$ instead of $$$O(n \log n)$$$, and the query limit makes great sense if so.

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          You only need to run your binary search among the values $$$last_c$$$ as $$$l$$$, where $$$last_c$$$ is the last occurrence of some character you already have met, so there are only $$$26$$$ values to choose from.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain for Problem B ( PROMO ) , what happens if x == y? I am confused as if x == y then we need to purchase x+1 items as one purchase will be done and rest items sum will be answer. Can anyone clarify it.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Think of it this way: you pay for the x most expensive items first, and then because of the offer, the store refunds you for the first y cheapest items of your purchase. because x = y, so you don't need to spend a penny after the refund.

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

Can C be solved by using this idea?

First I check if all frequency of some letters are not the same, then it's impossible to form $$$t$$$

Then, I try to move all c to the front. Assume that :

  • In original string $$$s$$$, we have c at position $$$c_1 < c_2 < ... < c_k$$$
  • In final string $$$t$$$, we have c at position $$$c'_1 < c'_2, ... < c'_k$$$

My claim : It's optimal to move c so that $$$c_i$$$ moved to $$$c'_i$$$

I just need to check that for each $$$i$$$ :

  • value of $$$c_i > c'_i$$$ (because we can only move c to the left)
  • there are no a between $$$c'_i$$$ to $$$c_i$$$ (since a cannot be swapped with c)

Then I do the same for a, but I try to move a to the back. I got WA but not sure what case breaks it

My implementation : 160335858

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I have the same decision and it also failes, I do not Understand why. https://codeforces.com/contest/1697/my

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

    Kind of easier C implementation

    code
  • »
    »
    2 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I did not read your code but did the same. When you move 'c' don't forget to do the swap. Example : 4 abbc bcab My code https://codeforces.com/contest/1697/submission/160335317

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

      Oh ya you're right. I forgot to swap it. Thsnks

»
2 months ago, # |
Rev. 3   Vote: I like it -23 Vote: I do not like it

Here is my submission for problem D https://codeforces.com/contest/1697/submission/160344339 . The problem states that: "In case you ask too many queries, or the jury program fails to recognize your query format, the answer to your query will be one integer 0. After receiving 0 as the answer, your program should terminate immediately — otherwise you may receive verdict "Runtime error", "Time limit exceeded" or some other verdict instead of "Wrong answer"." The jury program gave me verdict WA, but it also said (in the testcase 10) that i asked too many query type 2. This is unfair, I finished coding problem D when I still had more than an hour to debug.

Edit: actually less than an hour, my mistake xD

  • »
    »
    2 months ago, # ^ |
      Vote: I like it -18 Vote: I do not like it

    same, make the round unrated

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

    This is how interactive problems work — not only on CF, but in official ICPC contests as well. There is no separate verdict for exceeding the number of queries (what should it be? RE, TL, something new?), so the WA verdict is used for it almost everywhere.

    Note that the phrasing in the problem is "you MAY receive some other verdict", not "you WILL receive". This is due to the fact that, in interactive problems, two separate programs are used to judge your submission, and in some occasions, their verdicts can be different (for example, the interactor says that you should get WA for sending too many queries, but then your solution crashes or spends too much time, so it's eligible for WA/RE/TL). That's why you should terminate your program immediately after receiving the response "your query is incorrect", which you don't do.

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

      please quote fully it says "you may receive some other verdict INSTEAD of wrong answer". It may be possible that my English is just bad but to me this statement means that you can receive any verdict on exceeding queries but not a WA.

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

        You can receive any verdict, period. You may receive something instead of WA, or you may receive WA.

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          The problem did not say "or you may receive wa" or meant so. If it did really mean so, why did statement include "instead of wa"? It was unnecessary.

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It says you MAY receive any verdict instead or wrong answer. As BledDest said, it does not guarantee that you will not receive WA

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

          It was so easy to be misunderstood. Your viewpoint is true, some people will understand the problem in the way you did, but many other won't.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for the informations. However, such things are beyond newbie's level for myself (and some other contestants too, I undertood it after reading your comment though). I mean yes those might be compulsive for highly-rated contestants. But contests are for everyone, I don't think every div2-D-solver should have already taken those into account, some of them might just take contests for fun and have a passion for problem-solving for instance. With all being said, I acknowledged that it was my fault for not checking the number of queries, and furtherly understood how computers work to a certain extent (I'm really thankful and appreciate those informations), but the contest organizer could have done better not to confuse a lot contestants, including myself (I had suffered a lot of emotional damage debuging my code for that problem ngl xD).

      That was just my opinion, also English is not my mother tongue langague so please excuse me for any grammar or spelling error.

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Usually it's best just to do what the problem statement says you should do. The problem says that you should terminate your program after getting a $$$0$$$ in response to the query, or otherwise some strange things may happen — so you wouldn't have experienced this issue if you handled this case in your solution.

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          The word "should" might be used for illustration of meaning "the program will be like this like that" or something similar (I have experienced that while doing some cf problems ngl). Also it didn't say those verdicts are "strange things". As I have already said, contests are for everyone, not only for the experienced. So why wouldn't they make everything clear so that everyone can understand? Mistakes are inevitable, but they should be acknowledged. I am just telling my opinion, no offence here.

          • »
            »
            »
            »
            »
            »
            2 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Sometimes it's impossible to make everything clear for everyone, unfortunately. I used this exact wording in one of my previous interactive problems, and there were no issues about that. Maybe I'll change the wording for future interactive problems, considering the feedback from this contest.

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

              I believe that many other contestants would have had the same problem so I'm glad that you will consider it, thanks a lot.

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

          By the way, just for clarification, immediately terminating after getting response '0' will also lead to WA verdict, won't it?

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

            just do vector<int> a;a[784]=784; after getting response '0' and you will get Runtime Error instead of WA )

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

              What a strange way to write assert(false)

            • »
              »
              »
              »
              »
              »
              »
              2 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Ok ig the final issue is wrong answer and too many queries are all merged in one verdict, so as long as there are no different responses, can't really differ between them!

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I didn't see you check 0 as return value, so the verdict will be WA.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I'm new to competitive progamming, so I haven't gotten what you mean yet. Please further explain it. Thanks a lot.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yes exactly this statement is the reason why I spent ~1.5 hrs thinking that either my logic or my implementation was wrong. It literally says that you will get "Some other verdict instead of Wrong answer"

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

    I too was confused by the WA I got on submission just before contest ended. Now I realize my code just missed a single variable increment which I forgot to write(facepalm) making my program flooded with query 1 AC submission after contest.

    However, it is solely my stupidity and I greatly enjoyed the problem!

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I don't understand what you mean — this simply means that if your program is wrong you might get any verdict. You don't need to check 0 in case your program is correct

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Better count the queries in code, and put an assert statement in end to get RE instead of WA

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

interactives -_-

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

how to do c?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    S--->T Because a cannot be swapped for c, each char 'a' in s and t must have the same number of char 'c' on the left and right sides ( sequence wise for every a in s & t) Second, we can't change ba to ab, thus for each a in s and t, no of b in left of a in s <= no. of b in left of a in t (sequence wise for every a in s & t). Finally, because we can't exchange cb to bc, thus for each b in s and t , no of c in left of b in s <= no. of c in left of b in t (sequence wise for every b in s & t).

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

Can someone please explain me why my solution 160333877 gives TLE? From the code the complexity seems like nlogn. Thanks

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

.

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

Wasted 30 mins on C because of a single "break". How careless I am! :(

Anyway,the problems are fantastic!

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

I got the solution idea for problem D from the constraints.

  • First, we can use the first type of query at most 26 times. That indicates that we will use it to know the indices of the first appearance of each character.

  • Second, we can use the second type of query at most 6000 times. After trying some calculations, I found that the nearest calculation to 6000 is 1000 * log_2(26) which is approximately equal to 5000 or smth like that. So, then I came up with solving it using binary search.

Honestly, I think this problem is very interesting!

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

I kept getting WA 7 in problem D so I though that i am not exceeding the number of allowed queries. (because the statement mentioned that I should get some verdict other than WA in this case)

so I was looking for a bug in my code instead of my idea I also added assert to the response to make sure ites not 0 as the question suggested which means not breaking the roles

and after the contest finished I found out that its wrong because it exceeded the allowed queries -_-

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

import java.util.*; public class PalinInd { public static void main(String args[]) { Scanner sc=new Scanner(System.in);

int n=sc.nextInt();
     long q=sc.nextInt();
     long arr[]=new long[n+1];
     arr[0]=Integer.MIN_VALUE;  
     for(int i=1;i<=n;i++)
       arr[i]=sc.nextInt();
     int arr1[]=new int[n+1];
     arr1[0]=0;
     int p=1;
    long s=0;
     Arrays.sort(arr); 
     for(int i=1;i<=n;i++)
     {
       // s=s+arr[i];
        arr1[i]+=arr1[i-1]+arr[i]; 
        //arr1[p++]=s;
     }  
     for(int j=1;j<=q;j++)
     {
         int x=sc.nextInt();
         int y=sc.nextInt();
         int val=n-x; 
         System.out.println((arr1[val+y])-(arr1[val]));
     }
  }

} why my code give tle in 3rd test case in java??please answer

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    1. Arrays.sort is quick sort that is O(n^2) in worse case
    2. Scanner is slow. I used: new BufferedReader(new InputStreamReader(System.in))
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

A to D are good. Problem E seems interesting, will give a try later.

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

It seems like the observation of E is easier than D,but I dont have enough time..

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What's the different between F and k-sat?

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

my solution to b part is

https://codeforces.com/submissions/dsanurag520 (it is in python)

But my solution is jumbled. Does anyone know why this is happening?

»
2 months ago, # |
  Vote: I like it +7 Vote: I do not like it
Spoiler
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.com/contest/1697/submission/160338205 This is my submission for problem C. It fails on test case 407 of main test 2, which isn't visible (only the first 110 lines are visible on the page). Could anyone tell what test this solution fails on?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

B task is almost similar to this one

»
2 months ago, # |
  Vote: I like it +22 Vote: I do not like it

I love getting rank 3000+ because i solved D and i was unable to solve C, and i am getting passed by people who solved C with O(n^2), feels great and fair :)

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can always hack those who passed with n^2

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

      I tried hacking one and it goes up to 1.9s but it doesn't pass 2sec (i don't think there can be a more optimal hack) C++ is way too fast and O(n^2) solutions pass the time limit. Honestly, i believe that the TL for this problem is just way too big since optimal solutions in C++ pass in about 15ms.

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        My C just got hacked

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

        Maybe limits for such problems should be reduced to 1.5s

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Your hacks were not good enough. You were attempting 10 tests of size N = 10^4. 1 test of size N = 10^5 would have crashed an N^2 solution. Not even C++ can handle ~ 10^10 operations in 2 seconds.

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I tried 2 different hacks, the last one (the one you describe) was a curiosity hack because I wanted to see what time difference it would make if I dropped the operations down to 10^4 and increased the number of tests. On my first hacking attempt, I tried the hack you describe — 1 test of size N = 10^5, and yet this didn't crash an N^2 solution. The link to the submission I tried to hack is 160337496 and it is still not hacked.

          • »
            »
            »
            »
            »
            »
            2 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Apologies. I was only able to find the smaller attempted hacks. You're right though; somewhat incredibly it passes. I'm indignant on your behalf as it doesn't deserve to pass, and also kind of in awe at C++.

            • »
              »
              »
              »
              »
              »
              »
              2 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              No worries, indeed it's insane how fast C++ is, in this submission in particular it loops around ~2.5*10^9 times, and finishes in under 2 seconds.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Educational Rounds always weight each problem equally so solving F only and solving A only can have similar rankings. In a previous Education Round I solved A-D but then C got FST due to a stupid long long overflow and then I dropped to my lowest rating :).

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Would like to see a great solution for C. My solution requires complicated proofs and cumbersome implementations. Not sure whether I was in a hard and stupid direction again.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The simple solutions of C are based on two observations: the subseq of 'a's and 'c'c in both strings must be same. And the positions of the 'a's (and 'c's) must be so that they can be moved in the desired direction. That makes it possible to implement it with only simple loops.

    example 160322407

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Let's assume that two characters did not match when passing through C and T. We have two options when it can be fixed. 1. s[i] = 'a' and t[i] = 'b'. Then we need to find the next b and swap it with s[i]. This can be done only when between this symbol b and our s[i] all characters are a. 2. s[i] = 'b' and t[i] = 'c', etc., only instead of a, b — b, c. All this can be quickly implemented, for example, by creating a set of indexes for each letter and using upper_bound to recognize the next letter. If anything, English is not my native language, I write through Yandex translator. My code (on c++): https://codeforces.com/contest/1697/submission/160320598

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone please tell me what is wrong with in my submission for C. It is giving WA on test 2. I can't even see that case

»
2 months ago, # |
  Vote: I like it +32 Vote: I do not like it
  • »
    »
    2 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Lol. Roles got reversed.

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

    Last Atcoder contest has the famous leetcode problem: construct binary tree from preorder and inorder traversal.

»
2 months ago, # |
  Vote: I like it +7 Vote: I do not like it

the guy's solution is weird 160366565
It seems to be written like this on purpose and then hacked by others.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem B, I used Arrays.sort() and got TLE but after only changing code to work with Collections.sort() it passed. Why is this?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This implementation of mine is failing on 2164th case of test case 2. Can someone check what's wrong? Submission link

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

good contest

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I suspect a problem with problem B. Promo I made a very fast O(NlogN) solution using Java, and I got "TLE on test case 3". Since I knew for a fact it was fast enough, I wrote the exact same code logic using C++. It passed. I think the problem should have a second or 2 more, for non C++ users. Did anyone else encounter this problem?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I have used very fast algorithms in B, merge sort and then individual operations, but it was showing runtime error!

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same here. After contest I tried with Arraylist and used Collections.sort method which eventually passed.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Arrays.sort in Java uses

    • quick-sort for primitives (with worst case O(n*n))
    • And merge-sort for wrapper objects.

    Instead of int[], if Integer[] is used, it passes.

    Check this blog to understand more.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      wow, this is extremely helpful, tysm! I never knew this — somehow I have solved many NlogN problems where N>=100k without knowing this haha.

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

Could anyone please check where my code fails? 160297431 Its really annoying to get weak pretests. Coz of this my initial rank was 2k and now it is 8k. Had solved C in 14 mins :facepalm: :lolisad:

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Your complexity seems to be $$$O(n^2)$$$, so it is hacked because of TLE.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Completely bricked C. Bye-bye rating :(

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello, I found in the hacks that it appears as though a solution without prefix sums had passed the pretests on problem B (and then painfully got hacked). Is this intended, or did noone expect this passing the pretests? The submission of interest is as follows: 160341801

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    difference between x and y could be 2*(10^5), and number of operations could be 2*(10^5). So, yeah prefix sum is expected solution.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Got TLE even with prefix sum

      Pain
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Could someone say me where my 160349731 failed for problem C. I collected all those places where there is a mistake in string. They should be even in number because there if a letter could be corrected by swapping, then the other letter in pair of it should also be in wrong position. Now going from smallest index to largest index (in the collected indexes). Suppose if 2nd index letter is 'b' and 1st is 'a' without any c between them (I calculated it by prefix sum difference between these 2 positions is 0) then I'll swap them and remove those two indexes from my que. Similarly for c and b pair. Note: if 2nd element in que is 'a' then you can't swap element in 1st position to correct place.

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

Often struggle with constructive algorithm problems in div2 C. Any suggestion for improving in this category will be appreciated.

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

I have somewhat different idea for C, Some observations we can make:

1)In string s, if we have a 'c' at some position,then characters to left of it always remain left and characters to right of it always remain right.Similarly in string t, if we have 'a' at some position.

2)From 1 we can immediately say that if there is index i such that s[i]='c' & t[i]='a' ,then answer never exists.

3)strings should be anagram of each other

Now suppose that i is first index where a 'c'occurs in string s and j is first index where 'a' occurs in second string,and since i!=j(2nd condition) ,wlog suppose i>j ,then we can use first i-1 characters of s to match first j characters of t,this can easily checked if count a,b,c in s till i-1 is greater or equal to count of a,b,c in t till j,now we reduce frequency count of a,b,c in string s. This works because till i-1 we have only 'a' and 'b' in s and since they can cross each other i would be able to achieve any configuration of 'a'and 'b' to match first j characters of t.Now we move to next 'a' in t(because i>j) and disregard first j characters of both strings For example:

bcaabababc

cbbababaac

we start from left i=2 and j=4 count of a,b,c in s=0,1,1 till i and count of a,b,c in t=0,2,1 till j-1 and count in t is greater or equal we move to next 'c'(because i<j) and disregard first 2 characters now i=10 and j=4, count a,b,c in s=4,3,0 till i-1 and count of a,b,c in t=1,1,0 .Again condition is true,we move to next 'a' in t. i=10,j=6 count of a,b,c in s=3,2,0 till i-1 and count of a,b,c in t till j is 1,1,0.Again condition comes to be true. move to next 'a' in t. i=10 j=8 (a,b,c) in s is(2,1,0) and in t is(1,1,0). Again true. move to next 'a' in t .in s (1,0,0) and in t (1,0,0) .Again true and we dont have any more 'a' to move for . and hence we terminate and we can say it is possible to interconvert s and t

»
2 months ago, # |
  Vote: I like it +19 Vote: I do not like it

When will the rating change?

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

    How to check whether System testing is done or not?

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

      Just open your in-contest submission and see 'Sent' and 'Judged' time

      If they are 12-15 hrs apart then system testing is done else they are not.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Edu round take 24 hours after contest.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

When will Editorial out?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem D , (Guess the string) , while applying binary search how are you deciding that you have to go to left or right. Let's say: distinct characters(mid...i) == distinct characters(mid...i-1). Then we are sure that Str[i] = Str[mid]; Otherwise , you have to go left. (How can you say that you have to go left? ) Can anyone please explain it?

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

    You have to create a new temporary array where you store the index of last occurrence of all characters that you have encountered so far and then binary search on that array. if distinct characters(tempArr[mid],i)==(tempArr.size()-mid+1) then move left else you have find a potential character save it into variable (say fans) and move right in tempArray. Finally do ans+=fans;

    LINK->160405246

»
2 months ago, # |
  Vote: I like it +13 Vote: I do not like it

waiting for editorial.....

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The judging for B seems to be inconsistent for python. I have gotten TLE while similar solutions have gotten AC :(

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I totally agree! My python solution was initially accepted, and then ended up being successfully hacked, due to TLE. And I am guessing that the only part of my code that was producing the TLE result — which I think is probably similar to what happened on your end, from looking at your code — is using python's built-in sort function. It seems very inappropriate that their judge function produces that result on this problem.

»
2 months ago, # |
  Vote: I like it -19 Vote: I do not like it

Very slow system testing because most of people didn't use fast input. Please use it next time :)

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why is there so many downvotes? I don't get it xd

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    fast input can increase speed ~10x for problem B for example. Why is it so bad comment?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    the long systests were not because of people not using fast IO, instead it was due to the very few people expanding the systests to a whopping 60+ testcases on problem B only, and still more on other problems

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

O(n^2) solution passing for C. Seriously guys, is this what this has come to?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Could someone please explain why the same code gives AC for C when compiled with GNU C++17 (64) but it gives Runtime error when compiled with GNU C++17 ??

Correct soln: https://codeforces.com/contest/1697/submission/160348230

Incorrect soln: https://codeforces.com/contest/1697/submission/160432316

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

where can we find the tutorial?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why does my rank keep on increasing by a bit in the hacking phase?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem C was a nightmare. Tried so many things with "a" and "c" like counting inversions and removing "b" s and they did not work, ate so many penalties and finally went with valid parenthesis approach and still made more penalties because of forgetting edge cases

managed to solve it but ate 7 wrong answers. who else ?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i just simulated process of moving first b after a in S if S[i] = 'a' and T[i] = 'b'

    and same for moving first c after b and used two pointers for that. Also checked edge cases when we can't move right character to that place because characters before it are the same for S and T. (in 10 minutes)

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

    We have 2 cases when we can change something.

    if s[i] == t[i] everything is good

    1: s[i] = 'a', t[i] = 'b' we need to find closest b and swap it with s[i] and also there can't be any 'c' in path -> aaaab...

    2: s[i] = 'b', t[i] = 'c' same with above, find closest c, and check if there is no 'a' on path

    otherwise we can't get s equal to t

    best to use set for O(nlogn) time complexity https://codeforces.com/contest/1697/submission/160327520

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Solved during the contest but got hacked :)...hence was unsolved during contest:( Finally solved after 3-4 WA's.