_kun_'s blog

By _kun_, history, 4 weeks ago, translation, In English,

Hi!

Tomorrow will take place All-Russian olympiad for students of 5-8 grades, in the name of Keldysh. Good luck to all the participants! Olympiad is conducted under the guidance of the Moscow Olympiad Scientific Committee, in particular GlebsHP, ch_egor, Endagorion, gritukan, Zlobober, _meshanya_, _kun_ and, of course, Helen Andreeva.

We are happy to announce the codeforces round based on the problems of this olympiad! It will be a Div. 2 round, which will take place at Jun/16/2019 12:35 (Moscow time). You might have already participated in rounds based on the school olympiads, prepared by Moscow Olympiad Scientific Committee (rounds 327, 342, 345, 376, 401, 433, 441, 466, 469, 507, 516, 541, 545)

The problems of this olympiad were prepared by voidmax, alexey_kuldoshin, ch_egor, Nebuchadnezzar, achulkov2, manoprenko, V--gLaSsH0ldEr593--V, Endagorion.

Thanks KAN for his help in organizing the Codeforces version of this contest and MikeMirzayanov for the Codeforces and Polygon.

Also I would like to thank the Tinkoff company and personally Tatyana Kolinkova for organizing the onsite competition.

Good luck!

Scoring: 500-1000-1500-1750-(2000+750)

upd. Congratulations to winners!

Div. 2:

  1. thecodinglizard
  2. baIuteshih
  3. Cong1500DanPaiXia0
  4. Cottonyeti
  5. HatsuneMikuo

unofficial Div. 1:

  1. Radewoosh
  2. isaf27
  3. chemthan
  4. uwi
  5. kmjp

The editorial will be published soon.

upd. the editorial was published.

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

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

An unusual start time!!! Hope it give me an unusual experience .

»
4 weeks ago, # |
  Vote: I like it -47 Vote: I do not like it

Ind vs Pak CWC 2019 at 3 pm IST . Hard choice for Indian Cricket Fans to participate in this round.

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

    for dislikers: soccer world cup final attracted 1.6 billion viewers while today's India vs Pak crikcet match expected to attract 1.5 billion viewers..so dislikers do respect other's choices as well.. although i will be going for the contest :P

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

      Brother from another mother ... Haters gonna hate ....

»
4 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

Who is Keldysh?

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

The time is very very very friendly to Chinese

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

    So What? It is equal to say, "Although the time is not friendly for many other people, but the time is friendly for Chinese." Doesn't it?

»
4 weeks ago, # |
  Vote: I like it -52 Vote: I do not like it

Is it rated for everyone?

»
4 weeks ago, # |
  Vote: I like it -44 Vote: I do not like it

Clashes with India Vs Pakistan :-/

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

    No problem, rain will interupt the match

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

      Rain may affect the later part of the game. The match will start at the usual time without any interruption.

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

        then interesting part to watch would be what crowd will do as a result!!!

»
4 weeks ago, # |
  Vote: I like it -34 Vote: I do not like it

The number of reds in this post is "Huuuuuuuuge".

Like if you read it like Trump xD.

»
4 weeks ago, # |
  Vote: I like it +153 Vote: I do not like it

Glad to see gritukan and V--gLaSsH0ldEr593--V working together

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

Another round I will miss because of university exams :(

These stupid exams came when I am that close of becoming master, My rating in 2080 :(

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

please How many problems were prepared

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

May I know how many problems are there and if the solution will be pubished?

Sorry for my poor English :) Thanks

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

Minor clarification, I'm new around here. Does All-Russian mean the questions will be in Russian only?

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

    Statements are translated into English for the round.

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

what is the score distribution??

»
4 weeks ago, # |
  Vote: I like it -24 Vote: I do not like it

Is it a rated contest?

»
4 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

I just hope it won't be a mathforces

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

Can you let me know how many problems are there and what the score distribution is?

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

hoping for specialist. prey for me.

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

*me -> Wait a minute... *me -> Who are you? *to codeforces 567

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

Codeforces round vs India-Pakistan WorldCup match.Let's see what Indians prefer.

»
4 weeks ago, # |
  Vote: I like it +52 Vote: I do not like it

How does hacking work when there are two (easy and hard) versions of the same problem? They have to be connected somehow because somebody would be able to solve easy with brute force, lock it and check codes to find some which work even for hard version (and learn how to solve it).

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

    You can hack easy version only if you solved hard.

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

How to solve C ?

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

    I found every 1 column flag and found out how wide they could become.
    for every such flag, we get width*(width+1)/2 different possible flags.
    Yes, |: 10^9 operations but it passed

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

      You can sort the list of 1 column flags in such a way that corresponding flags end up next to each other (sorting by row and column). Then it is easy to check how far they extend horizontally. This was quick enough that even my python solution got accepted (without 10^9 operations).

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

      Hey, can you please help me with my code. I got a TLE by using brute force (10^9 operations).

      My code: https://ideone.com/iDkAwr

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

        10^9 is already a lot. Using a map on top of that isn't helping.
        Instead of using the map, I simply edited the map and zeroed out the positions that were already calculated and it barely passed.

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

Hard, but interesting. Thanks!)

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

So hard.55555~~~

»
4 weeks ago, # |
  Vote: I like it -40 Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it +24 Vote: I do not like it

So hard, feel like I am a retard

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

How to solve D?

»
4 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

hard problem for B

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

Where does my solution for problem C go wrong: code

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

    Check this case

    6 3
    aaa
    aab
    bbb
    bcd
    xxx
    xxx
    

    The answer is 4.

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

let me summarize. B = C, C = D. right?

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

    And D = B.

    I really think it feels right like that

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

      was that really? Why I didn't try that!

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

        Yeah I just read it and I think it was! It was a huge mistake not to start with it after A.

        Might take some coding but no edge cases like in B & C.

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

          I found too much edge cases in C that I suddenly forgot what my idea was. And now, I got the idea unfortunately.

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

        Euclid's first axiom : if A=B and B=C, A=C.

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

Light-speed system test, I love it! WOW!

Upd. It only used about 20 minutes! REALLY COOL!

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

    because of the total number of submissions not huge, comparing for other contest

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

what is the fifth testcase in problem B?? any guesses?

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

weak test cases for B.... (T_T)

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

I wrote an O(nlogm+mlogm+qlogm) solution to problem D by merging some segment trees link. I thought that would pass under a TL of 2.5s for n,m,q<=5e5. However, it got a TLE. I tried all methods I know to make it run faster but it always gets TLE on pretest 10 or 11. I'm just wondering why a nlogn solution gets TLE. Is the constant of my code too big or a solution with a better complexity(O(n) maybe?) exists?

Sorry for my poor English.

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

    I saw some AC submitions with search in the BIT, maybe it helps you ^^

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

    I used a Fenwick tree to get the n-th city, and it has passsed. https://codeforces.com/contest/1181/submission/55639812

    There is no need to merge many Fenwick trees. Just maintain a simple sum-based seg tree.

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

      Thanks, I've discussed that with my friends and they told me about the solution with BIT. I think maybe the constant of segment trees is too big.

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

        I solved it with segment tree, check my code.

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

          I used ordered set from pb_ds to solve k-th ordered statistics problem, check out my submission: https://codeforces.com/contest/1181/submission/55642500

          Btw it's quite useful data structure, it can replace segment trees sometimes!

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

            Can you explain your solution? I was also trying it with policy data structures

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

              Well, let's do the following: let's maintain ordered set $$$d$$$ that represents all cities with the smallest number of hosting days. If the current year is $$$timer$$$, then in the next $$$d.size()$$$ years these $$$d.size()$$$ cities wiil be selected to host the olympiad according to their indices(in ascending order). And this process continues until there is other city to add to $$$d$$$. Thus, we can answer queries $$$q_i\in[timer, timer + (cur - prev) * d.size())$$$, where $$$prev$$$ is number of hosting years of all cities in $$$d$$$ and $$$cur$$$ is first city with number of hosting years larger than $$$prev$$$. For query $$$q_i$$$ the answer is simply a city with order of $$$((q_i - timer)\mod{}d.size())$$$ in ordered set $$$d$$$. Then we can add new cities(cities that hosted $$$cur$$$ times) and continue this operation.

              Hope this was helpful, I struggled with English and LaTeX very much :)

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

    I solved it in $$$O(q log(q) + m log(m) + q log(m))$$$ using Treap but finished the implementation when the contest was already finished :( 55644594

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

How to solve E?

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

    Let's solve the problem recursively. If $$$n=1$$$, the answer is "YES". Otherwise, we have to find a horizontal or vertical line which separates rectangles into smaller ones without intersecting any of them. If no such line exists, the answer is "NO". If it exists, we can greedily assume that it was the line of the last merge and solve problems recursively.

    So, $$$O(n^2)$$$ (maybe $$$O(n^2 \cdot \log(n))$$$) is easy. How to speed it up? We'll try something like "smaller to greater", but in reverse. As we'll split the problem into two smaller ones, we can do it in complexity $$$O(size\_of\_the\_smaller\_part\_after\_the\_split)$$$ (possibly multiplied by $$$O(\log(n))$$$) and the overall complexity will be good. The problem is that we don't know if the line that we are looking for will be horizontal or vertical and we don't know if it'd be closer to the beginning or to the end of the list of sorted rectangles.

    The solution is to try every option at the same time. Maintain $$$4$$$ sets, one for each possibility, go through each of them and if you'd find a good line, stop here, split each set into two smaller ones and the complexity will amortize.

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

      You can change set into list or 2 stacks and this solution will work in O(n log n).

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

How to solve D? can you help me.

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

    I pre solved it in an offline manner.

    1. Sort all the queries in terms of time stamp.
    2. Interate through all the queries and merge the candidate cities in the process. I used two pointer like approach and fenwick tree to maintain this.

    You could read my submission first if it passes. I am currently away from my laptop.

»
4 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

So I will wait for Div.3 to raise my rating xD

»
4 weeks ago, # |
  Vote: I like it +20 Vote: I do not like it

B was incredibly time-consuming in my opinion. I hate strings, it took me 150 lines of code to solve B and I couldn't even submit it in time. After half an hour of coding B I realized that there's like a 100k digits and I can't sum the string as numbers but as strings, so this was my first time ever doing this and i hate it, I hate strings, they're just tedious things that are very easy to mess up because there's so many things that you need to do with strings to manipulate them that its very easy to mess up the code and then debugging takes a lot of time. And I unknowingly solved A within 10 minutes but because I forgot about long long, I thought that there was a math error in my code, so I just skipped A.

At least I learned something..

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

    You should study some accepted submissions and learn simpler ways to approach the implementation. Then you can stop hating strings!

    Here is my B. ~40 lines, 15 min.

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

      I like your submission but I think this is easier to understand: https://codeforces.com/contest/1181/submission/55655895

      The difference between this submission and the one I had during the contest is that I tried to check everything separately, so the guy I stole this from in 3 lines what took me 15. I don't think its the lines, I usually like clean expanded code, I don't mind long code as long as its properly formatted, that's why I almost never use shortcuts, its very easy for me to write 150 lines, I'm a fast typewriter, its just that its very easy to get confused in such large code.

      The reason this guy pulled it off in 60 lines is because he's done tasks like these several times and for him he just needs to understand the problem, and then the problem is solved, the implementation is no problem.

      For me, I encountered this kind of problem for the first time ever, implementation is almost non-existent because I'm not exactly sure what to do. The greedy solution of taking the middle is obvious, figuring out leading zeroes and summing up strings (and not numbers) is difficult if you've never done it before, and I've also had lots of problems with a lot of corner cases, which this guy solved with his mini function which I did not have and I never thought of it.

      Anywho, I've learned about it and I'm going to be ready the next time such a task arrives, if they ever arrive.

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

    String manipulation is much less annoying in python (in my opinion). My solution was less than 30 lines (and wasn't really optimized), so you might consider using a higher level language. Edit: 13 lines after cleaning up my code a little.

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

    Such problems are easier to implement using languages which already have built-in support for large integers, like Python and Java.
    It is always handy to learn the basics of such language (assuming you use C++).
    55623625 Python solution in 8 lines.

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

About problem B. The complexity of adding 2 strings is O(max length of 2 strings). I added 2 trings with max length <1e5 three times but I got TLE. I couldn't solve B. Can anyone explain? Thank you very much.

»
4 weeks ago, # |
  Vote: I like it +61 Vote: I do not like it

Am I the only person who felt this contest was boring, with lengthy statements and implementations?

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

    I'm not rated high enough to give an expert opinion about this contest, but from my perspective, this was a pretty lame contest. One or two more sentences in each problem to clear some stuff up would go a long way to helping us solve these problems, I feel like some of the information in the tasks were withhold from us just so the tasks would be harder to solve.

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

Do B have weak test cases

I found many codes which fail on

5 10100

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

Fast Testing...Btw i did not like B at all

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

    There's not much to test. Problem A from the last contest has more solves than this entire contest. In fact lets compare. 567 Div2 : 6578 solves

    566 Div2 : 16000 solves

    Take away 2000-3000 solves on after-contest solves and the last round still has 2x more solves than this one.

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

power of system test -> 1200 — 3086

»
4 weeks ago, # |
  Vote: I like it -17 Vote: I do not like it

0 doesn't have leading 0. but in problem B it have !!!!

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

    you sure?

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

    From the problem statement: "To solve the issue, Dima decided to split the strip into two non-empty parts so that each of them contains a POSITIVE integer without leading zeros." 0 isn't a positive number.

»
4 weeks ago, # |
  Vote: I like it +31 Vote: I do not like it

very hard and boring and just implementation

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

B is not fair for C++ ( and other programming languages which do not have bigint library ) programmers.

I solved B using python in 40 lines while C++ needs 100+. ps. sorry for my poor English...

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

    Also, end cases were not covered in the pretests.

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

    55636748

    This doesn't look like a 100 lines.

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

      Actually, the solution will fail at '55'. Why do I know that? Because I made the same mistake. -_-!

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

        but it's accepted...

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

          Wow, that was unexpected.

          Added the test for the upsolving.

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

    Honestly, it wouldn't take more than 3 one liner functions to get the same features.
    But I agree, it is unfair to C++ users.
    they'd have to spend precious minutes writing those functions and it could make the difference between rank 400 and rank 14.

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

What is C test case 20? Anybody else fail on that case?

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

E1 can be solved by simply dividing, now the problem is how to get an $$$O(n \log n)$$$(maybe) algorithm to solve E2.

Pls help me.

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

    Let’s optimize dividing. When we are finding cut, we do it in O(number rectangles in one part). Let’s go in 4 directions in one time and cut min part.

    Also, when we found cut, we should erase one part and keep correct orders in 4 directions. We can do it using stack or list.

    This solution works in O(n log n). (We gave here TL from the original contest, where you can solve this problem with python.)

    (Sorry, more details will be in editorial)

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

      I coded it and got ACCEPT just now. Without doubt this is a really cool problem, thank you!

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

    hint: for a subset of rectangles $$$A$$$, you probably have some function $$$solve(A)$$$ which splits $$$A$$$ into $$$B_1, B_2$$$ and returns $$$ solve(B_1) \text{ } AND \text{ } solve(B_2) $$$. The problem is that this splitting takes $$$O(|A|)$$$. Can you make it take $$$O(min(|B_1|, |B_2|))$$$ instead (with some log-factor)?

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

I had a mistake in adding long numbers. Very irritated now.

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

Could anybody please tell why this submission doesn't work for problem C? https://codeforces.com/contest/1181/submission/55645536

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

Too bad. I can't solve more than 2 problems in a contest that's meant for school students.

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

    It was div 2.

    I think so div 3 is for school students

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

      It was based on All Russian Olympiad which is meant for school students.

»
4 weeks ago, # |
  Vote: I like it +15 Vote: I do not like it

Time to become Expert!

»
4 weeks ago, # |
  Vote: I like it +18 Vote: I do not like it

Problem A has 16 tags now. :O

»
4 weeks ago, # |
  Vote: I like it +20 Vote: I do not like it

Next Div-3 contest is converted to the div-2 contest. lol...

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

There is change in figure of problem C,but no announcement of it -_-

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

Got tle on D, put #pragma GCC optimize("O3") and ios_base::sync_with_stdio bla bla bla and got AC with 889 ms.... damn it hurts...

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

    I guess ios_base with cin.tie would be enough

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

    Yea if ur a cin/cout user u should make it a good habit to use fast io, considering input is large most of the time...

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

    O3 pragma often hurts the runtime instead of improving it. It is the sync_with_stdio that did it for you.

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

      -O3 does wonders on brute-force solutions (just ask MrDindows) but it won't do much to improve the running time of a segment tree, for example.

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

Any hints for problem C? (not in a complexity of 1e9)

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

    n²log(n)= 660000 if you use segment tree to get how much you can extend the flag

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

    Build 2d-prefix array for each character, then consider each $$$(i,j)$$$ as the bottom left corner of the flag. Binary search the heigh of one stripe — the maximum value of $$$h$$$ such that all characters from coloumn $$$j$$$ in range $$$[i, i + h)$$$ are equal. Then check wherher all characters from $$$j$$$-th coloumn in ranges $$$[i+h, i+2h)$$$ and $$$[i + 2h, i + 3h)$$$ are equal. If not — $$$(i,j)$$$ can't be the bottom left corner of the flag. Otherwise use binary search again to find the maximum value value of $$$w$$$ such that all characters in rectangles $$$[(i,j), (i+h-1, j+w-1)]$$$, $$$[(i+h,j), (i+2h-1, j+w-1)]$$$ and $$$[(i+2h,j), (i+3h-1, j+w-1)]$$$ are equal. (Here $$$[a,b]$$$ means the bottom left and top right corners of the rectangle). There is exactly $$$w$$$ possible flags having cell $$$(i,j)$$$ as their left bottom corner, add this value to the answer and procced to the next cell.
    Here is a bit prettified version of my solution: https://ideone.com/dKdcpu

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

    For each j from 1 to m, we count number of submatrices which left most vertices are in column j. To do so, we divide column j into a list of segments of consecutive characters, for example: 'aabbbcd' -> (1,2) (3,5) (6,6) ('aabbbcd' is characters of column j)

    For each 3 consecutive segments, let x, y, z be lengths and c1, c2, c3 be single characters of 1st, 2nd and 3rd segment. For above example, with segments 2, 3, 4, we have: x=3, y=1, z=1, c1='b', c2='c', c3='d'.

    Now we can get the start of correct flags here if c1 != c2, c2 != c3, x >= y, y <= z. Then we can do binary searching to find maximum length which we can append from the start to get a correct flag. Assume it's d, if d = 0 then it means we can't append anymore from the start, and result += 1 (the start). So result += d + 1.

    When do binary searching, we have to check whether all three strips have only one character. To do so, we can precalculate 2d prefix sum of 26 characters.

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

    We can do it in O(n*m)

    Hint : Consider only flags of width one.

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

Could someone please help me figure out what is wrong in the 9th test case in problem B. Here is my submission 55649908. Thanks in advance.

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

    Try for this test case

    3
    110
    

    Your program gives the output 11 which is wrong because splitting 110 into 11 and 0 is not valid. Both numbers should be positive without leading zeroes.

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

    My logic was to look at the correct split point as close to mid point. Is this logic correct Also im not understanding the comment on my answer Could someone please help

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

      Your logic is correct. I think the problem is with your add function. Just try this case

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

        But still, I don't know why this is giving a wrong answer on test 9 with a comment "Not a valid integer".

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

          Could someone provide an explaination to this Thanks in advance

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

        Yeah i didnt take this case into account thanks!!

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

      I didn't check your code, but maybe it is wrong because you need to check splitting not only in mid index (if possible), but in mid + 1 and in mid — 1 too (again, if possible).

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

        I did checked the 4 nearest possiblt splits to n/2 i think that should suffice

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

Weak test cases for problem B

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

    Im sorry didnt get you. Was asking for the mistake in my solution.

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

Had a screwed up contest, when will the editorials be out?

»
4 weeks ago, # |
  Vote: I like it +22 Vote: I do not like it

Editorials?

»
4 weeks ago, # |
  Vote: I like it +20 Vote: I do not like it

Why did this 55636748 get accepted when it is failing for test cases like

2
55

and

2
65
»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Can anyone help me with a test for problem B? This is my solution and i can't find where the bug is https://codeforces.com/contest/1181/submission/55659680

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

How could one prove the corretness of greedy splitting in E?

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

    Let’s look on some correct splitting. What changes then we cut some line? Some next cuts will split set of rectangles in two parts with empty one. All those cuts should be deleted. After deleting correctness doesn’t change.

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

      Please, tell me if i understand well.

      If we look at some correct splitting, we can add this extra horizontal or vertical line, and then some regions may be empty ( without castle ). We can always merge this regions with their neighbours by deleting some parts of existing lines in order to achieve one castle in one region. Is this correct, or am I missing something?

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

        You are absolutely right!)

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

          Ok, thank you for your reply.

          There is actually one more thing im not sure about. After doing this operations shape of some regions may change. How do we ensure that it is always possible to merge them one by one ( finally achieving the whole rectangle ). Some of them will change they size so why is it always possible to obtain correct soltuion? Some of the initial mergings may be not available now.

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

Can you guys help me to debug my solution to problem D? I used a treap to update and find the kth smallest. Code : https://codeforces.com/contest/1181/submission/55663264

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

Nice contest, but way too heavy on data structures. My beginner students were struggle a lot.

Even B uses big integers.

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

Could someone explain why is it that in Problem C 10^9 operations also get accepted. Shouldn't that give TLE. Thanks in advance.

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

getting runtime error on test case 10 in problem D. https://codeforces.com/contest/1181/submission/55675351

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

Thank you for opening the contest.

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

When a new girl enters the class. Boys be like: