kevinsogo's blog

Codeforces Round #607 (Div.1, Div.2) based on ICPC Manila 2019
By kevinsogo, history, 5 years ago, In English

Hello, Codeforces community!

I'm glad to invite you to Codeforces Round 607 (Div. 1) and Codeforces Round 607 (Div. 2), which will be held on Dec/15/2019 08:05 (Moscow time). The round will be rated for both divisions.

The problems were taken (mostly) from the 2019 ICPC Asia-Manila Regional Contest that's happening at the same time. Thus, they have been prepared by various setters and testers from the Philippines: myself (kevinsogo), Kyle See (kylesky), Payton Yao (jabbawookiees), Tim Dumol (timd), Guissmo Asuncion (guissmo in HackerRank) and Marte Soliza (myrtactle in TopCoder).

Since the problems are based on the ICPC Manila regionals, we request all the coaches onsite to refrain from making the problem set public. We also request the coaches and everyone else who has seen the problems (or part of it) to refrain from joining this round.

A huge thanks to isaf27 for coordinating and helping me set up this round. Thanks to 300iq for some testing. Of course, thanks as well to MikeMirzayanov for providing us Codeforces and Polygon. These are great gifts to the competitive programming community! Also, thanks for the opportunity to use our problem set for a CF round.

You will be given 6 problems in both divisions and 2 hours to solve them. I recommend reading all the problems; they were written by talented writers from the judging team.

Good luck, have fun, and I wish everyone high ratings!

The scoring distribution will be announced closer to the beginning of the round.

Update: The scoring will be as follows:

Div.2: 500 — 1250 — 1500 — 2000 — 2500 — 3000
Div.1: 500 — 1000 — 1500 — 1750 — 2250 — 3000

Good luck and have fun!

Update: The editorial is up: Click here.

Congratulations to the winners! Congratulations to ksun48 for winning the Div. 1 round, and I_am_single for winning the Div. 2 round!

Div. 1 Winners:

  1. ksun48
  2. Um_nik
  3. ecnerwala
  4. VivaciousAubergine
  5. Radewoosh

Div. 2 Winners:

  1. I_am_single
  2. RikukiIX
  3. Owen_codeisking
  4. ly_61
  5. p6pou

I hope you enjoyed the problems! Thanks to the onsite teams and coaches who gave feedback; I'm glad the reception was positive.

I am planning on releasing the full, untouched ICPC Manila 2019 problem set in the gym sometime in the future, so you can see which problems you missed. The Intergalactic Sliding Puzzle is not the hardest problem in the round!

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

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

Auto comment: topic has been updated by kevinsogo (previous revision, new revision, compare).

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

Is it normal that there are two contests at the same day?

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

I am confused.

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

    You can do both the contests but say goodbye to sleep. I did that once and still got a good score.

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

So, now its possible to make a perfect 'T' shape in the rating curve. :3

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

Will the problems be in English only?

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

why was div2(606) contest held at such time ,also why not even one of 607 and 608 ,at a usual time??

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

    Maybe because that rounds are based on some contest(#606 : Technocup 2020 Elimination Round 4, #607 : ICPC Manila 2019, #608 : Municipal Stage of All-Russian Competitions for Schools, Saratov).

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

What will happen if a candidate master who has registered #608 officially becomes master in #607? Will he/she still be rated in #608?

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

Are there plans to upload the full contest onto codeforces gym? I am very much looking forward to this contest

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

    Yes, I plan on uploading the full set in the gym in the future, along with some past ICPC Manila problem sets too.

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

Auto comment: topic has been updated by kevinsogo (previous revision, new revision, compare).

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

I had this one question, how do problem setters generate big test cases, especially where some particular conditions need to be satisfied, suppose such as the given undirected graph had to be connected, and all?

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

    Ye, for graphs jngen is really awesome, but in general it's pretty uncommon for tests to have hard structure. Like the said connected graph is just a spanning tree (which is easy to generate) with some more edges on top of it.

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

    kevinsogo is the chief judge of ICPC Manila, that's why he has "early access."

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

(b1f8473e9ea8ceb5942935080a4b223c-1

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

What did people get hacked on in B?

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

How to solve Div1 C?

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

    Maximum — for each edge estimate upper bound of pairs which ways can contain this edge (it will be min(size_of_left_tree_if_we_erase_this_edge, size_of_right_tree_if_we_erase_edge). Answer — sum of upper bounds multiplied by weight of edge.

    Minimum — it can prooved that each edge must be taken at most once. Lets make tree rooted and count size of each subtree, we take an edge only if size of corresponded subtree is odd.

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

What is pretest 2 in Div 2 B ?

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

    What ever it was, it was the death of me xD Had like 15 submissions xD

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

      me too, I spent like 1hr 40 minutes trying to figure out that single problem... I guess I will lose a lot of my reputation points on this one... :(

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

        Luckly not that much, just around ~14.

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

          What was the corner case in Pretest 2? I still couldn't figure out.

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

    My code failed BANANA APPLE :(

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

    for test case : IA GOG why AI is not the answer?

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

    My code failed on BAA AABA. My code produced ABA and told me that it's impossible since it is smaller than AABA. smh

    As a grey, I solved A in 4 mins then stuck on B until contest ended. Still got positive delta.

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

    Try

    EBB BBF

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

It took a lot of time to solve Div.2 B :(

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

Div.2 B is a bad problem. There was no test in Div.2 D where the answer was 0.

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

For Div1 C, does anyone have a proof for why the contribution for each edge can be given by the minimum size of two components it connects multiplied by its edge weight? This seemed like a "best case" scenario to me, but I couldn't prove why it would always happen.

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

    wrong :/

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

      Wow, that's a slick proof. Thanks.

      EDIT: Apparently not.

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

      It’s not always possible to split into K and K. For example, a star with 4 nodes.

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

    That’s the upper bound and we just need to show a way to achieve it. Think about the edge that maximizes the smaller components. Pair the nodes based on that edge and the pairings should work for future edges.

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

      Yeah, I had trouble with accepting the "pairings should work for future edges" idea because it wasn't obvious to me that it wouldn't mess up previous pairings.

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

        Find the centroid of the graph, it will split in several subtrees all with size less than or equal to half of the full tree size. For each subtree assign consecutive number 1, 2, ... k, 1, 2, ... k. Notice that none subtree will contain a pair of equal numbers. You can prove that this distribution works good.

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

        Assume the initial 2 components have size X and Y (X <= Y). We need to prove that for further edges, its smaller components should not have more than X nodes. It's obvious for all edges in X side. Assume there exists an edge that produces a component with size Z in Y side such that X < Z < Y. Using that edge as the very first one would give us a better pairings and it contradicts to our initial assumption.

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

    Suppose the removal of the edge splits the graph into sets $$$S$$$ and $$$T$$$ with $$$|S| \le |T|$$$. If $$$ ( i, j ) $$$ is a pair within $$$S$$$, then there must exist a $$$(u, v)$$$ pair within $$$T$$$. Then you can show that pairing $$$(i, u)$$$ and $$$(j, v)$$$ is always better (try and draw a diagram to see why). Hence, each vertex in $$$S$$$ must be matched to something in $$$T$$$.

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

    Centroid can help you prove this

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

I actually failed life How did I not solve 2B???? I'm getting RE/WA on testcase 2 and sometimes even test case 1 (when it works locally) Can someone help please It's an easy bruteforce?? Is my "check strictly lexicographically smaller" function wrong??

Please help

Code:

from random import *
def r(n=10):
    return ''.join(chr(randint(65, 90)) for _ in range(n))

def check(s1, s2):
    if len(s1) < len(s2) and s2[:len(s1)] == s1: return True
    i = 0
    while i < len(s1) - 1 and i < len(s2) - 1 and s1[i] == s2[i]:
        i += 1
    if i < len(s1) and i < len(s2) and s1[i] < s2[i]:
        return True
    return False


for _ in range(int(input())):
    # s1, s2 = r(3), r(3)
    s1, s2 = input().split()
    removed = ""
    while len(s1) > 0 and len(s2) > 0 and s1[0] == s2[0]:
        removed += s1[0]
        s1 = s1[1:]
        s2 = s2[1:]
    f = False
    for i in range(len(s1)):
        tmp = list(s1)
        tmp[0], tmp[i] = tmp[i], tmp[0]
        tmp = ''.join(tmp)
        if check(tmp, s2):
            assert (check(removed + tmp, removed + s2))
            print(s1, s2, removed + tmp)
            f = True
            break
    if not f:
        print('---')
→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 3   Vote: I like it +4 Vote: I do not like it

    Well now I think about it I think I can just use "<" in python to compare the strings... I think that's how python compares already...

    BUT ITS FINE! Next competition in an hour! Hope I promote :)

    EDIT: FUCKKKK I GOT 2C WRONG OMG

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

I was stuck on Div2 B for the whole contest because I didn't read the constraints completely; seeing that the sum of the strings across test cases can only be 5000, I then soon got a AC.

I had around 10 WAs :(

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

    How? What made it so easy after reading constraints? Did you get to know why your solution was failing on pretest 2?

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

      I think that means you can use O(n^2) algorithm to solve this problem. (But I implemented one and still failed...)

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

        Now I passed the pretest 2 using O(n^3) sol (finally!!), but got TLE at pretest 10

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

          O(n^3) would never work as cube of 5000 is like 10^11

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

            Yes, but the 1st place's code is also O(n^3) solution but with trim for some obvious cases. (Notice that the comparison operators for string in C++ is O(n))

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

        Weird. My O(n^2) gave me TLE and I thought I figured out the reason.

        Sum of lengths across test cases doesn't exceed 5000, but we're doing sum of squares of length. In this case it looks like it could possibly exceed one second.

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

What was pretest 2 in Div. 2 Problem B. Azamon Web Services? The problem was very easy but my solution failed on this testcase even after multiple attempts.

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

What is pretest 6 in div 2 C?

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

    As far as I know it is a number where if you don't MOD correctly it fails. Thats how I fixed it, I implemented standerd MOD methods.66924381

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

    For me, on replacing $$$x \% p$$$ by $$$(x \% p + p) \% p$$$, I got AC.

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

      Probably the same, because my neg method basically does this

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

Just my personal opinion (not only my actually), but I didn't like this contest at all

A: it's harder to understand the statement than to solve the problem

B: just case check

C: superfamous problem

D: maybe I shouldn't judge on it if I didn't solve it in time, but isn't it a super standard dp problem

E: solution is fairly easy, the hardest part for me was parsing T_T (that's my fault for being stupid and being unable to parse it but still)

Can't say anything about F

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

    what dp in D? I hardcoded the cases of ans = 4/3/2/1/0, and that seemed to pass..

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

    Looking at the scoreboard, D doesn't seem so standard.

    Although, in my opinion the problem statement is really bad. It's so long for an actually very natural problem. The definitions slowed me down so much especially because they use silly names like "village".

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

    How you solved D with dp ?

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

    Shouldn't an hour be enough to code up a "super standard dp problem"? :P

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

      I was trying to do E instead T_T

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

        Shouldn't an hour be enough to code up an easy parsing problem, everything in brackets, all tokens are of length 1 etc?

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

    Yeah, D is trivial once you notice that combining the DP for the left ($$$L$$$) and right ($$$R$$$) subtrees in time $$$\mathcal{O}(|L| |R|)$$$ is $$$\mathcal{O}(|T|^{2})$$$ work for any tree $$$T$$$.

    Just calculate for every subtree the values $$$DP[k]$$$: The maximum pair $$$(c, s)$$$, where $$$c$$$ is the amount of other villages in the subtree with more wasp than bee voters, and $$$s$$$ is the sum of the village the current node is in, when we have exactly $$$k$$$ villages in the subtree.

    $$$\mathcal{O}(n^{2})$$$ is fast enough, as then we do in the worst case around $$$3000^{2} \cdot \frac{10^{5}}{3000} = 3 \cdot 10^{8}$$$ work.

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

      How do you prove that it's always optimal to maximise $$$c$$$ for every subtree (and sometimes not the sum)?

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

        Because reducing the sum cost you at most one village and that can be compensated by taking the maximum c.

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

        This clearly holds for the root of the tree. Induction on distance from root.

        We'll show that for any $$$k$$$ we always find the maximum pair $$$DP[k] = (c, s)$$$ for the subtree of our current node by only considering the maximum pairs of its children. But this is trivial: The $$$c$$$ we get is just the sum of $$$c$$$'s of the current node's children, and the $$$s$$$ we get is just the sum of $$$s$$$'s for the children, so if we pick for any child a non-maximal pair, we either get smaller $$$c$$$ or equal $$$c$$$ and smaller $$$s$$$. The second case is clearly never optimal, and in the first case, if the (possibly increased sum) is positive, we get an upper bound of $$$(c, 0)$$$ for $$$DP[k+1]$$$, but we would get this anyway from $$$(c, s)$$$.

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

      i thought in a similar way, but thought that i should put c in the parameter of dp. Why can we pull c out of the parameter?

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

        Let's say, we have 2 pairs {ans, sum} where the first one have a strictly bigger ans, but a much smaller sum compared to the second one. If you plan to take the second one, you are sacrificing at least 1 village to get a bigger sum. What's the point in getting a bigger sum? To later on, group it with something that will give you a "good" village, and at most 1 good one can be made.

        Therefore if you don't sacrifice this earlier village and later on you can't create a "good" village, it's practically the same thing. Therefore it's always better to take the one with the maximum ans.

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

      Can you please tell what is $$$s$$$ here? I didn't get what is the meaning of the sum of the village. Do you mean $$$s = no. of wasps - no. of bees$$$?

      Sorry if it's a silly question.

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

        Yeah, $$$s = \sum_{i \in \text{village}} \text{wasps}[i] - \text{bees}[i]$$$.

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

    Can somebody help me why my submission to Div2 C that is Div1 A is getting TLE on test 6 when I am using similar thing as antontrygubO_o

    https://mirror.codeforces.com/contest/1281/submission/66931104

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

How to solve div1 D? answered

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

it seems everyone(myself too :) ) messed up DIV2B due to over optimization. O(n^2) solution passed

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

DIV 2 B :-coding is not important than finding the edge case (What this problem said to me ?)

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

I think F can be solved as follows:

Put empty square in bottom middle always. Then you have two "dials", with a shared "center" square board[0][k].

Now you can define some moves like L = u l^k d r^k = left dial clockwise by 1. Similarly you can define left/right dial clockwise/counterclockwise by 1. Using L^t you can do left clockwise by t, etc. Across all these shortcuts, the empty square is always in the bottom middle.

Now your goal is to put the left dial correct except for 2 adjacent numbers, then put the right dial correct. You can do this just by spinning the dials. At the end, either the adjacent numbers are correct, or its not and the surgery failed. The existence of a failed testcase in the example proves that there is no "swap" operation, so the testcase is indeed impossible.

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

Div1C(max case): https://mirror.codeforces.com/contest/700/problem/B

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

missed problem D because some silly mistake

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

    Same. In one case check I used r instead of c and vice versa and during whole contest trying to find a case where my solution is wrong.

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

My submission isn't checked in system test. The submissions which submitted in minute 35 is checked but my submission is in minute 16 it doesn't checked why?

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

tight tl for div1 A ?

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

    Yeah, I got TLE for using mod.

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

      damn ... me too i guess

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

        I think test 18 is something like you have a string of length around $$$10^6$$$ and you do around $$$10^6$$$ paste operations while the length doesn't increase every time.

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

          i handled it . i copied it s[i] — 1 times to the back .. maybe its about I/O

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

What if my submissions were AC during the contest, but have received TLE during system testing?

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

    Can I ask for rejudge or something like it? If yes, how?

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

      Forget about it, looks like some tests have changed

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

How to solve Div.2 B?

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

    just construct the minimal word you can and compare with the target.

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

      I did the same, i think to construct the smallest possible answer then compare. I am not able to find my mistake ,as i got wrong on pretest 2.Here's the submission: 66923355

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

        you should find the last charcter . for example "bbbbaa", minimal should be "abbbab", not "abbbba"

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

why am i not able to see other people's code (which is submitted)?

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

is Div1 C Well-Known problem? Thinking solution about max case of problem C is some relevance of the previous problem I solved but I can't remember what the problem it is

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

    I think separating linear walk in a tree work for Min case . For Max case take edge which separates tree into two parts and get answer as the sum of subtree size * edgeWT , for all edges ;

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

    Can you share the approach to Div1 C? And also links to similar problems..

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

      min case -> sum all of the edge weight to min case answer and from root 1, if the path is x -> y and the number of child node of y is divided by 2, then subtract the x->y 's edge weight to the min case answer

      because if the number of child node is divided by 2, then the set of child node can match each other in any order

      max case -> from root 1, if the path is x->y and the number of child node of y is NUM, then add the min(NUM,child_node[1]-NUM)*(x->y 's edge weight) to the max case answer

      because Maxmizing use of all of the path x->y is optimal

      Surely, you choose any node to root

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

      i am not good at writing english.. So, if you can't understand what i replied above, i am sorry

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

MikeMirzayanov My submission isn't controlled and it is submitted in min.16

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

Can anyone help me with the idea behind Div2 C?

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

    Only implementation. I literally just implemented the operations, except the fact that if string length (which is always increasing very quickly) becomes $$$>x$$$, I didn't actually update the string, rather just updated the $$$length \% MOD$$$ of the string. And as the MOD-ed length can be less than $$$l$$$, be careful of that. My submission if you want: 66928873

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

    Cut and paste until the string length is equal x.

    suppose, x = 7 and given string is "231" then construct the string it doesn't reach "2313113".

    Then iterate the whole string and increase the length if necessary.

    initially, length = length of the given string and we can assume that first index of the constructing string is 0 and last index x-1.

    For every character,

    If the character is '1' then length remains the same.

    If the character is '2' then length = i+1 + ((length-i-1)*2);

    If the character is '3' then length = i+1 + ((length-i-1)*3);

    Don't forget to use modulus.

    My solution — > https://mirror.codeforces.com/contest/1281/submission/66937956

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

Can anyone give me a hint on problem 2?

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

Why submission is hidden? when submission can be seen?

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

get a WA on div.2 D test 8...

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

In Div1C, can negating the edges to get the min answer if we find the max answer work?

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

    In theory of course, but it depends on how your solutions works. If you have a general algorithm that handle any weight min/max is just the same.

    In this particular case my two solutions (for min and max) work for positive weight only, and I believe it was intended, so the answer to your question for this problem is no.

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

Spent almost 1 hour find O(N) solution in div2B because didnt realize that solution O(N^2) will pass :(

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

In Div2 C when i just use for loop my solution got tle on test 18...66931998 bt when i just replace it from predefined substr string function my solution Accepted....66932640 but predefined substr function complexity is also O(n) then why it give TLe... Correct me if i am wrong...

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

Can someone share their approach for Div2 E ?

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

How to solve div. 2 D ?

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

    If there are no A's then you can not convert the matrix, so answer for this case is 'MORTAL'. otherwise, check for each row and column whether you can convert this row or column into all A's. If yes, then using this row or column you can convert entire matrix into A's. Take minimum at every step.

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

Isn't in $$$Div2 C$$$ if you Generate the string in each step it should give $$$TLE$$$. Because as far as I know string concatenation in $$$O(n)$$$ operation

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

    but predefined substr string function also takes O(n)...

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

      Same bro I didn't code the obvious solution because I thought it is $$$O(n ^ 2)$$$

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

    Just make a character array of size about 10^6 , then you can generate that required string of length x in O(x).

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

    You don't need a string whose length is greater than X to solve Div.2 C.

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

buggy forces

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

What is subcase 136 in pretest 2 ?

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

How to solve Div1 D?

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

For div1 C for max -> summation of distances of all nodes from centroid also works

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

Please provide editorial

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

Here is my approach for Div2 B — Azamon Web Services.

Idea: We find the smallest string that can be obtained when we are allowed only a single swap.

Let sorted string be $$$s'$$$. Now if the string $$$s$$$ is already sorted, then $$$s' = s$$$. But if string is not sorted, then we have an index $$$j \in [0, |s|)$$$ such that $$$s'[j] \neq s[j]$$$. We loop through $$$s$$$ to from the end to find this character (find $$$s'[j]$$$ in string $$$s$$$ from end) and let its position be $$$k$$$. We swap $$$s[j]$$$ and $$$s[k]$$$. This new string, call $$$s' '$$$ is the lexicographically smallest string obtainable from $$$s$$$ with one swap.

Now simply compare $$$s' '$$$ and $$$c$$$. Complexity $$$O(|s| \log|s|) $$$ My submission : 66919628

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

I think I don't fully understand d. so is there a problem if we lose? ( I mean we must find the maximum in the cases that we dont lose the game ) ?

If its a problem then how to solve the problem if we can lose the game to ( Stop at a city (Don't have enough soldiers) )

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

The problems were quite easy, the first four problems felt like they could been in a Div 3 contest. The problem D could be replaced a harder problem. :D

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

I have solved problem 1281B - Azamon Web Services be with implementation code 66977057 Omg i am very happy for this accepted My rate geten up 115+ ^_^

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

Im getting a weird runtime error that question Question B can someone look into my solution ans help me. https://mirror.codeforces.com/contest/1281/submission/66990716

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

    Hey, a possible source of error could be that you are varying $$$i$$$ according to size of string $$$s$$$ but don't check out of bound error for string $$$c$$$ (no mention of c.size() anywhere in code)

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

Does someone know what's the testcase 41 in test 2 problem B? Answer is IUWWWWWWUUUUUUWZ

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

    In that test case you need to consider cases of equality of characters. For Example:- AAAGIZZB AAABZZE You can swap G with B to obtain AAABIZZG which is lexico smaller than AAABZZE

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    Try this on your solution
    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It helped me, thx!

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

Is ans >= 1000000007 very slow in python? I got TLE use if ans >= 1000000007 before ans % 1000000007? submissions: 67007248 and 67007151

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

Auto comment: topic has been updated by kevinsogo (previous revision, new revision, compare).

→ Reply