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

Hello Codeforces!

On Jun/29/2023 17:35 (Moscow time) Educational Codeforces Round 151 (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, 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
WORK & STUDY OPPORTUNITY IN BARCELONA — IDS x HARBOUR.SPACE UNIVERSITY

Intentionally Designed Solutions (IDS) has partnered with Harbour.Space University to offer Master’s degree scholarships to study Front-end Development, as well as work experience as a Front-end Engineer in a leading product development studio specializing in web-based solutions, including websites and web applications.

All successful applicants will be eligible for a 100% Tuition Fee Scholarship (29.900 €/year) provided by the Intentionally Designed Solutions (IDS).

CANDIDATE’S COMMITMENT

Study Commitment: 3 hours/day

You will complete 15 modules (each three weeks long) in one year. The daily class workload is 3 hours, plus homework to complete in your own time.

Work Commitment: 4+ hours/day

Immerse yourself in the professional world during your apprenticeship. You’ll learn from the best and get to apply your newly acquired knowledge in the field from day one.

RESPONSIBILITIES

  • Collaborate with cross-functional teams to develop and implement innovative front-end solutions that align with project requirements and design specifications.
  • Write clean, efficient, and maintainable code using modern front-end technologies, including Typescript and Svelte.
  • Ensure seamless integration of front-end components with back-end systems, leveraging technologies such as MongoDB and Firebase.
  • Demonstrate a basic understanding of smart contract technology, enabling the integration of wallets and blockchain functionality into web-based products.
  • Lead and mentor junior developers, conducting code reviews and providing guidance to improve code quality and development practices.
  • Drive the development arm of IDS's business by identifying opportunities to optimize processes, enhance efficiency, and improve overall team productivity.

REQUIREMENTS:

  • Minimum of 2 years of professional experience in front-end development, with a focus on web-based products.
  • Strong proficiency in Typescript and Svelte, with a solid understanding of front-end frameworks and libraries.
  • Experience with back-end integration, particularly with MongoDB and Firebase.
  • Basic understanding of smart contract technology and its application in web development.
  • Previous experience managing and mentoring developers, conducting code reviews, and improving development processes.
  • Excellent problem-solving, communication, and collaboration skills.
  • Bachelor’s degree or equivalent experience.
  • Advanced English level.
Apply Now →

UPD: Editorial is out

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

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

As a green participant, I hope to be cyan again after this contest)

If you want to race

GL & HF

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

    As a cyan participant, I hope to be green again after this contest)

    GL & HF

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

      As a blue participiant, I hope to be a LGM ever. GL & HF

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

      As a blue participant, I hope not to be blue again after this contest)

      GL & HF

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

      As a gray participant, I hope to stay gray after this contest)

      GL & HF

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

      As a black and un-bolded participant, I hope to be black and un-bolded after this contest)

      GL & HF

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

    I hope to be purple.

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

    As a Purple participant, I hope to stay Purple after the contest.

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

    As a gray participant, I hope to be green after this contest)

    GL & HF

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

    I might become cyan by morning if not hacked.

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

    As a gray participiant, I hope to be a LGM ever. GL & HF

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

    That's so good.

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

as codeforces user i hope to have great round

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

Again no tester

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

big chance to become green tomorrow

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

The road to green, God willing

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

    bro wdym, you don't even need God to make it to green. I have full faith in you! :D

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

      We can't do anything without the will of God

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

        Yes, my bad. Let's pray that god will be generous and allow us to advance to the next color.

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

          its god's will that i am dog shit at data structures&algorithms

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

            bro I'm awful at dp

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

      dud u burn in hell like this what are u even saying?

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

    almost there mashaAllaah

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

    Good luck, God willing

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

Will "not rated participant" get rated in this contest?

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

    Non rated participants always get rated if they participate. Which is why you should participate. GL! :D (Remember to bump)

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

I want everyone to take it to the next level

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

Why can't the code submitted now be viewed on the PC side?

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

who tested this round?? who tested this round?? who tested this round?? who tested this round??

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

    Nice contest, but there's just one small problem with it: who tested? like genuinely who tested? who gave you the testing code? I'll tell you nobody did, nobody tested it. There are zero people who tested among us, look I invited everyone who tested to this party, and took a photo of everyone who tested, yo check out it's a bus full of everyone who tested. You know what man, I'll do you a favor, clearly we can't see who tested, so I'm just gonna do it myself, I'm gonna find out who tested. I sailed in the seven seas to find out who tested, yo I literally found the one piece before I found who tested, I literally climbed to the top of Mount Everest and didn't find who tested. Keep searching boys we gotta find who tested. I just infiltrated the largest satellite dish in the world and I still can't locate who tested, I literally found the cure to cancer before I found who tested, I'm on maximum render distance and I still can't find who tested, I witnessed the collapse of human society resulting from a global nuclear war, I now live in the grave of this broken world ravaged by radiation for years on end before I found who tested, I visited every single planet in no man's sky and still didn't find who tested, doctor strange literally looked through 14 million different timelines and not in one of them than anyone tested, I literally searched through every single backroom's level and didn't find who tested, I literally died and went to heaven and god himself doesn't even know who tested. Leaving the earth's atmosphere to expand the range of our search, yo I literally found extraterrestrial life on Mars before I found who tested, I have achieved intergalactic travel before I found who tested, I just found a dyson sphere before I found who tested, I found the edge of the universe before I found who tested, I literally visited every single planet in the entire universe before I found who tested, I am literally witnessing the death of almost every star around me before I found who tested, the light of the universe is slowly fading I have searched across galaxies leaving no stone unturned, yet I am afraid my time in this universe is finally running out, it's a shame really I've witnessed stars being birthed and those same stars dying, I've seen literally everything there is to see in this beautiful universe, yet this whole time I've been caught up with such a petty task instead of enjoying my time while it lasted. I was distracted from the beauty of it all I don't regret what I've done, though the question that started it all: who tested has finally been answered. I've searched every nook and cranny in this entire universe and can now confidently say better than anybody that truly nobody tested [Music] the contest.

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

As a cyan participant I hope to go green this round.

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

What's the difference between common round and Educational round?

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

As a blue participant, i hope to cross my peak rating :)

GL & HF

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

Maybe I am ready to take the next step.

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

Problem C was really something..

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

how to do C with binary search?

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

    observation !!

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

    Read 2nd testdata of testCase 1 in the example. You might get it.

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

      Can you elaborate please.

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

        s = 123412341234

        m = 3 ,

        l = 111 r = 444

        So, Now, Traverse the string S from left to right. While doing so we need to keep track of zero'th digit of the password, until all the characters are occurred from l[0] to r[0]. Once all the character of particular digit of password are occurred in the string, we must move to next digit of the password.

        1234| (now all the characters are occurred from first digit of password, so we must move to next digit).

        If all the digits are exhausted from password, then answer is not possible. otherwise, answer is possible.

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

          got it,thanks.

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

          wouldn't it will give TLE for checking through all Possibilities of password. and thanks for hint of BS.

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

            Yeah,that is what I thought suppose m =10 and l = 0000000000 and r = 9999999999 then we have to check at least 10^10 passwords. Don't we??

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

          Man, I solved it with DP, shame on me

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

          I get this approach but where does binary search come into play here? The traversing is linear

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

            where Did I mention anything about binary search ?

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

              Vincenzo_ was asking for BS solution and you replied to him so I thought you may be telling something about the BS solution. Anyways do you have any insight on how to do this via BS? I am seeing a lot of people discussing BS solution of problem C but I dont find the approach mentioned anywhere.

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

Can someone give a hint on E please?

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

    You can squeeze in $$$O(NK^2)$$$

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

      I was thinking about something like doing a dp which keeps track of three parameters: current idx (n), current one, and wasted moves

      would this work ?

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

        This would, trivially implementing this is $$$O(NK^2)$$$. To squeeze it in, you can do the following: 1. If more than half of the array are $$$1$$$-s, you can consider that every box without a ball has one, and vice versa. This halves the runtime. 2. Write out the formula: $$$dp[i][k][p1] = dp[i - 1][abs(k - pos[p1 - 1])][p1 - 1]$$$, where $$$i$$$ is the current position, $$$k$$$ is the number of wasted moves, and $$$p1$$$ is the number of wasted moves so far. Notice that you can keep this dp in a single array and recalc top to bottom, so you do not do memsets and swaps.

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

          As someone has written, it might work not in $$$O(NK^2)$$$ but in $$$O(NK\sqrt{K}$$$)

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

    How far did you get/what part of the problem do you want a hint for?

    I think there are several stages in solving this problem:

    1. Thinking of any solution at all (this one you should probably do by yourself).
    2. Realizing how to make it run in $$$\mathcal{O}(N×K^2)$$$.
    3. Realizing how to optimize it into $$$\mathcal{O}(N×K^{1.5})$$$.
    4. Making the implementation efficient enough to fit in the time/memory limits.

    (I failed at step 4.)

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

How many people solved Problem C, ** AFTER READING SECOND TESTCASE DATA in TESTCASE 1 ?**

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

    :| I didn't read the explanation of test cases question was quite self explanatory!

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

    Oh I am glad, I am not alone.

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

    How to prove that if answer is no then the string must contain such a pattern?

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

    How??

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

    can you please tell what helped you in AFTER READING SECOND TESTCASE DATA in TESTCASE 1 ?, i didn't get it , is this testcase so obvious for BS. how did it helped solving the que

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

      there is no need of binary search, it can be done by linear search.my approach is:- try to find max first occurance position of elements of l[0] to r[0] and store it in last_position and then find from last_position+1 position for l[1] to r[1] and update the last_postion. if it goes beyond (size of string-1) ever then possible otherwise no. basically each time we are discarding max possible substring from left side ex:- 123412341234, 111, 444 for l[0] to r[0], last_position=3, then start searching from 4 for l[1] to r[1], last position will be 7 and for l[2] to r[2], last position would be 11 (string size-1=11) so ans is no. this example was a good hint for this approach but i didn't get it that time.

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

        thanks bud, I also had same intuition while reading the test case, but was not able to apply it through code while contest.

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

      It can be solved by dp also . use two state dp , dp[i][j]where : 1) i denotes the index in string s. 2) j denotes the index in string that we want to make( that is of length m). this j will help us in iterating through l and r string.

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

How to do D?

My intuition was maximizing this, pref_sum [i] + max(suff_sum[i + 1], ..., suff_sum[n — 1])

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

    You need to do max(suff_sum[i + 1], ..., suff_sum[n — 1], 0) instead.

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

      I think pref_sum[i] should also be included?

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

      For this test case

      2 -1 3

      Why answer can't be -1?

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

        If your answer is -1, then the player's rating will go 2 to 1 to 4.

        The answer should be 2. The player's rating will go 2 to 2 to 5.

        Any answer other than 2 will result in the player's rating decreasing from the -1. If our answer is 2 then we ignore the -1.

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

    It seems to be correct as that's I what I've done. I find the continuous interval with the smallest negative sum, and then remove it.

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

    I'll try to explain my solution in my own words. First, define C[n] as the prefix sum of A[1..n] (formally: C[0] = 0, C[i] = C[i-1] + A[i] for 1 ≤ i ≤ N). The elements of C are the scores that would be obtained if there wasn't a floor in effect.

    Hint 1
    Hint 2
    Implementation

    Code: 211553817

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

explain solution for C?

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

    I bootled this so bad . I got accepted after 7 minutes of contest end , the idea is so easy i just messed up the implementation :

    idea is that after you choose a number the first occurrence of that number splits the string into two, now the problem reduces to the right half only . so we can greedily choose the number from possibilites (that is between l[i] and r[i]) which gives the shortest possible remaining string. If at any iteration (i) one of possible numbers is not in the remaining string choose it and that gives answer yes. If you finish traversing all i's without then the answer is no.

  • »
    »
    10 months ago, # ^ |
    Rev. 11   Vote: I like it 0 Vote: I do not like it
    Spoiler
  • »
    »
    10 months ago, # ^ |
    Rev. 7   Vote: I like it +1 Vote: I do not like it

    Start from last in both range strings(l and r) and string s, let say p1 = n-1, and p2 = m-1.

    Now, looking from last (i.e from p1 to 0), find the numbers in range l[p2] and r[p2], if at any p1, you find all the numbers in the range, then reduce p2, then again find all the numbers in range l[p2] and r[p2], do this until you will encounter one of the case, if p1 becomes -1, then that means you can make some password which will not be subsequence in string "s" therefore the Answer would be "YES", else p2 would have became -1, that means all the ranges have ended therefore all the possible subsequences are present in string "s", Hence the Answer would be "NO".

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

Yet again I misread a problem, this time C. I thought it was asking to check if there exist a string s, such that s >= l && s <= r, instead of s_i >= l_i && s_i <= r_i. (mathjax not working?)

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

Overkilled D with binary search and sparse table and now feel very annoyed at myself. :(

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

    How did you solve D with binary search and sparse table? I am curious to know. My technique used a modified version of kadane's algorithm to solve it.

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

      Fix the position of k then find the smallest subarray starting at that position that has negative sum. Rating will be k after that. Repeat until there is no more subarray with negative sum. Rating at the end will be k + suffix sum from there. To simulate the above process run a binary search for the first index where sum of subarray starting at k's index is negative. Sparse table helps here. Yes it's overkill. And it's basically the same idea

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

        Oh I got your idea. True it is a little overkill but still its cool. Also it feels like my idea but from the opposite direction. My idea was to find the max sum subarray that ends in the last index of the array containing all match values. I would then add it to k.

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

D is a neatly disguised minimum subarray sum problem

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

How to do E? I have a O(n^2 k) DP which TLEs. Is this the intended solution, or is there anything faster?

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

    is it dp[i][j][p] = how many possible placements are there if the ith ball is at jth position and we have used p swaps so far

    in the end answer is =

    for(int j = 0 ; j < n ; j++){
    	for(int p = 0;p<n;p++){
    		if((k - p) % 2 == 0)ans += dp[n-1][j][p];
    	}
    }
    

    ( I just asked this to confirm if my idea was correct )

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

    I used the fact that if $$$one_i$$$ is the position of i-th one, possible final positions for i-th one are roughly $$$[one_{i-\sqrt k}, one_{i+\sqrt k}]$$$. If you use this then there is only $$$O(n\cdot k^{1.5})$$$ states.

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

      How this fact can be proved or even how can it be observed?

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

        Ones don't change their relative order, so to move $$$one_i$$$ to a position $$$x < one_{i-\sqrt k}$$$ you need to also move all of the other occurrences to the left. In the simple case when all of $$$one_{i-\sqrt k}, \dots, one_i$$$ stand one after the other you will need to make at least $$$(\sqrt k + 1)^2$$$ operations, and if they are not consecutive it requires even more operations. Not very strict, but I hope this helps.

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

    Congratulations for coming up with the $$$O(n^2k)$$$ DP! My solution is simply an optimization of the $$$O(n^2k)$$$ DP and the time complexity is $$$O(nk\sqrt k)$$$.

    In one word: throw away all useless states.

    In more words:

    DP is deciding from the left to the right for each position whether to put a 0 or 1 and count the number of inverse pairs (aka number of swaps used). Let DP[i][j][p] be the number of situations that: we have already decided the first $$$i$$$ positions, among them we have used $$$j$$$ 1s and we have encountered $$$p$$$ swaps. Naive implementation of this DP is $$$O(n^2k)$$$, but a state is useful only if $$$\left|j-S_i\right| <= O(\sqrt k)$$$ (where $$$S_i$$$ is the prefix sum of the original array), otherwise the number of swaps will be too large ($$$>k$$$).

    Source: Trust me. I am gray.

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

      Hi, could you point to a resource where one could practice such dp problems? I've done a few on cses.fi, and SPOJ but Even the O(n^2k) DP is a bit difficult for me to grasp and I'd like to learn more. Thanks :)

»
10 months ago, # |
  Vote: I like it -25 Vote: I do not like it

edu contest with 999999 caseworks

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

Can any one explain to me why my B submission is not working?

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

    Your first case of if is incorrect.

    It should be 1+min(abs(xb),abs(xc))+min(abs(yb),abs(yc)).

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

Did 3D DP for C worked for anyone?

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

The gap between question D and question E is too big, but of course, it could be mainly because I am too weak. Let's do better next time, although I am still a little disappointed.

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

I overkilled C with DP and I don't feel good now Submission

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

    It's impressive to be able to solve this problem using dynamic programming. At first, I also thought it could be solved using dynamic programming, but I couldn't figure out how to do it no matter what.

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

      Main idea is to store dp[i][j] — maximum value of "where we are" in the string s if the i-th digit of the password is equal to j. Transitions are handled by searching for the next occurrence of the next digit and updating the dp value accordingly.

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

    And this problem should deliberately retain the time complexity that can be achieved by using dynamic programming, because if a greedy approach is used, m can be larger.

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

    Yea me too. First I misread the problem, then I overcomplicated it with dp, After that fortunately I just had enough time for D

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

    Can you describe your DP approach? I'm trying to learn DP these days.

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

Can't think of any approach for C? Someone please provide some sort of hint like in which direction should I think?

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

    There is a strong independence between each digit of the final number. You can consider the optimal scenario for each digit and try to solve this problem using a greedy approach.

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

    If you know the problem colorland in Kattis, this problem is similar to that, you build an implicit graph from the start of the string to an "INF" node and see if there is a path of length <=m from left to right. (Note: you can greedily jump as far as possible!) You could maybe see my solution for more clarification.

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

    Our goal is to create a password that contains any subsegment that does not exist in the given string as a subsequence in other words, We don't need to generate all possible subsequences of the given string, but We need to check for a combination that will not exist as subsequences this way we can use dp to optimize our brute force solution to find a sub-combination that will make a valid password.

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

can anyone share their greedy/binary search approach for C?

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

    Sure, to solve it using greedy approach, one might try to think of how to build a string that would not be a subsequence.

    To do so let's think of positions of possible values of first digit of resulting password. It definitely should be from l[i] to r[i]. For all such digits let's find their first positions in the string. I claim that it is always beneficial to take digit with maximum value of first appearance. Why? Well, because it destroys more possible subsequences (since we cut off the largest prefix by doing so). See my submission for more details: 211498000

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

      Nice approach, very easy to understand, tysm

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

      Very nice solution! Thanks

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

      I understood your approach but could you please tell me what this line does?

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

        Of course, for pos[d] I store indexes where digit d appears in s (in reverse order). Now, when I try to greedily build this “bad” subsequence I interpret first appearance of digits as a candidate that can now become new digit of resulting password. When I have chosen this new digit, I know its position in s (it is p), so for all digits from 0 to 9 I want to stop considering ones which happen to have positions <= p.

        Storing in reverse order is very beneficial because it let’s me to delete element from a vector in O(1) and resulting complexity of solution is O(n + 10 * m)

        Hope this helps

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

    Take an index starting from the beginning of the given database string. Now consider first range of allowed characters for first digit — [l_i — r_i], move the index forward until all characters in this range have appeared at least once (I used unordered_set for this). Similarly, do this for all password positions, index always moves forward. If index reaches end of string while there are still digits in password left to be considered, answer will be yes, otherwise no.

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

    Did someone try it using binary search? I did it but Gave TLE for me :(

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

Haha, I sucked, couldn't solve D.

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

can anyone explain the approach of problem C ?

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

    Here's my approach, Take an index starting from the beginning of the given database string. Now consider first range of allowed characters for first digit — [l_i — r_i], move the index forward until all characters in this range have appeared at least once (I used unordered_set for this). Similarly, do this for all password positions, index always moves forward. If index reaches end of string while there are still digits in password left to be considered, answer will be yes, otherwise no. 211508945

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

Can anyone share their approach for D?

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

    just find the largest decreasing subarray of input and avoid it, then we get the maximum rating

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

    Let's denote prefix sum to position $$$i$$$, by $$$pref[i]$$$. If you think about it a little, it's easy to see that answer must be in $$$pref$$$ (unless there is no positive value in $$$pref$$$). Let's say that our initial answer is 0, and iterate over $$$pref$$$. Assume that before position $$$i$$$ we found some answer $$$x$$$. Now, we have to find some conditions to determine if it will be optimal to change our answer $$$x$$$ to $$$pref[i]$$$. Surely, it won't be optimal, if $$$x > pref[i]$$$. Otherwise, let's denote the prefix sum to position $$$i$$$, if $$$x$$$ was the threshold by $$$pref\_ans$$$. If there is some value $$$min\_val$$$ in $$$pref[i]$$$ on positions $$$[i+1, n)$$$, such that $$$min\_val + (pref\_ans - pref[i]) < pref[i]$$$, then it will surely be optimal to change our answer to $$$pref[i]$$$ (because if $$$x$$$ was our answer, prefix sum here will fall below $$$pref[i]$$$). Otherwise it won't.

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

Does someone knows if in problem E, DP with cost $$$O$$$($$$n^2$$$$$$k$$$) is hackable, I got TLE :/ 211505619, but I have seen some AC 211506794 or 211522102

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

Anyone did D by binary search???

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

    i want to know the same.

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

    You've to be sure about monotonicity of your search space whenever you're going for binary search, which in this case is not monotonic.

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

Was c really that easy or I guess i am too dumb as 4k people solved it

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

    C was easy. but the statement(possibly poor) made it a bit complex.

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

sorry but problem C statement was poor. you should have highlighted "i-th digit of the password has to be between li and ri, inclusive" with a bullet point :'3

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

Problem B, why is the answer to this 1 and not 2 ? 1

1 100000000

1 99999999

1 2

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

Any good hint for E, please? Want to solve it myself

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

That's truely educational round and i learned i should quit cp

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

Anyone else who felt that D was easier than C?

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

Can someone explain what is wrong with this solution?

It is failing for following in online judge but is working in my local machine: 1 2 1 99999999 1 1

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

    You're adding an additional 1 after 2nd if case.

    if(xc <= 0 and yc >= 0)
        ans = min(yc, yb);
    else if(xc <= 0 and yc <= 0)
        ans = 1; // <------- it should be 0
    else if(xc >= 0 and yc <= 0)
        ans = min(xc, xb);
    else
        ans = min(xc,xb)+min(yc,yb);
    cout << ans+1 << endl;
    
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Any hints for E?

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

Problem E when I do rolling table using two 2d arrays : oh no !!!, you are too slow !!!, get TLE

Problem E when I do the same rolling table using one 2d array by clever variable saving and iteration : Congratulations !!!, you are accepted !!!

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

It's kinda strange but in E the small trick with changing all zeros with ones and ones with zeros, if the number of ones if more than half, works and makes O(n^2*k) solution pass. I think it's strange and if it's not the intended solution, time limit should be smaller. 211535929

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

What do you guys think is the rating of problem C and D?

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

can anyone share approach for D?

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

Can anyone find a testcase where my code for B fails?

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

Why is this solution showing MLE in pypy3? I was shocked by this. It's AC in C++ Link: https://codeforces.com/contest/1845/submission/211534174

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

I'm so dumb that after reading the statement of C, I thought it is digit dp and waste for an hour to write. Then I realized it does not require to make the password from l to r(like 40 to 50 I thought they were 41,42,43...), it is just in range, digit by digit. I solved by the way, but it still got me negative delta. Hopefully for better luck next time :((

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

as a green, Hope to come close to cyan.

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

Problem C ... Can anyone tell me how the answer here is "yes"

s = "01342104424232424004113131423112311240" ,,,,
m = 5 , l = 23004 , r = 24244

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

    Could you write the case more clearly?

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

    23104

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

      Thanks I think I misunderstood the problem.

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

    because you can choose 2 3 1 0 4 :

    01342 -break- [104424232424004113131423112311240]

    10442423 -break- [2424004113131423112311240]

    24240041 -break-[13131423112311240]

    13131423112311240 -break- []

    [] no more elements to choose [4,4] from hence answer is yes

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

I hate how non intuitive problem D is. I am still not able to convince myself how the prefix sum just behind the minimum subarray is the answer.

Edit: Got it now. If we choose k = prefix[i] and if there exists a j(>i), such that prefix[j] is the smallest among prefix[i+1...n], then the elements from i+1 to j would contribute effectively nothing to the ratings.

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

    exactly, can someone share how they reached this conclusion and their thought process during solving the problem?

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

      After you fix the prefix sum till index $$$i$$$ as the current $$$k$$$, you can keep adding elements to your current sum until it dips below $$$k$$$.

      This will be when the sum starting from index $$$i + 1$$$ just becomes negative, which is when the prefix sum becomes less than $$$pre[i]$$$.

      Since we can't go below $$$k$$$, we just stop at $$$k$$$. This means we just ignore this subarray and do this process repeatedly: find the next index where the prefix sum is less than the same at our previous position, ignore it (since the subarray sum will be less than zero) and set that as the new position.

      If no index has prefix sum less than that of our current position, our subarray can be extended till the end of the array since the sum will be positive. This will occur only at the minimum of the prefix sum array (let us call this index $$$mn$$$).

      So, the answer when $$$k = pre[i]$$$ will be $$$pre[i] + pre[n - 1] - pre[mn]$$$ (or just $$$pre[i]$$$ if $$$i \geq mn$$$).

      So, the maximum value of this expression will obviously be $$$\max_{i \leq mn} (pre[i]) + \max(0, pre[n - 1] - \min_i (pre[i]))$$$.

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

    I solved this question and I still don't understand the intuition behind it.

    Here are some less complex observations for problem D :

    1. Let's make a prefix array first. Now, our answer is definitely from one of the values in the prefix array.(or 0 if all prefix values are -ve). Why? cuzz we won't let our rating fall from a point where we reached , so out k must be a value we reached.

    2. We can calculate answer for each prefix value (though it's easy to prove that optimal value is always a local maximum).

    3. Begin traversing the prefix array now how to calculate the answer from this value of k = prefix[i] ? ---> Answer is : [ Σa_i + (maximum distance you go below from k in you prefix array) ]

    How to prove this ? ----> You can think of it as : When you add something -ve that takes your prefix value below the threshold k, you actually add some EXTRA to your answer to keep it fixed at value k. Hence , whenever next time when again prefix value goes below k , again add value to EXTRA to keep it at k. Finally you will notice you added total EXTRA = max(0 , k — min(pref[i])).

    --> min(pref[i]) is minimum prefix value that we reached.

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

      Thanks for the explanation, I tried to do something similar by fixing the answer as any one of pref[i] values. Then I calculated the max rating possible when k = pref[i] by adding all +ve values after arr[i] to k, since the rating won't go below k. However where this goes wrong as you might have guessed is that if I fixed k as threshold from the start the rating would not be k when I reach arr[i]. Is that where the (maximum distance you go below from k in you prefix array) in your solution comes into play? I still do not understand what Σa_i is tho, could you please clear that?

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

      What could be a possible rating for D ques I thought on the same line but was not able to find the resultant score by fixing k in constant time.

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

    I did this for every i, k = prefix[i]; resulting score = prefix[n] + max(0, prefix[i] — min(prefix[i + 1]....prefix[n]))

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

I had a weird idea for C, for a password to not be a subsequence there must exist two indices in it for which it's not possible to get a subsequence from the database, we can brute force for the indices and the possible numbers on them, if these values are indeed the pair of two indices, then either all the occurrence of one is left to the other or this indices maybe belong to the the first m and last m of the database, pretty weird I know :p, someone thought something similar? This is idea, I don't know if it works

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

    WHAT I DID STARTED WITH INDEX POINTER 0 NOW I TRAVERSE THE L AND R STRING FROM STARTING FOR EVERY DIGIT (0 , 9) IN [ L[I] , R[I] ] FOUND THE MAXIMUM INDEX IN MAIN STRING THEN SHIFTED THE INDEX POINTER TO MAXIMUM

    IF NO CHAR IS PRESENT IN MAIN STRING — > HENCE NO SUBSEQUENCE CAN BE GENERATED -> "YES"

    PS : TC 2 HELPED A LOT :)

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

My idea for E. No idea if it's correct or not:

  • So first we notice that parity of the sum of position of 1 changes if k is odd. Other wise it doesn’t change
  • So we make it dp i,j,bool We will now try to take the ball at ith moving left or right. And ball ith can only be at jth if dp[i][j][bool] has some way to arrange. So once we have dp i,j,k, we can see that the balls occupying before pos i can be anywhere between its initial position and i-1 if we know the parity of the left over k from dpi,j,bool
  • We also need to compute the min cost and whether it is possible to move ball i to some position j, because it will shift everything on its way
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

why cant D be solved using Ternary search ?

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

    I believe it’s because your function might evaluate to the same value for intervals of input, and if that’s the case your ternary search will not be able to decide which side to move to.

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

    Because $$$f(x)=f(x+1)$$$ might hold for some cases where $$$x$$$ represents $$$k$$$ and $$$f(x)$$$ represents the value got with $$$k=x$$$.

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

Please anybody give me hint in D problem. I don't know why am I getting wrong answer. Submission --> 211537213

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

    I've tried, scroll above

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

      First time I saw your solution, I didn't get it. After drawing graph of prefix array everything was crystal clear. That's not very hard problem. Lol:)

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

Any traders realized that D was just maximum drawdown in your average backtest haha?

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

    lol. I thought about my cf rating chart while solving D

»
10 months ago, # |
  Vote: I like it -22 Vote: I do not like it

what is the test that hacks problem a?

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

Please implement same rating system as problem D here too. I don't want to go below expert.

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

what should be correct output for this test case in problem C

1
805544605628
1
7
3

if correct answer is "NO" then please explain me why

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

    Oh now i got it
    it's between li and ri inclusive i.e. it's range rather than ri or li spent whole contest on C :<(

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

    it is invalid input, every l[i] <= r[i]

    if you mean l = '3', r = '7', then answer is "YES", u can choose '7'

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

As a gray shekhar_46 user I wanna Green after this contest

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

Worst E question I have ever seen!..

If it has a solution better than $$$O(N*K^2)$$$ that I cannot be able to find then it is okay but if the original solution is to make optimizations on $$$O(N*K^2)$$$ then it is really bad!

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

    there exists n * k ^ 1.5 solution which is pretty nice and educative....sadly authors didnt expect cubic passing (i blame edu rushed preparation)

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

Can someone give a hint to solve D using Binary Search?

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

    max(pref_mx — mn( mn after pref_mx ))

    answer mx_pref

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

author of D pranker ):

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

Here's an O(N^2K) solution to E that passes in 655 ms. submission

There are no optimizations other than the fact that if more than half the array is ones, you can swap them with 0s. This reduces the solution by a factor of 2.

The original solution (without the optimization) passes in around 3000 ms

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

I don't think an E-question that blocks time is meaningful.

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

Is it possible to solve D using ternary search ?

»
10 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Lol! I solved A using the logic of UnboundedKnapsack rec code....

»
10 months ago, # |
  Vote: I like it -27 Vote: I do not like it

When will there be a tutorial? Or do you already have it but I didn't see it? 什么时候会有教程?或者说已经有了只是我没有看见?

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

Very Important I am a Newbie — @787. Yesterday I solved one question in the round successfully but my rating remained as it is. Why my rating did not increase even on solving one question

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

why in custom invocation my solution (of problem A) is working correctly, but when I submit, it says "Wrong answer on test 1" (that is example)?

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

does anyone know why my ranking did not change even after solving the C problem?211519289

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

Easy Solution for C: 211519289

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

Hacks:

A: WA: 665; RT: 1; TL: 1; ML: 1.

B: TL: 2.

C: TL: 85; WA: 2; ML: 1. [An uphack to C (TL) has been counted.]

D: TL: 14; WA: 3. [An uphack to D (WA) has been counted. ]

E: TL: 2.

F: (None.)

Total: WA: 670; TL: 104; ML: 2; RT: 1.

Count: 777

Could anybody explain why there are so many hacks?

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

Why was problem D so easy?

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

So many Cs and Ds were hacked via TLE. Please explain how to get a code to give TLE. I tried larger inputs, but the system constraint is that input can't be bigger than 256kb. So I could only make use of some of the input constraints.

It can be done using generator, got it now. Sorry for naive question, I'm new to hacking.

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

I guess the idea of problem c was taken from https://cses.fi/problemset/task/1087

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

This was a fun round. Cant wait to become rated.

»
10 months ago, # |
  Vote: I like it -26 Vote: I do not like it

My submission was having an indexing issue in all cases. Still it passed during contest. But it gave RE on test 3 in system tests. Fixing the indexing issue gave AC.

Why it did not RE during contest?

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

    Participant hacking test cases will be added after the hacking phase, maybe you failed one of them.

    That means if one participant being hacked, all similar solutions will be failed in the system testing phase.

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

      Since it failed on third test, it means they kept only 2 tests. They should have kept more tests

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

        There were at least 3 tests for B during the contest (the submissions show some people getting wrong answer on test 3) so if it was an indexing issue (e.g. leaving the bounds of the array) then the FST was probably because of undefined behaviour. During the contest it didn't cause issues, but you got unlucky with the system tests and accessed a part of memory that you couldn't access.

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

    What are you talking about? You haven't even participated to this contest.

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

For Problem D, I have tried binary search on answer. I'm getting WA on test2. please can someone help me rectify my code. 211583193

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

    I don't think the answer k satisfies some requirement to apply binary search. Assume the right answer is k, then 0 and inf will get lower rating than k. It is at least a single peak function that cannot apply binary search. By the why, I guess it cannot be solved by observing the rating's pattern of different ks. I solved it by trying all possible ks that can be the answer. There are only O(n) candidate ks and it is small enough to pass the problem D.

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

      i got either 0 or anyone of prefix sum value will be the answer.. but how to find which one will yield the maximum rating. I tried binary search on pref sum values now.... but it is giving WA on test 2 ... case 51.... suggestion plss 211608959

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

I seldom solve the C in div2, but I solved it this contest and I think I will be pupil again. However, my A is wrong in fst. oh my god.

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

When got my rating up?

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

There was no rating changes for me after this contest even though i'm in div 2. Thing is, this is the first contest i've performed well in a while so i'm maybe being a bit paranoid but was this round declared unrated? i really hope that the rating changes were just delayed for a little bit

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

update rating when??

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

Problem C can anyone please explain the approach to get position of ith element in string using 2D vector nxt, is there a name for this approach , coz i have seen such code many times. submission:https://codeforces.com/contest/1845/submission/211443935

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

    Your link isn't accessible by the way.

    How I visualized it is like this: consider first the $$$m=1$$$ case. Obviously what we do is check every digit $$$d_1$$$ between $$$l_1$$$ and $$$r_1$$$. If $$$d_1$$$ does not appear at all in the string $$$s$$$, then we output "YES" because $$$d_1$$$ will definitely work. Otherwise if no such $$$d_1$$$ exists then there is no viable value for $$$d_1$$$, whence we cout "NO".

    Now let's try the $$$m=2$$$ case. For the first digit $$$d_1$$$ we do the exact same as above, but this time even if every possible $$$d_1$$$ between $$$l_1$$$ and $$$r_1$$$ appear, we might still be able to generate a valid passcode if $$$d_2$$$ doesn't appear in the string $$$s$$$ after $$$d_1$$$ does. To maximize the possibly of this happening, we will try to pick the first occurrence of $$$d_1$$$ to be as far right as possible, so that there is less digits of $$$s$$$ that can block $$$d_2$$$ from succeeding.

    But how do we do this? The $$$\mathbf{nxt}$$$ array is what comes into play here. Let $$$\mathbf{nxt}$$$ be a $$$10$$$ by $$$|s|+1$$$ array such that $$$\mathbf{nxt}[i][j]$$$ is the (1-based) position of the next occurrence of the digit $$$i$$$ after position $$$j$$$ in $$$s$$$, or INF if no such position exists. (Long sentence, sorry.) Then the algorithm will be something like this:

    j = 0 // initially we start having no digits of s covered
    for every d1 from l1 to r1
        if nxt[0][j] is INF // then we are done!
            print "YES" and finish
    
    j = max {nxt[d1][j] | l1 <= d1 <= r1} // jump as far right as possible
    for every d2 from l2 to r2
        if nxt[0][j] is INF // then we are done!
            print "YES" and finish
    
    print "NO" and finish
    

    This now obviously generalizes to any positive $$$m$$$, I trust you can carry on the analysis from here :)

    edit: minor typos, sorry

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

As ratings have been updated and hack phase has ended, when editorial?

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

Can anyone explain me dp approach of problem c

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

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

»
10 months ago, # |
Rev. 5   Vote: I like it -14 Vote: I do not like it


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

[DELETED]

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

Can someone please give complete , easy to understand explanation of Problem E explaining it in easier steps , it would be very beneficial as it seems very very difficult to even understand anything about the problem rather the problem statement and editorial is way too tough to understand , it would be very helpful

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

Hi im a newbie on cf, any tips to reach specialist? i get stuck in adhoc/greedy problems.

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

what do i do now??? please help

Attention!

Your solution 211471860 for the problem 1845B significantly coincides with solutions Isaac_Netero/211471860, musthang/211512249, lepsinach/211512269, atulya_codes_/211516053, hatikyu/211516437. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.

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

Attention!

Your solution 211505041 for the problem 1845B significantly coincides with solutions cpnhihori/211494126, Sk_4036/211505041, ShaRingan/211517241, techie_2304/211521482. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.

It's just a coincidence... I used a simple way of calculating the standard distance walked by Bob and Carol. In the first of the code, I included a standard library, then used a while loop for the testcases, then six inputs where they are now present, and then where Bob and Carol want to go—then initiated an integer with value 1 because they are initially in the same cell according to the question. Then used, the if statement for the conditions on their X-coordinate cells if they both wants go down or up with respect to cell A. Then calculate the absolute minimum difference between Bob and Carol with respect to Alice and add this difference to the value initiated with 1. Same condition Y-coordinate cell and same procedure. Then finally, print out the number of common cells traveled by both of them.

So I didn't copy it from any of the online sources. The code logic both are simple, so I request you to please consider my solution.

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

.

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

This is the first time I have received such a warning, and it is evidently a false positive. I have never used any online IDE or commonly published source for competition purposes. I believe this is merely a coincidence, as the solution to problem D is fairly straightforward. Although my rating was not affected since I participated outside of the contest, I would like to appeal against this conviction. Thanks!

Attention!

Your solution 211480048 for the problem 1845D significantly coincides with solutions coderbd/211480048, randomIsNotRandom/211495795. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.

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

why ratings are rolled back of this contest? will they be rolled over again?

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

why is it unrate now?

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

[DELETED]