Блог пользователя kevinsogo

Автор kevinsogo, история, 5 лет назад, По-английски

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!

  • Проголосовать: нравится
  • +179
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится +54 Проголосовать: не нравится

I am confused.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится -6 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

Will the problems be in English only?

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +20 Проголосовать: не нравится

    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).

»
5 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +44 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 лет назад, # |
Rev. 3   Проголосовать: нравится -12 Проголосовать: не нравится

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?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится -12 Проголосовать: не нравится

Вы неправы

хотелось поломать B, а теперь придётся плакать

»
5 лет назад, # |
  Проголосовать: нравится +79 Проголосовать: не нравится

(b1f8473e9ea8ceb5942935080a4b223c-1

»
5 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

What did people get hacked on in B?

»
5 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

How to solve Div1 C?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +43 Проголосовать: не нравится

    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.

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

What is pretest 2 in Div 2 B ?

»
5 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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.

  • »
    »
    5 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +6 Проголосовать: не нравится

    wrong :/

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится +16 Проголосовать: не нравится

        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.

      • »
        »
        »
        »
        5 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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.

  • »
    »
    5 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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$$$.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Centroid can help you prove this

»
5 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

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('---')
  • »
    »
    5 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +4 Проголосовать: не нравится

    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

»
5 лет назад, # |
Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

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 :(

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
5 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

What is pretest 6 in div 2 C?

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится +128 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +37 Проголосовать: не нравится

    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".

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    How you solved D with dp ?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +37 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +65 Проголосовать: не нравится

    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.

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +18 Проголосовать: не нравится

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

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится +28 Проголосовать: не нравится

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

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится +26 Проголосовать: не нравится

        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)$$$.

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится

      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?

      • »
        »
        »
        »
        5 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится -10 Проголосовать: не нравится

        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.

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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://codeforces.me/contest/1281/submission/66931104

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится +32 Проголосовать: не нравится

How to solve div1 D? answered

»
5 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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.

»
5 лет назад, # |
  Проголосовать: нравится +37 Проголосовать: не нравится
»
5 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

missed problem D because some silly mistake

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
5 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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?

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

tight tl for div1 A ?

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve Div.2 B?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

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

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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 ;

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      5 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

      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

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Can anyone help me with the idea behind Div2 C?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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://codeforces.me/contest/1281/submission/66937956

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone give me a hint on problem 2?

»
5 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Why submission is hidden? when submission can be seen?

»
5 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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...

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone share their approach for Div2 E ?

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve div. 2 D ?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится -23 Проголосовать: не нравится

buggy forces

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What is subcase 136 in pretest 2 ?

»
5 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

How to solve Div1 D?

»
5 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Please provide editorial

»
5 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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) )

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится

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+ ^_^

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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)

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Try this on your solution
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    It helped me, thx!

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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