By awoo, history, 2 years 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

| Write comment?
»
2 years ago, # |
  Vote: I like it +53 Vote: I do not like it

Good luck for Everyone

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

Finally a Div2 Edu Round :)

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

    NO way . Only solving 1 / 2 question can't make you green

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

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

  • »
    »
    2 years 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 years ago, # |
  Vote: I like it +31 Vote: I do not like it

hope for a good contest, not speedforces .

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

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

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

All the best Everyone!

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

Good luck for Everyone

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

Hope to become BLUE at least today.

»
2 years 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 years 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 years 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 years 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 years ago, # |
  Vote: I like it +8 Vote: I do not like it

I'll die doing C

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

C was annoying

but D was very great and nice

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

              interactive = binary search

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

      I did exactly the same.

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

    Because it's ICPC mode

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

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

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

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

      • »
        »
        »
        »
        2 years 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 years 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!

          jnidv Thanks!

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

      can you pls explain your approach?

      • »
        »
        »
        »
        2 years 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 years 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 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Can anyone help with C?

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

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

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

Worst round since last Month.

Upd. Change my mind:

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

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

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

D << C

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

    How to solve E?

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

        thx! I catched my error

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

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

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

How to solve F?

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

    What's the observation for D ?

    • »
      »
      »
      2 years 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 years 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 years 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 years 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 years 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 years ago, # |
  Vote: I like it +13 Vote: I do not like it

What is test case 10 of E?

»
2 years 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 years 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 years 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 years 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 years 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 years ago, # ^ |
              Vote: I like it +5 Vote: I do not like it

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

»
2 years 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 years 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 years 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 years 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 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

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

What's the testcase 8 in problem D :(

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

solved

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

is problem D inspired from this ?

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

When and where can I get the solutions?

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

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

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

    (misunderstood the point, so deleted)

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

      binary search is actually "THE algorithm" here

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

      How is binary search not an algorithm?

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

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

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

            That makes a lot of sense!

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

    Kind of easier C implementation

    code
  • »
    »
    2 years 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.net/contest/1697/submission/160335317

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

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

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

Here is my submission for problem D https://codeforces.net/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 years ago, # ^ |
      Vote: I like it -18 Vote: I do not like it

    same, make the round unrated

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

              What a strange way to write assert(false)

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

how to do c?

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

    I believe, it's because you're accessing st[3] which is out of bounds.

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

      Arghhhh! How did i miss this?! This contest was a nightmare for me. Thanks for taking the time to figure it out.

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

.

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

    yes, I too came up with approach but unable to implement it.

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

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

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

    or something related to binary bits if constraints contains 32 as limit of queries

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

https://codeforces.net/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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

B task is almost similar to this one

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

    You can always hack those who passed with n^2

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

        My C just got hacked

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

        Maybe limits for such problems should be reduced to 1.5s

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

    Lol. Roles got reversed.

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

good contest

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

Completely bricked C. Bye-bye rating :(

»
2 years 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 years 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 years 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 years 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 years 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 years ago, # |
  Vote: I like it +19 Vote: I do not like it

When will the rating change?

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

    How to check whether System testing is done or not?

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

When will Editorial out?

»
2 years 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 years 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 years ago, # |
  Vote: I like it +13 Vote: I do not like it

waiting for editorial.....

»
2 years 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 years 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 years 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 years 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.net/contest/1697/submission/160348230

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

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

    Lines 94 / 109 you dereference an erased iterator which is undefined behavior.

»
2 years 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 years 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 years 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 years 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.net/contest/1697/submission/160327520

  • »
    »
    2 years 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.

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

I think my solution for problem C was cool. I turned s into a list of tuples by counting same characters in a row, i.e. aaabbaccb would turn into [('a',3),('b',2),('a',1),('c',2),('b',1)].

if there is a match I decrease 1 from current char, otherwise if there is mismatch and possible to fix, I would decrease 1 from the following tuple. i.e., if s=aaabb and t=babaa, Then [('a',3),('b',2)] would turn into [('a',3),('b',1)], then [('a',2),('b',1)], then [('a',2),('b',0)] (when zero I delete it) then [('a',1)], then [('a',0)] and done.

To check that a mismatch is possible to fix is easy. If the mismatch is a!=b, then I just check if the next tuple contains 'b'. Also, when I delete an element I merge two consecutive elements of same char. Also the listis actually reversed so I can pop() in O(1).

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

Why is it showing unrated for me?

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

    You are not alone bro.. But its taking a way more time than expected:).

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

Is it only me or the ratings for this round hasn't been updated yet for everyone?

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

Waiting for the rating to change.

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

the same code "copy & paste" :

TLE : 160442368

ACC : 160372033

How does this code get Acc with O(N ^ 2) where N is up to 1e5?

I see a lot of O(N^2) with Acc not only this

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

This is a more formal explanation of a solution to problem D.

Denote a query of type 2 by $$$ d(l, r) $$$, i.e. the number of distinct letters among $$$ s_{l..r} $$$.

First, find the first occurrence of every letter in the alphabet. They appear at index $$$ 1 $$$ and all $$$ i $$$ where $$$ d(1, i - 1) < d(1, i) $$$. Use queries of type 1 to find out the letters at these indices. There are at most $$$ d(1, n) \le 26 $$$ such indices.

Then, consider all prefixes of the string $$$ s $$$ in ascending order of length. Denote some prefix by $$$ p $$$ and its length by $$$ m $$$. Assume we know every letter in $$$ p $$$ already, now we will determine the next letter $$$ s_{m + 1} $$$. If we already know $$$ s_{m + 1} $$$ from the first step (because it is the first occurrence of a letter), we can move on to the next prefix.

Maintain $$$ c = $$$ set of letters in $$$ p $$$, and $$$ L $$$ = map of each letter in $$$ c $$$ to the index of its last occurrence in $$$ p $$$. Since $$$ s_{m+1} $$$ is not the first occurrence of a letter, $$$ s_{m+1} \in c $$$. Sort $$$ c $$$ by the value of $$$ L[c_i] $$$ in ascending order. We are looking for the last letter $$$ k $$$ in $$$ c $$$ where $$$ d(L[k], m) = d(L[k], m + 1) $$$, because it implies $$$ d(L[k] + 1, m) < d(L[k] + 1, m + 1) $$$ $$$ \implies s_{m+1} \not\in s_{L[k]+1..m} $$$ $$$ \implies s_{m+1} = k $$$. Note that we can compute $$$ d(L[k], m) $$$ instead of making a query. We can binary search for the required $$$ k $$$ in $$$ c $$$. Continue by setting $$$ p + s_{m+1} $$$ as the next prefix.

$$$ O(n \log 26) $$$ queries of type 2 are used.

I upsolved D here: 160441046

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

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

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

Problem D was so great !!! Thanks for this nice round :)

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

Just did problem E. Awesome problem!

First I noticed that the sizes of equal distance groups can only be 4 at most.

Then I noticed that you just need to keep a list of all points of minimum distance from you.

Then I noticed that the only way to color a few points the same color, is if they are all minimum distance from each other.

Then I noticed that a group (of min dist from each other) has to either be colored the same color, or all different, and this type of coloring is completely independent from the other choices for other groups.

From there it's straight forward, a dynamic programming depending on how many colors remain, and if you choose to color the group in the same color or all different colors (no other options). i.e. dp[number_of_group][colors_remaining][color_same_or_all_different].

Don't yet know its rating, but might be the highest rated problem I solved!

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

Finally specialist!!

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

At problem C. Can anyone explain why I got TLE in the first submission and the other one doesn't?

Link 1: TLE submission Link 2: AC submission