AdvancerMan's blog

Codeforces Round #610 (Div. 2)
By AdvancerMan, history, 5 years ago, In English

Hello Codeforces!

We're glad to invite you to Codeforces Round #610 (Div. 2), which will be held on Dec/24/2019 17:35 (Moscow time). It will be rated for all participants with a rating below 2100. You will be given six problems and two hours to solve them.

The problems were invented and prepared by the team from ITMO University: Supermagzzz, Stepavly, AdvancerMan, unreal.eugene, MikeMirzayanov.

Special thanks to MikeMirzayanov for great systems Codeforces and Polygon and coordinating round preparation.

UPD1: Special thanks to the ITMO University testers team: budalnik, Alexxx, Darui99, golikovnik, sharepoLOVEDDD, Mr.Hakimov, zergey.gad, MeowMr, Ilya-bar, 1ncendiary

There is an interactive problem in the round. You can read the guide for interactive problems here.

UPD2: Scoring: 500 — (500 — 1000) — 1750 — 2500 — 2500

We hope you will enjoy the problems. Good luck, wish you a high rating!

UPD3: Congratulations to the winners!

  1. Tsypkokokokoko
  2. K.Yuuki
  3. hyhtsdy
  4. ptica
  5. junukwon
  6. gumnam
  7. AnotherRound
  8. conqueror_of_obd
  9. rtilikay
  10. p1rattttt

Editorial will be published soon.

UPD4: Editorial is out!

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

Comments Comments (209)
| Write comment?
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Any subtasks?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it -184 Vote: I do not like it

    This is an online contest so there will be no subtasks

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

      He seemed to mistake subtasks of problems to subtasks of pretests. Why is everybody going so hard on him lmao?

      → Reply
»
5 years ago, # |
  Vote: I like it +286 Vote: I do not like it

I am very worried about the fact that Mirzayanov’s pawns can hold two contests a month, while the rest are waiting in line for six months

→ Reply
»
5 years ago, # |
  Vote: I like it -35 Vote: I do not like it

Hello everyone — Good luck for all I hope I can become a Candidate Master after contest

→ Reply
»
5 years ago, # |
  Vote: I like it -149 Vote: I do not like it

Before round:

Round is rated for Div.2 participants

After round:

UNRATED!

Sad story......

→ Reply
»
5 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Finally there is an interactive problem after 9 rounds ! :D

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +58 Vote: I do not like it

hope interactive problem is not a binary search. pleaaase

→ Reply
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

are there interactive problems in ICPC contests !

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it +16 Vote: I do not like it

hope for short statements like the last round !

→ Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

it's look like interesting contest

→ Reply
»
5 years ago, # |
  Vote: I like it -13 Vote: I do not like it

Can someone please explain what is an interactive problem and whats the difference between and regular problem and an interactive one?? Bcuz i did not really understand the meaning by reading the blog from MikeMirzayanov :) tnx for your help!

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

    Interactive problems(over simplified): the input isn't given all at once, or it's in a "Q&A" style.

    → Reply
»
5 years ago, # |
  Vote: I like it -23 Vote: I do not like it

Which problem will be Interactive ?

→ Reply
»
5 years ago, # |
  Vote: I like it -20 Vote: I do not like it

I just finished my graduate entrance exam.It is so excited that I can join contest now.

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it -25 Vote: I do not like it

Excited about the contest after a long break.

→ Reply
»
5 years ago, # |
  Vote: I like it -11 Vote: I do not like it

Interactive problem and 20 questions ..

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can somebody help me with interactive problems

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

    you give the jury some numbers and it will give some information about that. then you should use this information for next question or guess the answer.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What interactive problem will be A,B,C?

→ Reply
»
5 years ago, # |
  Vote: I like it +115 Vote: I do not like it

I bet that 80% participants of this contest has no girlfriend. It's Christmas Eve!! Go hang out with friends!!

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it -6 Vote: I do not like it

[deleted]

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone provide link to the mirror website m1/m2/m3 I am not sure where to find it

→ Reply
»
5 years ago, # |
  Vote: I like it +23 Vote: I do not like it

Merry Christmas!!!

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it -21 Vote: I do not like it

Good contest

→ Reply
»
5 years ago, # |
  Vote: I like it -9 Vote: I do not like it

feeling orz................

→ Reply
»
5 years ago, # |
  Vote: I like it +50 Vote: I do not like it

Problem statements are longer than my hair.

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

Hope for strong pretests. Merry Christmas!!

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is test 6 for D?

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

Am I the only one who over-killed C with segment tree and stuff and later realize it could have been done simply:((

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

    Am I the only one who doesn't know how to do C?

    → Reply
»
5 years ago, # |
← Rev. 5   Vote: I like it +29 Vote: I do not like it

I think problem C has some problem

Problem C- In statement: 2 <= n <= 1e5

Whereas just changing maxn=1e5+5 to 2e5+5 changed an RTE to AC

This should be rejudged with proper input files and first ac submission should be counted.

UPD5: sorry seems like, I've missed the announcement

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it -7 Vote: I do not like it

    It's written 2e5 in C statement

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

      It was 1e5 at the start of the round and updated during the round.

      → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D?

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

    Solution of D :

    1. You can get length of required string and number of 'b' by asking two queries.

    2. String of 300 a's will give you value = 300 — n + no. of b's.

    3. String of 300 b's will give you value = 300 — n + no. of a's.

    4. Plug them to get above length and no of b's.

    5. Take a string of n a's and start locking the indexes in order by using provided answer and no. of b's left to be selected.

    → Reply
»
5 years ago, # |
  Vote: I like it +32 Vote: I do not like it

My approach for D, making at most $$$n+2$$$ queries: 67539477

First make two queries, one with 300 A's and the second with 300 B's to figure how many A's and B's are in the string, and therefore its length.

Notice that the edit distance from a string of length $$$k$$$ with all of the A's already placed is $$$n-k$$$ if and only if between no two A's we have more B's than in the hidden string (as then we could not make only insert-operations).

Using this, add B's before the first A until the edit distance doesn't decrease, then place the first A and repeat. Thus after the $$$i$$$th operation, we know a prefix of length $$$i$$$ of the hidden string. Thus after $$$n-1$$$ operations we know the entire string (as we know character counts). Including the first two queries, we make at most $$$n+2$$$ queries in total.

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

    To get number of A's and B's you can also query a single "a" first, and then an all "b" string of length equal to answer of first query.

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

      I think I did this, but I'm getting WA on Q5 with the comment:

      Do you know what is wrong?

      My solution is failing with input abababababababab, and the error message is

      wrong answer Line [name=s_17] equals to "", doesn't correspond to pattern "[ab]{1,300}"

      However, when I tested locally it seems to work, and I also added asserts to check that I never output empty strings. My code is below.

      http://mirror.codeforces.com/contest/1282/submission/67561919

      Thank you!

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

        I couldn't solve the problem, but I think you should look over here probably. This comment

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

        Hey simp1eton, Could you tell what the problem was. I am receiving the same verdict as you mentioned. I used 300 a's and 300 b's to find the length. Here is my submission 67569644

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

          I assumed wrongly how edit distance is computed. I think if your program throws and exits for any reason, the checker says that your program outputs an empty string

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

        I was also having the same issue. But later found that, when testing locally I was miscalculating the edit distance.

        This was happening because my program existed before and the testing program was getting EOF and probably taking it as an empty string.

        → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone help me why I am getting wrong answer for Div2 B1??? My approach- Sort the array. Check if you can buy all items till index 'i' supposing that you got i-1 item for free. 67533371

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

    Do you consider the case when you purchase the first item itself, and not for free?

    → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it 
    1
6 4 2
1 1 1 1 2 2

    Your program outputs 4 for this, but should be 6

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

      Can you please clarify your test case what are you taking?

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        The test case is as follows -

        1

        6 4 2

        1 1 1 1 2 2

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          Answer should be 4 right???

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

            No, you can buy all, choose the 2nd 1, the 4th 1 and the 6th 2

            Update — I think you somewhere forgot to do i += 2

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

              please explain solution of B1 i am beginner here

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

                Sure, for the case of $$$k = 2$$$ (which is easier actually, since you need to solve the problem in $$$O(n)$$$ time); first of all, sort the array on the basis of prices. Now try to understand the points mentioned here as to why they're true. Now, going ahead, since k is just 2, you either choose the first one and then keep taking 1 on 1 as the offer; or you take all goods on offer, the answer is the max of the two.

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

            with two 1's can take other two other 1's and with one '2' can take other '2', in all 6 while spending 1+1+2=4.

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

      Got it. We can apply the offer again and again. I thought that we can apply it only once. Wasted an hour on this.

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

    what is the hack of B2??

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

      O(k*k) Algorithms will not work. While there were no tests as such in Pretests.

      → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve B2?

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

    first sort all items. then you make a list with size k that ith element is the cost if you take i starting elements alone. for each item(after k initial items) you update the list.

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

      can you please elaborate more?

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
        ← Rev. 2   Vote: I like it +2 Vote: I do not like it

        Sort the array first.

        Try to understand the following facts -

        1. If not choosing to use the offers, you should buy only the first few(< k) items, and not from any later part of array.

        2. Once you buy some or all of the first k items, you would only use the offer now, and no individual buyings.

        → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain why I got TLE in the problem Div 2-B2 ? Here is the link to my solution.Solution

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

    Because PriorityQueue.remove() function has O(n) complexity instead of O(log n) in Java

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

1

6 17 2 6

0 0 1 0 0 1

7 6 3 7 10 12

Why should that give us 1 as an output? (Problem C-petya and exam) can someone help me?

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

    At t = 2, you can solve any one of the non mandatory easy problems

    → Reply
»
5 years ago, # |
  Vote: I like it +33 Vote: I do not like it

Ultra fast system testing

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it -59 Vote: I do not like it

Ok codeforces

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

    *your worst

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

    Hey man, your contribution is already -26. So I strongly recommend you think twice before you make a comment .

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

    I agree tbh. The problem statements are overcomplicated and the score distribution is really not balanced. Who decided to put D = E?

    → Reply
»
5 years ago, # |
  Vote: I like it +27 Vote: I do not like it

E was a very nice problem. Among the best I've seen in a while. Too bad I had a silly bug in my code during the contest.

D was also nice. Hats off to the authors.

→ Reply
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

One of the fastest one I've ever seen...

→ Reply
»
5 years ago, # |
  Vote: I like it +25 Vote: I do not like it

D&E are realy good problems! ABC — stupid idealess problems!

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +73 Vote: I do not like it

Hello Codeforces, I didn't see the notification that the bounds for problem C were changed. As a result, I didn't notice the change for a long time. Would it be possible to unrate me? thanks!

My first correct sub with wrong bounds: https://mirror.codeforces.com/contest/1282/submission/67543972 Changed to 2e5: https://mirror.codeforces.com/contest/1282/submission/67558110

→ Reply
»
5 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Am I the only one who did B by handling $$$K >= \sqrt{N}$$$ and $$$K < \sqrt{N}$$$ differently?

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

    Well, I was planning to do the same at first :D

    → Reply
»
5 years ago, # |
← Rev. 14   Vote: I like it +5 Vote: I do not like it

I'll post a screencast of the round within 12 hours. (I will also add those 5 minutes which I did not have enough to pass E).

UPD I hope the screencast will be available tomorrow at 07:00(MSK) by this link in good quality

UPD2 It is available

→ Reply
»
5 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Approx 25% of all ACs of D ended up in fst, the edge case being bbbb...300 times. This was an obvious edge case and I do not get why you guys did not include it in pretests. Was this deliberate by any chance?

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    Fortunately, Tsypkokokokoko hacked my solution with this test case and I managed to correct my solution

    Congratulations on your 1st rank, Tsypkokokokoko!

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

    Actually I do not understand what is the difference between bbbb… 8 times (as in test 4) and 300 times. What's more, I wonder why would anyone want to include the 300 constant in their program (and so, it's no longer an "Edge case")

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

      Well I was checking your code and it seems the rand() part saved you. try printing just "a" in the beginning and you will know.

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

        Oh, that's like the weirdest thing that happened to me for the past 2 years on Codeforces :P If I print just "a" in the beginning (which I tried to do, submit #1...) I get TLE 4 (which is the first monochrome test). There are MANY such tests up to #67, so idk why those solutions make it that far...

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

          Seem like you got really lucky :p

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

            More like time trouble :)

            With 5 minutes left, I couldn't figure out how to find |s| and I just made this leap of faith, haha

            Btw, I was 110% sure this would fail the systests and even now I don't know why it passed (there were soooo many monochrome strings)

            → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it -15 Vote: I do not like it

      My program uses aaa..aaa (301 times) as second query in this case and for some crazy reason it is not allowed. I would be very angry if this was an actual round for me, not the one where I do educational video.

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

        Guess, it's time to rewrite this one :D https://mirror.codeforces.com/blog/entry/62744

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it -16 Vote: I do not like it

          More like reread, and also the story with Golovanov399 and 22 vs 20. Yes, double standards.

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

            Rereading this particular fragment would be enough I guess:

            Answer: Do you fucking read your questions? I like that "I can't solve the problem with operations in statement, can you provide better operations for me?"

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

              Nope, this is not it. I didn't ask for a clarification. Also I'm not that mad to consider the problem bad because of small issue.

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

                Well, you don't have to build so literal analogies. It's up to you to decide what conclusions you leave for yourself from this situation. I just suggest you to think why you call not allowing string(301, 'a') "crazy" and compare this to that sentence from your blog.

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

                  There is a clear divide between ranting about the problem during the contest in a clarification and ranting about the contest afterwards.

                  Also I didn't call allowing crazy.

                  And yes, I already did admit that there is a resemblance, what's the problem?

                  → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Test 67 for D?

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

    bbbbb....300 times

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

      67542439 Can you help me with finding out what is wrong with this solution? It works with 5b's, and I don't see anything that would make it not work with 300 b's.

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

        your code is probably printing 301 characters somewhere.

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

          Thanks, I figured it out, it was because if there was 300 a's or b's, my code would continue after getting a query of 0.

          → Reply
»
5 years ago, # |
  Vote: I like it +52 Vote: I do not like it

Amazing system testing speed. Like

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem C, I created 2 sets one to store hard problems mandatory time and the other to store easy problems mandatory time. Every time I check first problem in Easy problem + a and first problem in Hard problem + b and i take the one which Solved eailer. then I check if any problem should be solve in this time and I add it I only update the answer if the time at the end <= the total time of exam

Why this idea is wrong ? 67550974

→ Reply
»
5 years ago, # |
  Vote: I like it +47 Vote: I do not like it

Checker for D is incorrect. This solution https://mirror.codeforces.com/contest/1282/submission/67555058 still outputting things after getting 0 as response for the test "b" * 300, but I got incorrect hacking attempt on this one.

Hack is here https://mirror.codeforces.com/contest/1282/hacks/603027

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

    In the problem statement it says that on such cases the checker will give an "arbitrary" verdict, which can include Accepted (depending on how the checker is written).

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Good evening everyone! Help me please understand what am I doing wrong on the second problem, so for the input (n = 4, p = 9, k = 2) and the numbers { 2, 3, 4, 5 } the expected output is 4, mine is 3. Thanks in advance!

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

    If you buy the 2nd good then it will cost you 3, and you will get the first one for free and you will be left with p = 9-3 = 6. Then just buy a good 4 for 5 and get good 3 for free. Hence finally, you have 4 goods.

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

    Offer can be used more than once. You can pick 3 and 5,you get 2 with 3 and 4 with 5 for free

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone tell what's wrong in this solution of D? 67559495

→ Reply
»
5 years ago, # |
  Vote: I like it +39 Vote: I do not like it

How come the pretests for D didn't include a single string with max length? It seems the longest string in the pretests had only 17 characters.

→ Reply
»
5 years ago, # |
  Vote: I like it +19 Vote: I do not like it

Can not understand why let $$$O(k^2)$$$ solution pass B2 pretest.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello. Please AdvancerMan could you help me understand why 67555899 got WA. The problem is that when I run locally the 5th case it returns the correct spell.

Thanks in advance

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it
    This is your output

    Check how you calculate the edit distance.

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

      that is exactly the problem. I am calculating the edit distance in a wrong way.

      Thank you so much

      → Reply
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I didn't submit because i couldn't solve Div2-B1. And i couldn't solve B because I kept thinking offer had to be applied once. I really think the setter should have clearly mentioned that :'( . Looking forward to next contest

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

can someone explain how to solve C?

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

I am getting WA for Problem D.

The checker says I printed an empty line (" ") which not acceptable , but my code doesn't print any such line.

Here it it : My Submission

Thanks in advance!

UPDATE : Resolved! :)

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

    > If the number of spells exceeds limit (n+2, where n is the length of the spell s, which is unknown to you), you will get the Wrong Answer verdict.

    That could be the reason

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

      Yup I did check for that. My code always prints n+2 strings , no more than that!

      → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    AdvancerMan can you please have a look?

    Thank you!

    UPDATE : Resolved! :)

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

      Your program prints no more than $$$n + 2$$$ strings but it doesn't print the correct answer to the first test as well. Your output for the first test:

      Code
      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Just came online to update this XD

        Thanks I messed up edit-distance part!

        Thanks for the help! :D :)

        → Reply
»
5 years ago, # |
  Vote: I like it +45 Vote: I do not like it

Awesome problemset, super fast system testing and rating change -> In a word a nice contest!

This contest is also exiting for me, because I found my mistake in code for problem C last minute and submitted 30 seconds before the contest ends and it got Accepted, and became blue after a long gap.

Thanks for the nice contest!

→ Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

div2 b is similar to house robber but cannot solve in the contest :(

→ Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

For a second I thought I can't solve B2 so i went for naive approach in B1. after writing some stupid long worthless code i tried B and solved it much faster and with less lines of code.Should have just sticked to B2.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

My solution for D got AC code. But it is wrong, because i write always n + 2.. Ok.. This solution on C++11 got RE code. Then this solution got RE too. Can anyone explain me, how is it working?

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

    Try exiting the program if a == 0 or b == 0 as soon as you get them. I don't know why that would give an out of bounds error, but I had the same problem.

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

      Ok thanks, it is really strange...

      → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't understand the WA message wrong answer Line [name=s_8] equals to "", doesn't correspond to pattern "[ab]{1,300}" on D. I tested my solution locally and I am not printing any empty strings.

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

Shoudn't B2 be done this way?

sort the given array. maintain K lists of prefix sum of (i%k) indices only. Then find upper bound of p in these lists, return the max. of these upper bounds. Also add to these upper bounds, those gifts which still can be bought without any offers, after each upper_bound applied.

My submission is failing on 55th TC of 2nd test case. Can someone please help me with that? I am not able to get that particular test case, since it is not being rendered on CF.

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    It is simple dp, where dp[i] is min money to pay for first i problems. Sort the goods by price.

    dp[i]==min(dp[i-1]+a[i], dp[i-k]+a[i])

    You can allways buy goods one by one, or choose at any point to buy k goods at once. Anyway, you allways buy the cheapest goods.

    → Reply
»
5 years ago, # |
  Vote: I like it +10 Vote: I do not like it

What strange problems this contest have. I felt upset from Problem B(1).

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

Problem D

Why if I do more than N + 2 requests (exactly 1000 times) "aabba" it passes 1st test? link. I guess that checker counts only unique requests, not the actual number of requests. My solution was making N + 3 requests (while I thought it was N + 2) and I was getting WA 5 the whole contest. I couldn't even think that the problem was with a checker :(

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone solve B with binary search..

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

    Not sure it would work. In this problem if you can buy x items, there is no guarantee you can also buy x-1 items.

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

      But some are manage to pass by using binary search. Can't understand how.. sol 1 — https://mirror.codeforces.com/contest/1282/submission/67533137 sol 2 — https://mirror.codeforces.com/contest/1282/submission/67532628 In the second case the user use the binary search twice.. Can u explain the logic behind both the solutin... Thanks..

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

        My submission using binary search: 67564167. Not sure if my idea is the same as those above.

        My idea is to sort the goods by their prices, then fix the number of goods that we have to buy separately (obviously, it's in range $$$[0,k-1]$$$), and finally using binary search to find the number of group of k goods that we can buy.

        If the numbers of good that we buy separately is i, it's optimal to buy the first i goods.

        Overall complexity should be $$$O((n+k)logn)$$$.

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

      If you really want to you can binary search on the number of groups of size K you buy, then binary search on the number of singletons you additionally buy.

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

      Yeah u are correct if your predicate is can we buy x items but if you consider predicate to be can we buy at least x items then BS can be applied code : 67538774

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

        Thanks for replying, can u explain what does second while loop do i.e inside bs.

        → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain that why in this solution https://mirror.codeforces.com/contest/1282/submission/67533137 they use midb and the for loop for midb, with using only mid as in normal binary search answer fail on first case on test case 7.. Pls explain why midb is necessary.

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

    For binary search, your function needs to be monotonic, and this is not the case when you just use the "mid" approach. In the seventh case, note that it costs 7 to get three things, but 3 to get four. 

    4 6 4
3 2 3 2

    This is caused by being forced to buy mid%k items individually. The "midb" approach compensates for this by "rounding up" and checking the answer for the next multiple of k. This works because the cost for all values between mid and midb is greater than or equal to the cost of mid and the cost of all values larger than midb is greater than or equal to the cost of midb (proof left as an exercise).

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How would the solution for D be affected if the strings were not binary? Let's say you had 26*(n+2) queries. Would the same technique work? If not, what would change?

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

How this test case in 1282C - Petya and Exam is getting the answer as 1. Shouldn't it be 0?

6 17 2 6
0 0 1 0 0 1
7 6 3 7 10 12
→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can solve any of the easy problems and leave the exam at t = 2, which nets you one point.

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

    No At time t = 2 he can leave the exam after solving 1 easy problem.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

WA because of integer overflow hurts again

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

In Problem C, second Testcase, the 12th test is 

2 13 3 6
0 0
2 0

Since mandantory times are 2 and 0, and a==3 I would expect the answer to be 0, no problem can be solved in time, since the first solved problem is at t==3, that is after 0 (and 2).

But grader says answer is 2, so both problems should be solvable in time.

What did I get wrong, can somebody explain? submisson

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

    It is not necessary to start solving problem before it's mandatory time.

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

      Ahhh, I understand. There is no need to solve the problems until mandatory time. Only, if one finishes after mandatory time, that problems must have been solved.

      Funny, that the whole first test and the 11 ones before the 12th work correct, even after getting the problem so wrong.

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

    Because T = 13, you can solve the two problems and leave at t = 6 (which is < T).

    Mandatory doesn't mean it has to be solved before that time, it means that if you don't leave before it becomes mandatory, then you cannot leave until you solve it (it doesn't matter when you solve it but you have to solve it before leaving), but you still have to do that before you run out of time (t=T).

    → Reply
»
5 years ago, # |
  Vote: I like it -70 Vote: I do not like it

This was one of the worst rounds I've done. I hope none of real coordinators would allow problems ABE in the contest. D was nice, but forbidding to ask queries longer than maximal string is a bit silly. Still, having one nice problem is not enough to make a round out of it. I like when new people are starting in problemsetting, but next time ask for an actual coordinator who is willing to say that your problems are bad.

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 3   Vote: I like it +30 Vote: I do not like it

    Just out of curiosity, what was bad in A and B other than the long problem statement?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it -26 Vote: I do not like it

      None of these problems are fresh in any sense.

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

        Cool, makes sense. The problem ideas may seem old especially given your level of experience.

        Still according to me both A and B were good problems for beginners.

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

          The first time that I see Nutella's comments are downvoted!

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

    I would agree on A (probably, suits Div.3 better). B seemed okay, but maybe too complicated statement for little thinking effort. E was nice although seemed too easy for the last problem. But in the end the contest seems to be well-balanced, maybe one more hard problem was missing.

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

    Nah, nice contest :D

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

    E was really nice

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

    I think he forgot to look at... It was Div2 not Div1.

    → Reply
»
5 years ago, # |
  Vote: I like it +24 Vote: I do not like it

What is the reason for having an upper bound on the size of string query you can ask?

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

    Do stop people from bruteforcing everything.

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

    I'm guessing it's mainly for hacks. It's easy to forget the condition and print a 301 length string

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

i solved E with topological sort . Is there any other way (for finding the vertices permutation)

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

    Not sure if we can call it topological sort. It's just a simple circular cycle which isn't even directed. Maybe calling it a dfs is enough.

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

      Guess i made it over complicated for me then

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

      can you explain how to use dfs to solve this problem ?

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

        There was a bit of preparation needed before doing the dfs which was the crux of the problem, dfs was simple once you get the idea that —

        • identify outer circle's edges (those which occur in only 1 triangle)
        • create a graph using those edges (guaranteed that it will be a circle). then do dfs starting from any random node.

        My code: https://mirror.codeforces.com/contest/1282/submission/67581486

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

          thanks.can you explain that idea which led to dfs as solution.I mean can you elaborate a little more.

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

            The main idea was -

            • whenever there is a cut — the place where knife went and created an edge will have to be shared by two triangles. Those edges are of no use. So find those edges and remove them. And create a graph with rest of the edges.

            How to find those shared edges?

            • Just count each edge in all the triangles like map[edge_a_b]++ . Whichever edge has count 2 are the ones where knife went.
            → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I solved it like this: the last piece to be cut must contain a vertex which only appears once. So, find such a piece (let's call it [t,a,b], where t only appears once), remove it, solve recursively for the remaining pieces, then in the linked list obtained by solving recursively, replace edge (a,b) with edges (a,t) and (t,b).

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

Can some one help me find the mistake in my submission 67570438 for Problem D.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

When you think your approach is wrong but after contest you realize it is just -1 which gives causes WA, it hurts.

1

→ Reply
»
5 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Master as christmas present!

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello everyone,

I have tried to make video solution for the first four problems of Codeforces Round 610 Div. 2, hoping to help people understand the problem and what was my approach for the same. Please do like the video and do subscribe for more such content.

Video playlist: Codeforces 610 Div2 Video Solutions Playlist

Separate links are as follows: A B1 B2 C

Happy Coding

Divyanshu Kumar

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Using google translate for the editorial makes it super hard to understand :(

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

in problem B1 how can (4 9 2 ) 2 4 3 5 results into 4. its impossible to buy 4 items with 9 coins

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

    Pay 5 coins and take the items 5 and 3. Then, pay 4 coins and take the items 4 and 2.

    → Reply