Jatana's blog

Codeforces Round #612
By Jatana, 5 years ago, translation, In English

Hello everybody!

Now the winter SIS (Summer Informatics School) is taking place, and we, as part of the parallel A*+ with its teachers, have prepared a complete Codeforces Round.

The round will happen at Jan/05/2020 17:05 (Moscow time) and will last for 2 hours. There will be 6 problems in each division.

The tasks of the round were invented and prepared by ismagilov.code, devid, Volkov_Ivan, Jatana, karasek, polinarria, cookiedoth, AlesyaIvanova, KhB, AliceG, D.Pavlenko, VFeafanov, LordVoIdebug, forestryks, Ilistratov, seiko.iwasawa, senjougaharin, Drozd_off under the guidance of teachers PavelKunyavskiy, VArtem, meshanya, budalnik.

Thanks aneesh2312 MarcosK Stepavly Infinity25 tourist antontrygubO_o isaf27 fedoseev.timofey, Kurpilyansky, vintage_Vlad_Makeev for testing!

And, of course, thanks to MikeMirzayanov for great systems Codeforces and Polygon, and 300iq for round coordination.

Good luck everybody!

UPD:

In problem E an error was made in the intended solution, an overflow of long type while calculating the answer. The first test, on which it happened, reached 4 participants (ainta aid Um_nik ecnerwala), among who two passed the pretests, and two others did not, though they should have. In automatic mode, it is not possible to test so that both answers are accepted, because the overflow changes the tests because of the way the requests are encrypted. So, we decided to test two pretest solutions on the old set of tests and the rest on the new one. As a result, three of the solutions passed the tests (congratulations!), and one received WA80 on the 17th answer inside the test, which is clearly not related to the overflow problems. Only the solution that takes into account the overflow problem can be used in upsolving.

UPD: Editorial!

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

Comments Comments (307)
| Write comment?
»
5 years ago, # |
← Rev. 2   Vote: I like it +55 Vote: I do not like it

OMG, round by cyans only!!! _overrated_, where are you looking???

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

cyan round!

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

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

    It wouldn't be complete without Mr. Rodgers wearing a cyan shirt.

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

I have changed my color to cyan in order to participate in this round.

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

Round by cyans and for cyans only.

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

why everyone is specialist?

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

How on earth is MikeMirzayanov cyan.

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

CyanForces!

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

[deleted]

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

What happened to the time being displayed in the local time zone in the blogs?

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

Do I need to be cyan in order to take part in this round ?

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

I thought my laptop was glitching at first.

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

You guys made me cyan

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

Cyan apocalypse

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

After two consecutive mathforces I hope this contest will not be a mathforces.

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

Btw

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

Mike is the real Loki.

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

Jokes on you I became cyan today. ( for a second I thought I broke the system)

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

I wonder where is UnstoppableChillMachine...

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

Is this some kind of anti-ratist movement?

let's remove colors! make them all cyan!

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

Yesterday we participate contest with maximum no of registration and today we are going to participate contest with maximum no of writer.

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

Round doesn't seem worth participating in. Maybe with 900 more of these problem setters it will equal the quality of an Um_nik round.

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

Joining the cyan trend!

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

the winter SIS (Summer Informatics School)

Hold up.

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

Specialist round!

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

.

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

Why is it cyan round?

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

The round is rated for every one with ratings between 1400 and 1600. However, all of you who wish to take part and have not rating between 1400 and 1600 , can register for the round unofficially.

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

Is it just me, or it's actually looks satisfying to see all cyan like that

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

cyanity

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

Me: (Looks at setters) This is incyanity

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

A creative use of cf new-year magic!

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

Even if we consider the worst-case scenario, where both divisions have completely different problemsets (i.e., 12 unique questions in total), it is still way less than the number of writers for this round (which is 22). Interesting.

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

    Every problem has been worked on by multiple people. You can easily have one person write both (english and russian) statements and 1-2 others do everything else all at the same time. Yes, every person listed as a writer is actually one, everyone had a part in making the round.

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

Go team Cyan!

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

Over 20 writers for 8-9 problems (combined in Div 1,2)... Can we expect each problem to be a mixture of multiple concepts and observations ? And will not be speedforces today ?

P.S. It should be fun today. :)

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

The round of 1000 cyan .. = the round of Um_nik

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

Hell yeah, cyan round.

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

in respect of all the cyans

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

Let's make cyan great again everyone!

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

the number of authors makes me feel good about this round, but I hope it's not a mathforces

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

When you're not cyan yet:

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

Does it mean that jqdai0815 would be participating today.

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

    Man, your display picture is disturbing.

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

Cyan round?

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

I can be cyan after this cyan round!

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

One more cyan! UPD: scores for problems?

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

How is task complexity calculated?

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

Seeing a strong cyan community, Hoping to become a Cyan today.

Good Luck everyone!

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

Why there are some candidate masters registered in div2 and some experts registered in div1?

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

    Because some of them registered for the contest before the Hello 2020 ratings have been recalculated.

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

      It will be rated for them?

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

        I'm pretty sure that yes.

        Once I was transferred to Div. 1 several minutes before the start of the contest (I registered when I was still Div. 2), and it was rated.

        However I don't know if that's a global thing or not

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

My rating is 1346, would this div 2 contest be rated for me? I am confused as it is not mentioned in above blog.

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

    Yes div2 is for rating lower than 1900 and div1 is for rating greater or equal to 1900!

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

Is it Rated?

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

    Yes. It's rated!

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

    Of course NO one really want to do this round unrated .

    Did someone can really think that Regular Codeforces round can be unrated?

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

This is the point where you need to cut down the list of authors on the Contests page to only the most relevant ones because it's tl;dr.

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

    What do you mean by "most relevant ones"? Everyone had a part in making the contest.

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

      What do you mean by "most relevant ones"?

      Are you asking what the phrase "most relevant ones" means or who should be considered the most relevant ones? In the first case, try a dictionary, in the second case, I can tell you what I'd pick if you describe the preparation process in detail and how everyone contributed.

      If, for example, I made a dumb heuristic solution for some problem and a countertest for that got added, I wouldn't consider it relevant enough to call myself one of the authors of the contest.

      Everyone had a part in making the contest.

      And everyone can be mentioned for example on this page, with a shorter list posted where it would be an inconvenience to have a very long list — the Contests page, in this case. It's not like everyone who had a part in making a contest should make their own blog post about their part in it, either, right? The logic is the same.

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

        So every person got assigned to a problem, with 2-3 people per problem, and each team then distributed the tasks between its members. There's really a lot to do if you're making a problem in polygon: write a statement and a tutorial in 2 languages, write several solutions (correct and incorrect ones alike), generate tests, make a checker and a validator, and each one of these tasks can pretty much be done independent of others. Of course, the harder the problem, the harder each of these tasks are, but not significantly: everyone involved knows the statements and the solutions well, so preparing any problem is pretty much a routine job. So there really are no "most relevant" problemsetters, they are all roughly on the same level.

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

          Huh, that's... unusual. Most of the time, there's someone who makes sure statements are ok, someone (possibly the same person) who makes sure translations are ok, testers who write the correct+incorrect solutions and comment on what's missing, and for each problem one, very rarely two people who do the main, initial brunt of the work — basic statement, correct solution, basic tests.

          each one of these tasks can pretty much be done independent of others

          I don't have that experience. When I'm preparing a problem, in order to make strong tests, I want to understand intricacies of the problem and the solution well enough that I might as well write it down, so making the statement, tutorial, one solution and tests is all interconnected. The same goes for the checker if a non-trivial one is required. If I do just part of it, I can miss something important, and if I divide it up with someone else, it happens too often that one of us ends up doing too much or there's just a general lack of communication, and it costs more than it offers. Then, some tasks are independent — validator, simple checker, simple bruteforce etc, and some, like good translations, then require specialised roles.

          In your case, it's more like when there's a prioritisation meeting at work where some bigger structured task was already explained and divided into also explained smaller parts before, it gets moved from the todo list and team members are assigned to parts of that task. Since you mentioned that each assigned person knows their problem+solution well enough.

          Anyway, regarding the long list: you mention 18 people + 4 teachers/coaches + some testers. Since you mention 2-3 people per problem, I assume that's the 18. If each person is mentioned just for 1 problem and only for the division where that problem appears (C is one problem), that would cut it down. Another, probably better alternative, would be to just keep the list of authors on the Contests page empty. Whoever wants to read it can read it here.

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

What is scoring distribution!!

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

Let's all convert to Specialist

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

Come in as a fake cyan, come out as a real cyan.

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

i didnt registered because i didnt see starting time how can i now register there is 50 minutes remaininig?

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

me at the contest cyan round was very difficult for me

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

good contest. specialist here i come!

stuck TLE on div2B for about 1h until i found i used map changed to unordered_map and pp lol

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

Nice Impossibleforces !!

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

Radewoosh RIP

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

Is this correct for D2E1/D1C1 —

We ask (1,1) + (1,n) + (2,n) By (1,1) we get first character, by (1,n) and (2,n) we can get only prefix substrings. By keeping count of frequencies, we can place characters by reducing the first character one by one.

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

    That worked for me, but asked only (1, n) and (2, n) — you get the first character for free as it is the only string of length 1 in their difference.

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

On problem C, I spent 20 minutes debugging my code, only to find out that all I was missing was the edge case where N = 1. :(

Overall, great contest in the D2 at least.

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

https://codeforces.me/contest/1287/submission/68274741

Please explain why this isn't working. Time complexity is O(n*n*(k+log(n))) Can it be done in better???

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

    String concatenation is not always O(1). Better to use vector of characters. 68258848

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

      Thanks ..... This has made me sad now, didn't knew such a thing :(

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

    My solution (pending systests) is pretty much the same idea. I only used a set instead of a map. Also I locally generated a n=1500, k=30 input locally to make sure my code does not TLE before sending it

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

    You should also note that the log(n) factor is unnecessary, and due to the strict time limit can by itself cause a TLE, assuming a badly implemented code.

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

    this line t=t+v[i][m];

    It's inefficient, because basically you create third string and get data from the first string and second string, the total t construction after k iteration will be O(k^2) http://www.cplusplus.com/reference/string/string/operator+/

    It will be faster, if you change it to t += v[i][m] It will only add the second string to the first string, The total t construction after k iteration will be O(k) http://www.cplusplus.com/reference/string/string/operator+=/

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

How to solve C?

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

never mind

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

Why constraints for DIV2 C are so low? It can be solved in O(nlogn) using greedy.

Update: my solution passed system tests

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

    Whats the greedy solution? I could only think of a dp solution with states involving (index, oddRemaining, evenRemaining, lastOddOrEven)

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

      Consider the parities of fixed points in order as they appear in the string. We can see that if two consecutive parities differ, then the the complexity of the substring between them is 1. So, it remains to consider the segments with same parity, sort them according to length, and give the required numbers with the same parity till we run out.

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

        The greedy which I implemented has some annoying edge cases.

        Basically, you have to separately consider substrings bordered by the edge, and substrings bordered by two numbers. Plus, you have to deal with the all-zero case and the N=1 case.

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

      Only 4 types of gaps are possible: even-even, odd-odd, even-odd, odd-even

      For even-odd and odd-even, the minimum complexity generated is always equal to 1 (doesn't matter if you use all even or all odd or combination of both)

      So just take all even-even and odd-odd types of gaps in increasing order of gap value and greedily fill them. E.g. for even-even if enough even numbers are available to fill the whole gap then the minimum complexity generated is 0 otherwise 2.

      Gaps in start and end of the array are needed to be handled separately.

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

        I thought of similar solution but couldn't implement it cause B took all the time.

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

        I started writing this as well, but I wasn't sure if it was correct so I just deleted everything and wrote DP, since I knew for sure that would pass.

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

          How to solve using DP ?

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

            Define $$$dp[i][j][k]$$$ as the minimum obtainable complexity upto position $$$i$$$ such that exactly $$$j$$$ even numbers have been used so far and the last one used has remainder modulo $$$2$$$ equal to $$$k$$$.

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

        I tried that too, I immediately knew it was DP but for some reason, I went too far with the DP tbh it felt like I was drunk XD

        I have submitted this idea but since I was in a hurry (Badly written) there might be a bug in the code, If anyone gets accepted with this idea please link it.

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

        I followed the exact same greedy approach but cannot get AC on 12th test case. I am unable to find the issue with my code. Can you help? 68277187

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

          You should try this

          7

          0 3 0 5 1 4 2

          The correct answer is 2, not 3.

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

    Perhaps because the greedy (if it is indeed correct) is error-prone while not very interesting. I started with greedy and after 20mins and 2 WAs just wrote the DP which passed immediately. I actually respect their decision not to force the greedy approach.

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

    No offense, but your solution is pretty ugly. DP produces a shorter and cleaner code.

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

      My point was about time complexity not implementation complexity

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

        Finding the best possible complexity is nice, but to me it sounds like an upsolving excercise. During a contest, the goal is to get points ASAP, so I don't see why waste time implementing it.

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

          No offense,but when there is a solution with better time complexity,it is always better to learn it.

          Same question,could have been asked with larger constraints,and dp wouldn't work.

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

            I don't think you read my comment carefully. It is good to learn the fastest solution, but it's better to do so without time pressure during contest. That's what upsolving means.

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

              I get it,it is always better to implement a dp solution than a greedy,if it works under constraints,but I believe the intent to post the greedy solution to help others.

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

                I never said his comment had a bad intent. He asked why constraints were so low, and I answered: DP was simpler than greedy.

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

      Can you please explain your solution to $$$D$$$ ?

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

That feel when you read that test 20 is incorrect and then get "Pretests passed".

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

How to solve B?

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

    lets choose two strings i , j any two are valid ( try to prove it ) then you can know the third string in this way loop in those two strings if current two chars are equal then the third string must have the same char else the third string must have a char nethier equal those chars in that position

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

Terrible
I have a problem with live contests usually I can solve div2A in < 15 min and div2B in < 30 min (in training)
But I need to see the test cases to see why I get WA... if someone know how to get over such a problem..
Yes and i will be newbie after this round

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

Do you really think putting these problems together in one round was reasonable choice? Already C2 was a tough one and A+B+C1+D (solving only one out of 4 hardest problems) gives me 11th place before systests.

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

    I prefer contests like these to contests where all the top participants solve everything. It gives freedom to choose which problem to solve. Pretests could be stronger though. :(

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

Why did i go in thinking a cyan round should be like taking candy from a baby :sobs

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

Does this mean I have successfully hacked the judge?

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

    No

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

    I thought that in problem called "implement a lot of stuff" implementing BigInt was just another part.

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

      Wow! Now I see why Codeforces doesn't support 128bit integers.

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

      Ok, I think results of this round prove that Um_nik is really worth more than 21 cyans.

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

    What's the final resolution to this? It looks like there are no tests that overflow 64-bits now? I think that decoding via $$$ans \% 2^{64} \% 26$$$ and $$$ans \% 26$$$ both pass?

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

Any gueses what is in test 3 for Div2C?

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

    n == 1

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

      My code gives answer 0. But I still get WA 3

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

        n == 1 && p[1] == 0

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

          Yeah! In this case my code answers 1. Thanks

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

    some ideas:

    6
    0 0 1 0 0 0
    (expects 1)

    5
    0 2 0 4 0
    (expects 4, pretest 4 is like that)

    5
    0 1 0 3 0
    (expects 2)

    1
    0
    (expects 0)

    6
    0 0 1 3 0 0
    (expects 2)

    looking for pretest 5 if somebody got it

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

      Pretests are now visible.

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

        Indeed, and I realized my mistake. I had something like 

        if(condition1)
    if(condition2) dosmth();
else if(condition3) dosmth();

        and my intention was to do

        if(condition1){if(condition2) dosmth();}
else if(condition3) dosmth();

        because the else if in the first version acted as an else for the if(condition2), and not for the if(condition3) like I wanted... What a mistake xd

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

    n=1

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

Anyone solved C2 by asking $$$(1, n)$$$, $$$(1, \frac{n + 1}{2})$$$ and $$$(\frac{n + 1}{2}, n)$$$?

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

    how do you recover answer?

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

      I didn't have time to implement it, which is why I'm asking others who actually solved it here. My rough idea is we should know $$$a_\frac{n+1}{2}$$$ from the beginning, then just build up the answer symmetrically from those 3 parts.

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

    That's my solution but I kept getting WA on 12. I think I have a bug because the implementation is tough.

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

    I think query same half would be work, thus might use one half to recover another half. waiting for editorial..

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

    Sort of, but I have 6 cases: $$$n = 1, n = 2$$$, and $$$n \mod 4$$$. Maybe some are unnecessary.

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

    I'm not sure, but I assume that it recovers the string up to reversal, isn't it?

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

5 4 SETT TEST EEET ESTE STES Participant's output 0 Checker comment wrong answer 1st numbers differ — expected: '2', found: '0'

But my dev c++ runs out 2 Can anybody explain that?=_=

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

    You are likely dealing with some kind of undefined behavior (such as indexing an array with an invalid index or using ununitialized variables)

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

    change char kk[k]; to char kk[31] = "";

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

Interactive problems...

Find out a solution at last but keeping 'Idleness limit exceeded on pretest 1'

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

How to solve B ?

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

    Choose 2 strings and try to make the third one. You can see that if you have 2 strings, there can be only 1 third substring. All you have to do is to create a map to store the frequence of every string and, after you build the third string, add its frequency to the answer. Be careful, you count every triplet 3 times, so, at the end you should divide then asnwer by 3. :)

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

I got WA on D and E1 on first submission because i was missing the case N = 1... Has it happened to someone else? :)

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

Thanks for including $$$n = 1$$$ in pretests for C1 -_-

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

Really sad. I found where I made a mistake in my prob D code after 2 minutes the contest had over.

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

How to solve Div2-D?

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

    Start placing integers in nodes in decreasing order — When subtree size = c-value, this is max in subtree, select the one with lowest depth and decrease subtree size of all its ancestor by 1.

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

      Can you explain what you mean by "start placing integers in nodes in decreasing order"? Should you place bigger integers before smaller ones? Or should you place integers from nodes n to 1? And what do you mean by "subtree size = c-value"? What is max in subtree of what? And what do you mean by decreasing the subtree size of all its ancestors?

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

        Should you place bigger integers before smaller ones? — Yes

        And what do you mean by "subtree size = c-value — c_values given in problem

        What is max in subtree of what? — Maximum a_i among nodes in its subtree

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

can someone please explain why this solution 68252477 for PROBLEM B of DIV 2 is getting TLE

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

    Your solution is (n * n * k * k * logn) which is quite big

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

    You are using std::set, which has an awful constant on nearly all the operations. Using three ifs instead of set gave AC.

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

      Thanks for replying. I don't think this is the problem but still i will give it a try once submissions are allowed and will update you

      update: you are correct. Just by using three loops it passed. Thanks man

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

    You did s += x to add a single character to a string, which will lead to $$$O(k^2)$$$ for forming the string. Instead do s.push_back(x), which will be in $$$O(k)$$$.

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

      s+=x has complexity linear in term of length of x. s=s+x has linear complexity in length of resulting string.

      so s+=x will lead to O(k) only

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

      can you explain why s+= x is slower than s.pushback(x) in general ?

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

spend half an hour on alternative, correct solution for Div2-C

submit old buggy version with 2 minutes left

Sigh...

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

I liked problem C, but it can be hard to spot the solution. It is kind of guessing which approach to take.

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

C is probably my favourite interactive problem now, finally something that is not binary search :Dd

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

How to solve Div1D ?

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

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

I hate subtasks so much!!!

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

What's wrong with this solution for div2B? I am getting TLE on pretest 10. https://codeforces.me/contest/1287/submission/68262344

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

When you are just on time. epic.png

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

So what's the best ratio anyone's gotten in Div1 C2? My solution takes about $$$0.75N^2$$$ and that's likely the intended one. It doesn't feel like this would be the optimal solution.

Edit:

According to aid a query restores the string uniquely up to reversal, which makes the problem much simpler. I've no clue how one proves that, though.

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

    I think you can solve it with one query for the whole string and then one more question for a single string. The algorithm is rather messy so I didn't get time to implement :(

    Basic idea: Looking at strings of length $$$N-1$$$, you can get the first and the last symbol. Then, with some considerations, from the strings of length $$$N-2$$$ you can extract 2nd and $$$(N-2)$$$-nd symbol, and so on.

    There is one more consideration: the first time you encounter different characters with the above algorithm, you can ask for one of them directly. After that, you can use this difference to figure out where each character is for each different pair in the next iterations.

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

    Look at all strings of length $$$n-1$$$. There are 2 of them. From them you can restore first and last elements, but you don't know which one is first and which one is last. If they are different, ask about the first one. Then if we restored the first and last $$$k$$$ elements, let's look at the strings of length $$$n - k - 1$$$, we know all but 2 of them. Find those 2 strings, from them we can find $$$k+1$$$-st elements. There are some cases like when we already found 2 different characters and not.

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

      From them you can restore first and last elements, but you don't know which one is first and which one is last.

      How do you handle something like aabbaa?

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

        We have strings "aabba" and "abbaa", from them you know that first and last elements are 'a'.

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

          But those strings can also come from bbaaab. Can you elaborate your approach?

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

            But you know the number of 'a' and 'b' in the whole string. Each of the strings of length $$$n-1$$$ either has 1 less 'a' or 1 less 'b', from that you know 2 border characters.

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

              I had the same approach, but during upsolving I found out that during restoring there can be an issue, where prefix and suffix are the same (w.r.t character frequencies), we have two different letters, and we don't know which letter goes to prefix and which goes to suffix. That's why I got WA23 :/ How do you deal with such situation?

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

        You know how many A's and B's there are because of the 1-length strings, so you can check which character is absent in both substrings by counting

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

    My solution uses around $$$\frac{2}{3} N^2$$$:

    C1: $$$\textrm{query}(1, N) - \textrm{query}(2, N)$$$ gives you the set of prefixes of the hidden string, which is enough to construct it. It uses around $$$N^2$$$ strings.

    C2: With the same idea from C1 we can learn the first $$$\frac{2}{3}$$$ of the hidden string using $$$\frac{4}{9}N^2$$$ strings. Knowing the middle third of the hidden string and querying its last $$$\frac{2}{3}$$$ (an additional $$$\frac{2}{9}N^2$$$ strings) is enough to construct the final third.

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

      Can you explain how do we get the last third of the string?

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

        We want to construct a string of length $$$2T$$$. We know its first $$$T$$$ characters and we know the list of responses from querying the entire string.

        From the unique response with length $$$2T$$$ we know the unordered contents of the full string.

        Suppose that we have already figured out the last $$$k$$$ characters of the string. Initially $$$k = 0$$$ and when $$$k = T$$$ we are done. We consider all substrings of length $$$2T - 1 - k$$$. We already know enough characters at the beginning and end of the string to construct all of them which don't start at the very beginning of the string (subtract excluded letters at the beginning and end from the contents of the full string). By elimination we find the one which does start at the beginning: it gives us the $$$(k+1)^\textrm{th}$$$ character from the end.

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

CAN YOU MAKE PRETESTS STRONGER?

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

Very very very weak pretests :(

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

Attempt 1 : TLE
Attempt 2 : TLE
Attempt 3 : TLE
Attempt 4 : TLE
Attempt 5 : Pretests passed at 1:59:32
Reason for TLE : use of set to find the character not present at a given index rather than simple if else.

 set<char>se;
 se.insert('S');
 se.insert('E');
 se.insert('T');
 se.erase(s[i]);
 se.erase(b[i]);
 char a = *(se.begin());
→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I used policy based data structure so my solution got accepted at last

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

    please can someone tell me why using set give TLE

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

      set.insert() and set.erase() are not O(1) operation but O(logn) operation, although n here is equal to 3, i didnt expected that to be huge issue

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

https://codeforces.me/contest/1287/submission/68275963 this solution give output 0 for n=7,p={0,0,0,7,0,0,0}, but actual output is 1

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

That's not the way on how to write problem B for Div 2.

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

Duh, getting $$$O(3^n)$$$ is not that hard in F, definitely more doable than anything like $$$O(2^n n^{10})$$$ and indeed as I expected both accepted solutions are $$$O(3^n)$$$ -.-

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

never give up :))))

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

unordered or ordered map ? In some problems unordered passes while ordered fails, while in others exact opposite happens.

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

    Always use map,unordered map's time complexity depends on nature of input,if a solution passes for unordered map but fails for map,then it's either bad implementation or bad question

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

    Unordered map is faster, provided that you have a good hash function. The reason why unordered_map is sometimes slower than regular map is that there exist special techniques of generating worst-case tests for unordered map, where standard hash functions give a lot of collisions.

    See this blog for more details.

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

The contest was raely nice but I had a better idea on it
It was realy nice to add a simple problem at the begining of the Div. 2 then you change the n of the problem Div 2. D to 1e5(solveable with easy dfs).
so the contest would be better to solve.
And also D was easier than C and swaping them was a good idea.
Thanks CyanForces!
It was good at all.

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

    can you tell your approach for d, i find dp solution of C much easier than d.

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

      as a dfs return a vector and make this like:
      insert all of the vector of kids of v together
      the insert v as c[v]_th element (if impossable "NO")
      then get the vector of root
      then for all i, ans[a[i]] = i
      then output the ans[i] for each i
      And I think it is the best problem fo teaching dfs to someone :)

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

        Can you explain why that works?

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

          Because every vertex is the c[ i ]_th it it's kid's set.
          Because we inserted it as c[ i ]_th element in the vector :)
          Do you agree? so now we came to find out what numbers to assign vertex to get the order v1, v2, ..., vn.
          so we assign 1 to v1 and 2 to v2 and ... .
          now we have some numbers that are the c[ i ]_th in their SubTree. :)

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

    How would you do div. 2 D with n = 1e5?

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

      Do like the comment on top but with a little diffrent.
      First with an easy dfs check if every vertex's (SubTreeSize[v] <= c[v]); If not output("NO");

      Here we go:
      take an ordered set Insert all 1 to n in the set
      For each vertex in the dfs erase the c[ v ]_th element and it would be ans[ v ] and it's ans sequence is the same as This (try to prove it by Mathematical Induction and the delete the root and it is ok for the tree's made by deleting it and so on ...
      And output ans[i] for every i.

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

        Good one! Actually, just implicit key cartesian tree gives nlogn if vector is replaced with it. Code for n^2, which can be modified with tree instead of inserting into vector

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

          Yes bro got it right!
          it was the idea behind it.

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

What is the time complexity of writer's solution of problem F? I think coming up with O(3^N) solution is not so hard, yet I was able to fit it to TL by pruning: 68281697

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

    $$$O((1 + \sqrt{2})^n + \log{n} \cdot n^2 \cdot 2^n)$$$

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

Could someone please, tell me, where I went wrong. 68273158

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

How to solve DIV1B/2D numbers on tree.

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

    I solved in this way: Keep the number of nodes in the subtree for each node(let it S[]). If there exists i such that S[i] <= C[i], then the construction is impossible. Otherwise, the construction is always possible. Keep 1, 2, 3, ... n originally in a set data structure(e.g., treap?); let the the set B. From the root, run DFS and make each A[i] value to C[i]+1th smallest value of B, and erase the value from B. Then, the number of smaller nodes in the siblings are exactly same to C[i].

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

      Then, the number of smaller nodes in the siblings are exactly same to C[i].

      Do you mean number of smaller nodes in the subtree?

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

        Yes. As we wish to be. :) 68267213 This is my submission. I feel ashamed to be in public(cause the code is dirty..).. But maybe it would be helpful under the function predfs. I used treap data structure to keep the set and find kth element from it. But there would be many alternative solutions like indexed tree + binary search, or etc.

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

        Cleaner submission with Fenwick Tree and binary search(to find kth element): 68289460. (O(nlog^2n))

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

Sorry, but it was a coincidence.

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

My solution for C was 100 lines in python (making lists of gaps with different ends then sort etc) there should be some shorter approach to avoid this spaghetti mess.

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

When tutorial will be published???

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

in problem B, TLE code in contest time 68259187. Ac code after contest 68286650.

just modified a simple function named f(). I think it should not matter. please have a look.

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

    Well, you were using map in the function that gave you overhead

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

It was a good contest.

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

Can someone tell me why this code gives WA on div2A? 

        #include <bits/stdc++.h>
        using namespace std;
         
        int main(){
         
        	ios::sync_with_stdio(0);
        	cin.tie(0);
        	cout.tie(0);
         
        	int t, n;
        	string s;
        	cin >> t;
        	while(t--){
        		cin >> n >> s;
        		int mx = 0, counter = 0;
        		for(int i = 0; i < n - 1; ++i){
        			if(s[i] == 'A' && s[i + 1] == 'P'){
        				i++;
        				while(i < n && s[i] == 'P'){
        					counter++;
        					i++;
        				}
        				mx = max(mx, counter);
        				counter = 0;
        			}
        		}
        		cout << mx << '\n';
        }
        return 0;
    }
→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    APAPP, add i-- after while loop and it should be correct

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

How to solve Div.2 C/Div.1 A?

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

I m newbie can someone tell me where is the editorial?

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

https://codeforces.me/contest/1287/submission/68290995 wrong answer on case 12 which doesn't have a value at index 0.

https://codeforces.me/contest/1287/submission/68290894 wrong case on case 8 which also doesn't have a value at index 0.

https://codeforces.me/contest/1287/submission/68290844 wrong on case 12 which also doesn't have a value at index 0.

https://codeforces.me/contest/1287/submission/68290780 wrong on case 19 which also doesn't have a value at index 0.

please help me with this error .

My approach

i am not able to manage what should be done first .

My approach

in some cases assigning to first works in others after assigning to all gaps first and last are checked. Only 4 types of gaps are possible: even-even, odd-odd, even-odd, odd-even For even-odd and odd-even, the minimum complexity generated is always equal to 1 (doesn't matter if you use all even or all odd or combination of both) So just take all even-even and odd-odd types of gaps in increasing order of gap value and greedily fill them. E.g. for even-even if enough even numbers are available to fill the whole gap then the minimum complexity generated is 0 otherwise 2. Gaps in start and end of the array are needed to be handled separately.

7

0 3 0 5 1 4 2

The correct answer is 2, not 3 , my code is giving 3.

Please help me fix it.

should i sort the gaps in increasing order of length before filling?

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

Editorial???

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

div1 F

O(3^n) can spend only 300ms

my code

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

can someone tell me why i am getting tle on problem(B. Hyperset) here is my solution https://codeforces.me/contest/1287/submission/68274322

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

Grammar mistake in the description of div. 1 F.

"The array is considered destroyed is all its elements are zeroes."

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

Waiting for editorial...a bit par contests for green coders...

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

How to solve div1D?

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

    Let $$$dp[i][j][0/1]$$$ = probability of proton $$$1 \dots i$$$ 's first collision time is $$$j$$$ , $$$i$$$-th proton flies to right/left.

    There is at most $$$2n$$$ different values of $$$j$$$.

    Use segment tree to optimize，time complexity is $$$O(nlogn)$$$ .

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

respected sir, i have no clue how my code matches with the other 2 persons you mentioned in the e-mail. this is absolutely a coincidence. i neither share my code with anyone nor do i copy. i used flag method to solve the question which is quite common, and hence may be it matches with these 2 other persons. thank you anirudh agarwal

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

(https://codeforces.me/contest/1287/submission/68307501)

Please help me i have done everything still this is not working on test 12 but working fine till 18 tests other than 12th one.

Thanks in Advance.

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

In D1C, any solution to query two times, [1,n] and another point, is impossible.

Consider the following 4 strings: abaabbab abbabaab baababba babbaaba

If someone only queries [1,8], he will got exactly the same results.

I'm not sure if it's possible for [1,n] and queries of O(1) additional length.

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

how to solve div 2 C ?

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

Where I can find editorial?

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

Where is the Tutorial???

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

Why is this 68314242 passing and not 68261685 for Div2B?

The only difference is the way in which i find the third string to be searched! Both are constant time!

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

Can someone explain the DP approach for Div2 C, it is not there in the editorial released.

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

there is O(n) solution in question Div2-C by greedy

1-count number of different parity between number which aren't zero

2-sort contiguous segments of zero by counting sort by their length in O(n), we can use from vector structure like vector p[100] which index is our length of segments and we store start and end of segments, we can iterate vector's elements in O(n)

3-chose smallest contiguous segments of zero which don't start from beginning and don't ends at the last element, these segments are between two numbers like x and y (for example x 0 0 0 ... 0 y)

4-if x % 2 != y % 2 then we have one different parity in this segment always so don't do anything

5-if x % 2 == y % 2 then if you have enough numbers with parity of x % 2 then by adding these number in this segment we have no different parity but if you don't have enough numbers then we have two different parity in this segment

6-after visiting of all segments which aren't beginning of numbers and aren't end of numbers, if there is contiguous segment in beginning of numbers or in the end of numbers then our segment is like ... x 0 0 0 0 ... 0 0 or 0 0 0 0 0 ... x ... then if you have enough numbers with parity of x then we don't have any different parity and if you don't have enough numbers with parity of x then we have different parity with 1.

→ Reply