amul_agrawal's blog

By amul_agrawal, 6 weeks ago, In English

Namaste Codeforces!

We are excited to invite everyone to CodeCraft-22 which will take place on May/31/2022 17:35 (Moscow time). It is rated for all people who are below yellow! (rating under 2100)

The Programming Club at IIIT-H organizes this event under Threads'22, as a part of our techno-cultural fest Felicity, IIIT Hyderabad.

There are 6 Problems with 2 hours to solve them. The scoring distribution will be released soon!

We have worked hard to keep the statements clean and the pretests strong! After the contest, step-wise tutorial and video tutorial will be released along with the code!

We hope you enjoy this contest!


UPDATES

Score Distribution: 500 — 750 — 1250 — 1750 — 2250 — 2750
Editorial is out.

Winners

Congratulations to all the winners for such an amazing performance.
Global Top 5
1. tourist
2. ksun48
3. noimi
4. jiangly
5. Um_nik

Official Top 5
1. JrNTR
2. YinJinRun
3. Remakee
4. see_wo
5. HowtobeRed

We will send a CF personal message to the winners of the T-shirts soon.


PRIZES

The following twenty lucky participants receive a T-shirt:

  • Top 10 Indian participants.
  • Random 10 from top 100 (ranks 11-100) Indian participants.

These ranks are determined from the combined unofficial rank list. People who have their Country set to India in their CF profile will qualify as Indian participants.

We are giving T-shirts to Indian participants only to avoid logistic issues that we have to face during international delivery. We apologize for this limitation, we will try our best to bring international prizes too from next year.


Thanks to NEAR for supporting this round, details can be found in this post.

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

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

All the best everyone

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

    What F*ckhead created problem C ?

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

      It is an interesting problem, I think. I solved it, and it seems very easy after you solved it (it is not sarcasm)

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

      Whats wrong wid it..? It is really a good problem and if you could not solve it, that does not mean problemsetters are bad. Infact they are really good.

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

        There are "hidden" edgecases in the problem that makes it frustrating for the ones not seeing them. That does not make it a bad problem, but explains the frustation.

        In this case the more obvious edgecase is that there can be less than 2 '1's, the less obvious edgecase is that by limit of $$$k$$$ the only valid move is moving the one '1' to the left.

        However, I also do not think that such "edgecase hiding" problem statement is a good problem per se. It remainds me more of a chrismas riddle than a serious problem.

»
6 weeks ago, # |
  Vote: I like it -100 Vote: I do not like it

An indian contest, we expect a lot of math problems!

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

    You showed us how to get a negative contribution in the fastest time.

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

      Ngl, as an Indian, I don't get why people were offended or whatever. The comment wasn't that bad, imo

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

        I think the reason is many people don`t like math problems.

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

what is the meaning of orz.

»
6 weeks ago, # |
  Vote: I like it +34 Vote: I do not like it

Just take a moment to appreciate how cool the poster design is. Also where will the video editorials be posted ?

»
6 weeks ago, # |
  Vote: I like it +45 Vote: I do not like it

Feels good to see myself under sponsors:)

»
6 weeks ago, # |
  Vote: I like it +141 Vote: I do not like it

Since this event is sponsored by EA, how many dollars needed to unlock problem B?

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hows is this made possible , i mean the organizing and stuff

»
6 weeks ago, # |
  Vote: I like it +58 Vote: I do not like it
orange
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope to see brilliant problems, hope new colors for all

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Oh cool round

Hope! I will able to solve at least 1 or 2 problems haha :)

»
6 weeks ago, # |
  Vote: I like it +26 Vote: I do not like it

Why only Indian?

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

    The prizes are only for Indian participants to avoid logistic issues faced during international shipping.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope I can get a green color in this contest!!!

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

Hope some positive rating change. Have become pupil from expert in the past few contests.

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

Namaste Codeforces!, Great to see the Indian contest

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

Time to change my profile country to India.

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

Yeah!! Less goo!!! ;)

»
5 weeks ago, # |
  Vote: I like it -14 Vote: I do not like it

Done

»
5 weeks ago, # |
Rev. 3   Vote: I like it -93 Vote: I do not like it

upvote or bad luck for this contest

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

Tis gonna be crazy..IIIT HYD (One of the best institutes in INDIA ) <3

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

    One of the best? Seriously bro? Its undoubtedly the best one

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

Although this is an Indian game, I don't think the following conditions are very reasonable...

Random 10 from top 100 (ranks 11-100) Indian participants.

Can players from other countries also participate?

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

    Hey!

    I am really sorry. This year our logistics allow us only to deliver T-shirts within India. For future years, we will try our best to bring international prizes too.

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

    yes anyone can

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

Hello amul_agrawal To count as an Indian participant, do you have to live in India, or simply be of Indian heritage?

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

    Hey!

    Thank you for asking this, I realize that the prize distribution which is written in the post is indeed a little unclear.

    The purpose of giving T-shirts to Indian participants only is to avoid the logistic issues that we have to face during international shipment. Hence, by the Indian participants, we mean the people who have a home in India, so that we can deliver the T-shirt there. People who have their Country set to India in their CF profile will qualify as Indian participants.

    Apologies for this confusion. I will update the blog soon with this detail.

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

on account of the overwhelming interest of competitive programmers to avail this round's T-shirt, here is a helpful link.

»
5 weeks ago, # |
  Vote: I like it -12 Vote: I do not like it

good luck for Every One

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

great to see a contest organized by one of the prestigious college of India.

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

It is the time to see my new color wish me luck (:

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

Very Excited for this Round !!

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

Expecting a good quality ques and super excited for the round.

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

wanna hit specialist so bad wish me luck

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

    Becoming specialist today means speed-forcing A,B,C. Let's see if you can?? Hope for the best . Prepare for the worst

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

I hope to see Hamo-ElTe5a is in the top 10 in the standings

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

The scoring distribution?

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

You are all freaks ;)

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

How's The Josh guys?

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

[delete]

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

all the best guys, hope to see your colour change

»
5 weeks ago, # |
  Vote: I like it -9 Vote: I do not like it

Very interesting D

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

    hint?

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

      Problem requires multiple subtask.

      Subtask 1 hint: In which subarrays element at index i will be the maximum

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

      define l[i] as the max index such that l[i] < i and a[l[i]] > a[i], r[i] as the min index such that r[i] > i and a[r[i]] > a[i]. Then for each i you need to find indexes l' and r' with the max sum of a[l';r'] such that l[i] <= l' <= i and r[i] >= r' >= i.

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

lmao. Was C so easy that so many people solved it? Implementation seemed so difficult.

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

    Just move a 1 to the right if you can, and then to the left if you can.

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

Can someone please tell me what's wrong with my code for problem C? https://codeforces.com/contest/1691/submission/159053938

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

    ans is 10 but you code gives 11

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

    you didn't look in corner cases try, like if i can move the one to left corner of the array, if i can move the right 1 to right corner of the array, if i can move them both extra ... example :

     1
     10 4
     0010000000
    

    it should give you 10 not 11.

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

 I think we need to block meggage when ongoing contest. Ban++!

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

    I started codeforces recently and got super mad at cheaters but now I stopped caring. It happens every contest man. That’s why no one responds anymore. There are too many cheaters to do manual check, and they just find ways to trick the plagiarism detector anyway. It stops matter once you solve D or above

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

      If there is an opportunity to ban a sussy baka cheater, then why not to use it?

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

    If you are Legendary Grandmaster, you will not care about the cheater. So be stronger!

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

boring ABC, D classic segment tree. Thanks for the round!

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

    did without segment tree code

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

      how?

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

        1-> there cannot be 2 consecutive positive values

        2-> replaced consecutive negative values with their sum as a whole they don't change the result

        3-> not considering the values which are zero

        4-> only checking till 3 length subarray by contradiction we can prove that
        if more than 3 lengths give us no we can do it in 3 or less than 3 lengths (but I checked till 50).

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

          4 -1 -1 4. How can we do in 3 length subarray? Is there something I am missing.

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

            I replaced the array as 4 -2 4 changing consecutive negative values with a single one

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

            He said that he is replacing all the consecutive negative numbers with the sum of them. Anyway, that approach fails for this:
            1
            9
            12 -39 44 -36 30 -14 8 -9 18

            I had to submit it again and lost around 400 points, also I could have completed E if I had not seen that test case after submission.
            Very unlucky day for me :(
            Still not sure whether my solution for D will pass or not

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

              Wrong answer on test case 65 :(

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

              I have written a brute force method in D checking all the positive position pair wise which is n^2 but is still passing.

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

                I have hacked your submission now. I wonder how they missed to add this basic case of alternating 1 and -1 in system tests.

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

                  I have even messaged them to add the test case which I have posted in the above comment. But still, they didn't add. Is it not allowed to add any test case during the contest?

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

                  How to hack after the contest?

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

                  only >=1900 rated people can hack after contest

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

                  Yes, it's a basic test case and they should have added it. I have asked the setter to the add the case. I think it will be reevaluated.

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

          Can explain more on how this work? like if the testcase is 5 {-4 4} {-4 4}...(same for n times) 5, can it still be processed?

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

        I did it using a slightly modified Kadanes, where I checked if:

        (Max sum till index) $$$>$$$ (Max element in subarray under consideration) $$$\forall$$$ $$$i$$$ $$$(a[i]>0)$$$

        and then checked the same in reverse. I don't have a proof to why this worked, just intuition.

        Code

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

          Your code prints wrong answer for this test

          6
          10 -8 2 4 -8 10
          
          • »
            »
            »
            »
            »
            »
            5 weeks ago, # ^ |
              Vote: I like it +3 Vote: I do not like it

            Damn, yeah you're right. I guess I was lucky.

      • »
        »
        »
        »
        5 weeks ago, # ^ |
        Rev. 5   Vote: I like it +2 Vote: I do not like it
        • lemma 1 : we should not have 2 consecutive positive integers
        • lemma 2 : consider 2 positive integers [a, b] which appear next in order in the array having a segment of negative integers between them whose sum is say p ie : a p b then max(a , b) >= a+p+b this we can check for all such segments.
        • lemma3 : consider 3positive integers [a, b,c] which appear next in order in the array having a segment of negative integers between them whose sum is say p1 , p2 ie a p1 b p2 c now among all the possible combination of order of max value of [a,b,c], we need to check for the case , where b is the smallest among all three. for other combination we can boil down back to lemma 2 (a p1 b , b p2 c) [you can do a little math ;)] so i checked for case of 3 numbers too
        • lemma 4 : n>3 positive integers can be broken into lemma3 then lemma 2 , so we don't need to check more .

        hopefully doesn't give FST

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

        I was thinking of using the maximum stack technique.

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

      Explain please

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

    solved with basic observation hope doesn't get fst

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

    How is D giving AC for some solutions with O(n^2) time complexity for other with completely similar logic

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

Approach for E?

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

    Do a classic sweepline. The main observation is that if at some moment during the sweepline there are open intervals of both colors, then all those intervals will be in the same connected component. Therefore, if there's a moment with both colors present, it's enough to unite all active intervals, and keep the interval with largest right endpoint of each color. Notice that during each moment in the sweepline, the set of active intervals will be either unicolor, with each interval belonging to a different connected component, or both colors will have one active interval. Therefore, when encountering a new interval it's enough to unite it with all intervals of the opposite color, and the complexity will be $$$O(nlogn)$$$.

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

    I like overkilling tasks, so here is my approach, but it's basically the same as previous answer. Let's create a segment tree, for every red segment we will add it to vectors of nodes covering this segment. So it's standard adding on range operation, instead of increasing some variable, we're pushing to vector. Now, for every blue segment iterate down the tree. When you're in some node, add edge to every red segment in this node, now all of them are connected, so it's enough to leave only one of them in vector.

    Repeat this approach for blue segments stored in tree and queries for red vertices.

    Now you'll get something like n * log(w) edges, where w is maximum coordinate of segments. So you can do standard DFS now.

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

Why does my submission for problem C (159077623) produce a different output on the server? On my machine it gives:

21
22
12

On the server it gives:

22
22
12
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.com/contest/1691/submission/159070540 What can be wrong with my submit of C? Thank you.

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

Approach for C??

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

    Just tedious casework...

            if(L && R && L + R <= k && cnt > 1) {
                cout << ans - 11 << "\n";
            } else if(R && R <= k) {
                cout << ans - 10 + !(L || cnt > 1) << "\n";
            } else if(L && L <= k && (R || cnt > 1)) {
                cout << ans - 1 << "\n";
            } else {
                cout << ans << "\n";
            }
    

    Here $$$cnt$$$ is the number of $$$1$$$ bits, $$$L$$$ is the distance from the beginning to the first $$$1$$$ bit, $$$R$$$ is the distance from the last $$$1$$$ to the end. And if $$$cnt=0$$$, output $$$0$$$.

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

      I mean, it's also possible to brute force all possibilities if you're lazy. The result only depends on the first and last digits.

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

      thanks! got it now

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

    sum is minimum only if there are 1's on both the end points, for example: 100001 is better than 010100. Just check for closest 1's to index 0 and index n-1 Also priority should be first 1 at n-1 index than at the 0th index

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

    Every element except 1st and last element contributes at ones place and tens place. Last element contributes only to ones place. First element contributes only to tens place

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

GeeksForGeeks have working challenge (impossible) I tried this code for but couldn't get it to work.

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

The most ridiculous mistake I ever made was in today's E. I used the following function to check whether two intervals are intersecting.

Function

The intervals are passed by reference, and therefore change the order of the intervals in the original array. Fml :)

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

For me A,B,C where simple to guess but hard to prove.

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

    B can be proven by noticing that if there's at least an element that's unique in the array, then you can't swap it with anything. Why? Swap with a smaller is disallowed, and swapping with a larger element is also not allowed, bc the larger element now has the smaller element. Then just swap indices with the same integers, a way to do it is in the example.

    For C, any 1 that is not at 0th or n-1 index will add exactly 11 to the sum. So you just have to try to move a 1 to the back first, and then to the front.

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

OMG. It was my first contest in codeforces and I totally failed. In Problem B, I made sections with each size. like [1, 1,][3, 3, 3] by searching with Two Pointers. And I flipped the idx in each section. In upper example, the answer will be [2,1][5,4,3].

Then I got WA in pretest 1. I'm really curious about Problem B.

Why my submission failed in Problem B?

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

    u have change by index not section index

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

    Cuz if u flip the idx of a section with an odd amount of people, the middle person in the section has the same shoe as before. In ur example, person 4 gets his own shoe back.

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

    Bro read community guidelines. Don't post full code directly. Post in either spoiler or post link

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

What did I miss for problem C? 159077051

Will be grateful for an explanation :)

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

solved D for the second time(last time got hacked). Hoping not to get fst today.

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

Solved Di2D for the first time :)

Was the intended solution to find next and prev greater element for each one and then use range max seg tree to find a prefix and suffix for each element such that their sum > 0?

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

Start the goddamn system testing, I want to send my code.

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

Misread B, moved on. Failed C, moved on. Solved D in 20 mins. Went back to C, but still failed. Went back to B, and understood that I have misread it, yet failed again. What a round... I am quite confident about my solution for B (also for C but whatever), but I get WA in case 3... any help? 159066034

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

    I think you have done mistake in case when total 1 count is 1. Try this 7 2 0000100

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

      My code for C gets output 1 for this input. I may have some other mistakes, although I don't understand why my code for B fails.

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

    Case 3 of B is n=1

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

      Yeah, and my code for n=1 has output -1, isn't this correct?

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

    ok i missed

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

      But in the line right below, I fill ans[j]. I didn't go up to j because at index j I append i (wrap around).

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

    I got it... I actually am retarded.... I have print instead of println and I misprint.

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

    wrong output format Expected integer, but "-1-1-12" found (test case 3)

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

can anyone explain why I got a WA in A? I know there is an another solution but why this one got WA? 159035323

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

Is problem F kidding? I think it's even easier than problem C,for which I will consider its difficulty as *1700.

And I also would like to know why I got TLE on pretest 2 (the given sample to which the answer is 849) at the first attempt (nothing wrong with it in my PC) , and after I add two "inline" ,I got an AC.I think it may be the judge's fault, not mine.

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

    Or perhaps you're just really good at combinatronics

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

    Your pretest 2 fails not because of the judge but seems like it's the compiler. You are probably running your code with no optimizations. Try adding -O1 (or 2,3). It segfaults. Exploring why this happens further.

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

      plz can you tell me more details about it? for example how i can add -O1(or 2,3),and why i haven't encountered any fault like this when solveing other problems before?

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

        I'm not able to find the assembly to show you but the problem is that you use scanf("%d%d") instead of scanf("%lld%lld") (which clangd will warn you about :D). I'll try to find the exact assembly diff if I can, but this is the major problem.

        The reason your second code passed is that you luckily used some other I/O way. inline is usually useless in the same file, compilers are now smart enough :D

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

159066950 why i am getting mle on this code question b

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

    plz never use unordered_map.

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

      but lot of code using unordered_map has passed

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

      159039176 can u also tell me why i got runtime error on this code

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

        You always need to read all the input per test, even if you know the answer before it's all read. When n is 1 you return early and all the following tests will be read incorrectly.

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

        when n = 1 you should read the number $$$a_1$$$ .

        for example, the input is :

        2 1 5 3 1 2 3

        then you will find that your code reads "n = 5" in the second test case.

»
5 weeks ago, # |
  Vote: I like it -18 Vote: I do not like it

Problems were really very good and contest was very well balanced, Kudos to the problemsetters

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

Cheesing D by just checking some of the intervals. Happy hacking!

https://codeforces.com/contest/1691/submission/159019206

EDIT: Hacked by tourist, I'm honored!

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

    You need to check all intervals [i .. j] where either a[i] or a[j] is the largest number in the interval

    Someone hacked you before me :( Here is my testcase https://pastebin.com/6aBxXZuP

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

    I can't believe I got beaten to it by tourist because I somehow copied my testcase incorrectly. I'm so mad right now.

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

For problem B can anyone tell me why this code exceeded time limit for test 30? this is O(n) solution. Link to the solution. https://codeforces.com/contest/1691/submission/159016521

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

I made the array smaller and RE on test 30 of problem B,that i can't go blue this time,f**k the fst!!!

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

Nice problems and pretests

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

D was interesting Any simple solutions without segment tree ?

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

Isn't problem F too easy? The rerooting solution is so obvious, although the top rankings' solutions seem to be shorter.

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

E is waaaay easier than D. One more confirmation that proper tactic is to "read all the problems"

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

    Nope, D has 4 times more solves than E. It's your personal opinion.

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

      Of course it's my opinion. But nobody knows how many solves it'd have if swapped with D: do not forget that majority solves A->B->...

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

    I thought so too

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

I think the test set for problem D are not strong enough because I just tried a brute force kind of solution and it passed.I would request to rejudge Solutions with strong test set.

Here is my solution : https://codeforces.com/contest/1691/submission/159082582

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

159067765 this solution should be wrong. For test case:

10

100 -30 -20 50 -30 -20 50 -30 -20 100

It should give "NO". But the solution give "YES".

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

    And a large test case like this pattern can hack a lot of submissions.

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

This code for D got AC after the contest had finished, can anyone prove why it works?

https://ideone.com/mnFtIx

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

    Its similar to Kandane's algorithm. I had thought of the same at first but thought and I still think that this should fail

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

My brain during contest:

Spoiler (Problem C)
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Please Please ,Can someone please tell me what's wrong with my code for problem C? https://codeforces.com/contest/1691/submission/159087368

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it
Noticed?
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it allowed to add the test case by authors during the contest? Or only test cases which were used to hack is added automatically?

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

An interestingly balanced round. Had fun!

»
5 weeks ago, # |
  Vote: I like it -15 Vote: I do not like it

Hey amul_agrawal, akcube and others from the team.... The post says "It is rated for all people who are below yellow! (rating under 2100)"

However, after the contest, my rating has not changed... I assumed this was because solutions were not checked on main test cases yet, but that process is now complete.

I can see this contest under "Unrated Contests" on my profile... why is that so? I thought this was rated. It was a fantastic contest and I had a lot of fun trying my hand at the problems, thank you. It is not a problem even if it is unrated, I was just expecting it to be rated for me, since I am below 2100 rating.

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

    Have you checked your profile? It's already changed!

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

      Yeah, I checked 10-15 minutes ago and it hadn't till then. My bad, should have waited a while longer.

      I was confused by the fact that it showed the name of this contest under "All" on the contest page of my profile, but not under "Rated".

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

    Sorry, my bad. My rating changed just now (idk why it showed the contest under "ALL" and not under "RATED" though, maybe because of the checking time. I am new so I didn't really know).

    Thank you for the amazing contest

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

Why these O(n^2) solutions pass? Is there any additional neat trick that will reduce the complexity?

Submission 1 Submission 2 Submission 3

UPD: okay 2 of them hacked, the last one's is still AC

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

Oh god! I'm getting nervous for A and it's setting up or spoiling my mood for the rest of contest based on whether pretests of it are passed or not.

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

What is uphack? I still got AC after being hacked in problem D. Even the rating changed. I don't understand. Someone please explain if you know something. This my submission for D

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

    According to me the hacking is open even after the contest ends for those who have rating greater than 1900. Your code has passed the the testcase provided by the contest writers but there maybe some testcase on which your solution may give Wrong Answer or Runtime Error or Time limit exceeded on which your code got hacked.

    Later these hacking testcases gets merged with the system testcases, so if you will try to submit the same code after some time you may get WA or TLE.

    I am not sure of the rating changes though, according to me they will be updated after all solutions are re-judged.

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

      No. Uphacking doesn't change contest result and rating changes. It is for adding test cases for future practice submissions or virtual submissions. It doesn't rejudge contest submissions.

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

I am never rerooting again :')

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

    nice profile pic and name bro.. only indians can have this much of creativity

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

      to get so many upvotes just say something about india and indian user will show their presence :)

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

    I dont think it needs so complicated transformation?

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

      Yup, It can be reduced to half it's size. I maintained dp states in a little more detail than i needed

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

        I only kept the size of each subtree if the whole tree is rooted at 0, then do some calculation.

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

Indian students and colleges are organizing such contest . Great to see that indian education system is improving :) | but this will never happen in tier 3 :(

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

how can one know if he/she has won the random tshirt between 11-100 rank, i am ranked 64 is there any form to fill? or way to know?, this is my first time so pls help.

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

    Just check your notifications their would be a notification..

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

The idea for A was so straightforward and I had to use pen and paper and only got the right approach half an hour into the contest

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

Very interesting problems. About D, my thoughts went in the same direction of this https://codeforces.com/blog/entry/103240?#comment-917608, but i am getting WA (https://codeforces.com/contest/1691/submission/159073623).

Any thoughts why?

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

Please any1 explain the C problem.I am not able to understand the tutorial :/, what he is exactly trying to do.

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

    The idea is to look at the contribution of each $$$'1'$$$ to the value of the string. Fix some string $$$s$$$, for example $$$s = "100101"$$$. There are three types of positions that a $$$'1'$$$ could occur in:

    1. Middle position: some $$$0 < i < n - 1$$$ with $$$s[i] = '1'$$$. Notice that such index appears in two substrings of length two: $$$s[i - 1]s[i]$$$ and $$$s[i]s[i + 1]$$$. In the first one, the $$$'1'$$$ will have value $$$10$$$ and in the second one, the $$$'1'$$$ will have value $$$1$$$, resulting in a total contribution of $$$11$$$ to the total score.

    2. Leftmost position: $$$i = 0$$$. In this case, the $$$'1'$$$ is only a part of one substring: $$$s[0]s[1]$$$, and its contribution is $$$10$$$.

    3. Rightmost position: $$$i = n - 1$$$. In this case, the $$$'1'$$$ is only a part of one substring: $$$s[n - 2]s[n - 1]$$$, and its contribution is $$$1$$$.

    Notice how since the number of $$$'1'$$$ s doesn't change in swaps, the best thing to do would be to lower the contribution of some $$$'1'$$$ s in the string. So, we will first try to bring some $$$'1'$$$ to the rightmost position (since its contribution there would be the smallest), and then, whether it succeeds or not, we try to bring some $$$'1'$$$ to the leftmost position.

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

For task D, there are many O(n) solutions, which doesn't seem to be really correct (I can see they have been hacked after contest had ended).

So I have 2 questions:

1) How to make a hack after the contest has ended? I can't find any possibility on codeforces gui.

2) Is it fair to keep ratings unchanged, knowing that "valuable" task was accepted and points were counted by a mistake (or, speaking more rude, by contest authors fault — weak system tests) ?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +10 Vote: I do not like it
    1. This is known as Uphacking, available to Div 1 participants, you can check Mike's blog about it.
    2. The official rating and ranking is not affected on the basis of uphacking, but in this case, since the Main tests allowed even O(n^2) to pass, I believe they should be rejudged, rest all depends on Mike and the contest authors!
»
5 weeks ago, # |
  Vote: I like it -13 Vote: I do not like it

I do not like this contest i quit codeforces

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

    Yeah sure u can.

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

      I just want to get downvotes bro! I also know problems were good as usual

      Spoiler

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

Plz rejudge the solutions as many would fail for the D ques.

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

i thought it was only mine, but when I checked other users who got rated in this round, the time they participated in the event changed to 1970screenshot link

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

Why is this contest suddenly unrated for me all of sudden? (Although I spoiled this contest very badly)

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

    I was expert for 2 days and then it became unrated :(

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

      There you go, You are back to Expert again. Good Luck in today's Contest

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

why the ratings are not updated after this round? what has happened?

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

My answer matched it was just coincidence