cdkrot's blog

By cdkrot, history, 5 years 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, vintage_Vlad_Makeev, Zlobober, meshanya, cdkrot 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, budalnik, achulkov2, manoprenko, vintage_Vlad_Makeev, 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. Yelan
  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

| Write comment?
»
5 years ago, # |
  Vote: I like it +74 Vote: I do not like it

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

»
5 years 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.

  • »
    »
    5 years 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

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

Who is Keldysh?

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

The time is very very very friendly to Chinese

  • »
    »
    5 years 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?

»
5 years ago, # |
  Vote: I like it -44 Vote: I do not like it

Clashes with India Vs Pakistan :-/

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

    No problem, rain will interupt the match

    • »
      »
      »
      5 years 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.

      • »
        »
        »
        »
        5 years 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!!!

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

Glad to see vintage_Vlad_Makeev and vintage_Vlad_Makeev working together

»
5 years 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 :(

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

please How many problems were prepared

»
5 years 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

»
5 years 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?

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

    Statements are translated into English for the round.

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

what is the score distribution??

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

Is it a rated contest?

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

I just hope it won't be a mathforces

»
5 years 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?

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

hoping for specialist. prey for me.

»
5 years 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.

»
5 years 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).

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

    You can hack easy version only if you solved hard.

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

How to solve C ?

  • »
    »
    5 years 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

    • »
      »
      »
      5 years 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).

    • »
      »
      »
      5 years 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

      • »
        »
        »
        »
        5 years 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.

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

Hard, but interesting. Thanks!)

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

So hard.55555~~~

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

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

So hard, feel like I am a retard

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

How to solve D?

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

hard problem for B

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

Where does my solution for problem C go wrong: code

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

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

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

    And D = B.

    I really think it feels right like that

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

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

      • »
        »
        »
        »
        5 years 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.

        • »
          »
          »
          »
          »
          5 years 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.

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

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

»
5 years 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!

  • »
    »
    5 years 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

»
5 years 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.

  • »
    »
    5 years 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 ^^

  • »
    »
    5 years 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://mirror.codeforces.com/contest/1181/submission/55639812

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

    • »
      »
      »
      5 years 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.

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

        I solved it with segment tree, check my code.

        • »
          »
          »
          »
          »
          5 years 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://mirror.codeforces.com/contest/1181/submission/55642500

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

          • »
            »
            »
            »
            »
            »
            5 years 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

            • »
              »
              »
              »
              »
              »
              »
              5 years 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 :)

  • »
    »
    5 years 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

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

How to solve E?

  • »
    »
    5 years 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.

    • »
      »
      »
      5 years 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).

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

How to solve D? can you help me.

  • »
    »
    5 years 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.

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

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

»
5 years 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..

  • »
    »
    5 years 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.

  • »
    »
    5 years 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.

  • »
    »
    5 years 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.

»
5 years 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.

»
5 years 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?

  • »
    »
    5 years 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.

»
5 years 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

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

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

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

power of system test -> 1200 — 3086

»
5 years ago, # |
  Vote: I like it -17 Vote: I do not like it

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

  • »
    »
    5 years 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.

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

very hard and boring and just implementation

»
5 years 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...

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

    Also, end cases were not covered in the pretests.

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

    55636748

    This doesn't look like a 100 lines.

    • »
      »
      »
      5 years 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. -_-!

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

        but it's accepted...

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

          Wow, that was unexpected.

          Added the test for the upsolving.

  • »
    »
    5 years 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.

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

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

»
5 years 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.

  • »
    »
    5 years 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)

    • »
      »
      »
      5 years 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!

  • »
    »
    5 years 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)?

»
5 years 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.

»
5 years 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://mirror.codeforces.com/contest/1181/submission/55645536

»
5 years 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.

  • »
    »
    5 years 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

    • »
      »
      »
      5 years 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.

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

Time to become Expert!

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

Problem A has 16 tags now. :O

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

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

»
5 years 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 -_-

»
5 years 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...

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

    I guess ios_base with cin.tie would be enough

  • »
    »
    5 years 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.

    • »
      »
      »
      5 years 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.

»
5 years 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)

  • »
    »
    5 years 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

  • »
    »
    5 years 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

  • »
    »
    5 years 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.

  • »
    »
    5 years 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.

»
5 years 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.

  • »
    »
    5 years 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.

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

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

      It should be 11 which is 10+1.

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

      What you talking about? In this particular case correct answer will 11 cuz we separate 110 to 1 and 10 and sum of this two numbers its 11, dont post stupid idea if dont realy sure about it!

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

      Sorry. 11 is the correct answer.

  • »
    »
    5 years 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

    • »
      »
      »
      5 years 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
      
      • »
        »
        »
        »
        5 years 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".

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

          Could someone provide an explaination to this Thanks in advance

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

        Yeah i didnt take this case into account thanks!!

    • »
      »
      »
      5 years 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).

      • »
        »
        »
        »
        5 years 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

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

Weak test cases for problem B

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

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

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

Editorials?

»
5 years 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
»
5 years 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://mirror.codeforces.com/contest/1181/submission/55659680

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

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

  • »
    »
    5 years 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.

    • »
      »
      »
      5 years 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?

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

        You are absolutely right!)

        • »
          »
          »
          »
          »
          5 years 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.

»
5 years 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://mirror.codeforces.com/contest/1181/submission/55663264

»
5 years 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.

»
5 years 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.

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

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

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

Thank you for opening the contest.

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

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