300iq's blog

By 300iq, 3 months ago, In English,

Hi!

On Mar/19/2020 17:35 (Moscow time) we will host Codeforces Global Round 7.

It is the first round of a 2020 series of Codeforces Global Rounds. The rounds are open for everybody, the rating will be updated for everybody.

The prizes for this round:

  • 30 best participants get a t-shirt.
  • 20 t-shirts are randomly distributed among those with ranks between 31 and 500, inclusive.

The prizes for the 6-round series in 2020:

  • In each round top-100 participants get points according to the table.
  • The final result for each participant is equal to the sum of points he gets in the four rounds he placed the highest.
  • The best 20 participants over all series get sweatshirts and place certificates.

The problems of this round were developed by isaf27 and me. Thanks to the testers mohammedehab2002, Taran_1407, Aleks5d, Endagorion, 74traktor, HIR180, dlwocks31,ToTheMoon, coyorkdow, Tzak, DomiKo, JustasLe, Hyado, Nemo, tattosha_aptan, Jatana, and (language corrector!) caoash.

Thanks to XTX, which in 2020 supported the global rounds initiative!

Good luck!

UPD: Score distribution: 500 1000 1000 (1000-1000) 2500 (2000-1500) 4000

UPD: Editorial!

Announcement of Codeforces Global Round 7
 
 
 
 
  • Vote: I like it
  • +565
  • Vote: I do not like it

»
3 months ago, # |
  Vote: I like it -13 Vote: I do not like it

I hope to get a t-shirt <3 :)

  • »
    »
    3 months ago, # ^ |
      Vote: I like it -27 Vote: I do not like it

    Why people are down voting? Is is offensive for a newbie to have a cherish for getting a T-shirt in CF?

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

      being in top 500 in combined round means his real rate should be higher

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

      It's just ratism. Smh at least he said "I hope", not "I will"

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

        Hope is a good thing.

      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it -49 Vote: I do not like it

        yeah...Ratism exactly

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

        What rating do you think that people will upvote for "I hope to get a t-shirt" at the top of the comments of a contest announcement? I don't think others are interested in his hope.

        I'm not saying that he can't hope for a t-shirt, but I think "I hope to get a t-shirt" is meaningless to me, and he also can't get any help — he can ask "how to improve on a specific topic" if he really wants to get a t-shirt.

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

          Well, I'm not saying one should upvote him. Maybe his comment is not useful, but it's not harmful or annoying too. I think amount of downvotes he's getting is a bit much and probably many people downvoted him because he can't do it.

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

            IMO it's kinda annoying. It's just noise, and I think it's reasonable to discourage noise.

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it -25 Vote: I do not like it

      Thank you for your support :)

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

    don't let the downvotes frustrate you , It is all about a long journey of hard working . wish you the best ❤️

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Order online :P

  • »
    »
    3 months ago, # ^ |
    Rev. 2   Vote: I like it -30 Vote: I do not like it

    From your words we can infer that your real rating is $$$2164$$$ instead of $$$1082$$$

»
3 months ago, # |
Rev. 2   Vote: I like it -27 Vote: I do not like it

This comment has been deleted due to negative feedback

»
3 months ago, # |
  Vote: I like it +309 Vote: I do not like it

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

    We are really sorry for the delay. :(

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

    I guess you'll need smaller size now :D

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

    Bruh I got one from Global Round 1 and still waiting.

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

    According to the rules at most 50 people will get T-shirt but >=254 people are concerned about it. Nice!

»
3 months ago, # |
  Vote: I like it -33 Vote: I do not like it

Well, I know I won't get anything, this doesn't mean I won't participate.

Anyways, what Div is this?

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

    Div1 + Div2 , it's rated for everyone.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it -32 Vote: I do not like it

    Why is it getting so many downvotes, I didn't say anything wrong

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

      Why you won't get anything?

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

        Give him a break. He obviously meant that he was not expecting to win any prize.

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

      You don't need to say anything wrong to get a lot of downvotes.

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it -19 Vote: I do not like it

      You are getting down vote because you think yourself out of everybody.

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

        Thinking yourself within everybody isn't helping you much, is it? :P

»
3 months ago, # |
Rev. 2   Vote: I like it +11 Vote: I do not like it

Hope you have a good year.

»
3 months ago, # |
  Vote: I like it -20 Vote: I do not like it

Is it very hard?? I'm a newbie so I don't know i can have a t-shirt.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Extremely.

  • »
    »
    3 months ago, # ^ |
    Rev. 2   Vote: I like it -110 Vote: I do not like it

    [The post that you want to dislike ,currently do not exists]

    • »
      »
      »
      3 months ago, # ^ |
      Rev. 2   Vote: I like it -90 Vote: I do not like it

      [Deleted]

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

        He didn't ask the difficulty of solving all problems, so the "truth" is: there are problems from the ones which can be easily solved by a pupil to the ones which are challenging for a grandmaster.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it -21 Vote: I do not like it

    try to solve at least 2. its hard but you can .

»
3 months ago, # |
  Vote: I like it +6 Vote: I do not like it

How many problems are there and what's the score for each problem?

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

    It will be announced 3 seconds before the contest start

»
3 months ago, # |
  Vote: I like it +47 Vote: I do not like it

I hope this round will have strong pretests. :)

»
3 months ago, # |
  Vote: I like it -24 Vote: I do not like it

MOOSAGA HAHAHAHA

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

No thanks to Mike. I am very afraid.

»
3 months ago, # |
  Vote: I like it +12 Vote: I do not like it

Really excited for the classical competitive programming questions. Global codeforces rounds are always great for learning.

»
3 months ago, # |
  Vote: I like it +75 Vote: I do not like it

Ivan and Ildar are trusted authors :sunglasses:

»
3 months ago, # |
  Vote: I like it +141 Vote: I do not like it

»
3 months ago, # |
  Vote: I like it +6 Vote: I do not like it

It's good to see another combine round here. I hope everyone doing well with their rating.

»
3 months ago, # |
  Vote: I like it -25 Vote: I do not like it

only want to solve problems and learn as much as I can.

»
3 months ago, # |
  Vote: I like it +2 Vote: I do not like it

I hope to get a t-shirt <3 :)

»
3 months ago, # |
Rev. 2   Vote: I like it +55 Vote: I do not like it

Off-topic, but I found this interesting. There's a search option on the Contest page to search for particular contests. Not many platforms have this feature. I don't know how many of you knew that already.

  • »
    »
    3 months ago, # ^ |
    Rev. 4   Vote: I like it -22 Vote: I do not like it

    But it's better to use CTRL+F to search. Because that works far better than cf search feature, like I searched div 3 and it did not work(because I missed the dot), because it matches with the exact word. But using chrome's ctrl+f it was successful to find the result.

    Edit: Why am I getting downvotes? Is there anything wrong?

»
3 months ago, # |
Rev. 3   Vote: I like it +15 Vote: I do not like it

Hope that I can solve ABC ❤️

Good luck guys ❤️

»
3 months ago, # |
  Vote: I like it -13 Vote: I do not like it

They had us in the first half, not gonna lie. Hoping for a great contest.

»
3 months ago, # |
  Vote: I like it +30 Vote: I do not like it

May I know who is the coordinator? :P

»
3 months ago, # |
  Vote: I like it -13 Vote: I do not like it

How could you guys forget thanking MikeMirzayanov for the amazing platform.

»
3 months ago, # |
  Vote: I like it +13 Vote: I do not like it
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What's more difficult? Securing a rank under 500 or getting a Tshirt after that?

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

    I think getting a tshirt. Because getting under 500 rank depends on your hard work, but getting that random depends on luck.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

300iq contest means troll problems. Time to become cyan!

»
3 months ago, # |
  Vote: I like it -26 Vote: I do not like it

Yesssss!!! ... I think my rank gonna be 500 and I am so happy because rank 31 to 500 INCLUSIVE, not EXCLUSIVE!!!! gonna get a t-shirt randomly ... so lastly I am likely to get a t-shirt... Thanks GOD!!!

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I will get 0 points :(

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

High ratings everyone :)

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope the statement of problems be short like the blog :D

»
3 months ago, # |
  Vote: I like it +1 Vote: I do not like it

I need not to stand 1st but will very happy if I can solve 3 problems. :)

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

Hi! The codeforces app here .

»
3 months ago, # |
  Vote: I like it +6 Vote: I do not like it

How many problems will be there?

»
3 months ago, # |
Rev. 2   Vote: I like it -10 Vote: I do not like it

are we going to see a dp problem after all?

»
3 months ago, # |
  Vote: I like it -14 Vote: I do not like it

Please, help me to solve this problem

It is about polygon

»
3 months ago, # |
  Vote: I like it +1 Vote: I do not like it

How long is it gonna be?

»
3 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Hoping it to be a div 2 level contest with 6 problem having strong pretest cases. :)

»
3 months ago, # |
  Vote: I like it +12 Vote: I do not like it

With how many problems?

»
3 months ago, # |
  Vote: I like it +21 Vote: I do not like it

Me After 1 successful submission. Let's Check Leader Board and friends standings :)

»
3 months ago, # |
  Vote: I like it +2 Vote: I do not like it

According to the time left before contest the contest is suppose to start at 08:05. Please have a look

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

All the best guys, hope this round will also be very enjoying, and will bring some new concepts in the box..♥♥

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

If XTX is gone, who is sponsoring the prizes this time then?

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

    Thanks to XTX, which in 2020 supported the global rounds initiative!
    This blog also has XTX logo. I don't think XTX is gone.

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

My best wishes to everyone in the house, hope this round will bring new developments in you, and will be marked an amazing experience for you all... ♥♥♥

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Best of luck to everyone!

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

Expert will belong to me again after this round haahahahahahaahaaaaaaaaaaaaaaaa

»
3 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Score distribution??

»
3 months ago, # |
Rev. 2   Vote: I like it +61 Vote: I do not like it

Effect of Corona Virus situation. 17500+ registration.

»
3 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Hope for best, Number of Problem solved == Number of people cured from covid19

»
3 months ago, # |
  Vote: I like it +29 Vote: I do not like it

everyone wash your hand and start coding. All the best...

»
3 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Cant submit, i keep getting: You have submitted exactly the same code before

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yup, I got the same issue, it was around 5 minutes late for B ~ 20points

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    My solution is just too simple, you may know it but i still wanna say that if you add a comment line or just couple of slashes at the end of your code, then its done, you can submit it.

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I know this, but I was getting this error for every code I try to submit, for about 5 minutes I couldn't submit anything.

»
3 months ago, # |
  Vote: I like it -12 Vote: I do not like it

Such Long Queues !!

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

God bless adamant !

»
3 months ago, # |
  Vote: I like it +51 Vote: I do not like it

Subtasks === poor problemset

»
3 months ago, # |
Rev. 2   Vote: I like it +236 Vote: I do not like it

Me when I read problem F:

»
3 months ago, # |
  Vote: I like it +46 Vote: I do not like it

![ ]()

C, WA on pretest 5.

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

    same i also got Wa

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

    Same here, and I had to wait for the feedback, because of the long queue :(

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

    I also got WA at pt-5 for several time. Finally got AC.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    Any idea of how to solve it?

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +14 Vote: I do not like it

      Almost 2000 lines of templates, lol =))

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

        As a friend of mine, an author of this round, said, 2000 lines of templates is like putting on your trunks not in the dressing room near the pool, but at home in order to swim faster.

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      orz

»
3 months ago, # |
  Vote: I like it -21 Vote: I do not like it

Good Job everybody!!! Thanks God for not missing this global round! :)))) And also hope every pupil to get cyan just like me :)))

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Don't say bullshit =)

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    First of all congratulations!

    Second, can you tell me how did you solve C? my idea is to add to a variable largest k numbers, then number of valid sequences is to increment another variable with distance between every k big numbers (But I hit WA 5).

    If my approach is wrong, then what's the correct one?

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

      When you are taking the largest k numbers at that time you can mark those position of permutation. Then For number of valid sequence you need to iterate the whole array of your marked position in the reverse order and increase a counter until your marked position doesn't come. If it comes just multiply the variable with your ans of valid partition and decrease the counter to 0. Don't forget to start your iteration from a marked position as well as your initial ans should be 1.

»
3 months ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

How to solve D? Upd: can it be solved without Manacher's algorithm?

»
3 months ago, # |
  Vote: I like it -12 Vote: I do not like it

Queue,Speed,Think,String and Math FORCES.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C and D ?

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For C read 1. Read statement carefully : 2. Find first k maximum elements of the permutation and store their indices in a vector. 3. these vector contains sorted indices as we traversed from 1 to n to store indices of first k maximum values.

    1. for first part of answer just find the sum of first k maximum values
    2. for second part multiply different of adjacent indices in the obtained indices vector and modulo it with given number ...
    3. finally output both the parts..
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve E?

»
3 months ago, # |
  Vote: I like it +58 Vote: I do not like it

A little disappointed by the contest.Not much to think in Problems A,B,C,D .

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

    I can't agree any more. But it need much more careful to implement them. I finished 5 problems but only got 4 problem's score.

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

    I could only solve A & B :(. So it just depends on your experience, I reckon... But again, I'm a Pupil, so you might be right :)).

»
3 months ago, # |
  Vote: I like it +25 Vote: I do not like it

First thing came to my mind when I read title of problem D — link

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve E? I figured out I need a structure that holds pairs (x, y) and allows me to answer queries "what is the maximum y for x > c", but I don't know how to do that.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Lazy segtrees :") (I got the soln in last few minutes, spent the rest of the time trying to implement retroactive Priority queue without luck)

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

    The answer is at least $$$res$$$ if there exists some suffix with more values at least $$$res$$$ than bombs.

    Thus, to check if the answer is at least $$$res$$$, make a segment tree with range sum and maximum, store in it suffix sums, where each value at least $$$res$$$ is $$$+1$$$ and each bomb is $$$-1$$$, and check if there exists some suffix sum that is greater than zero. If there does, the answer is at least $$$res$$$. Otherwise, answer is less than $$$res$$$.

    Lastly we just need to note that the answer never increases, so we can maintain this segment tree, making in total at most $$$2n$$$ changes and $$$2n$$$ queries.

    Code: 73693217

»
3 months ago, # |
  Vote: I like it +54 Vote: I do not like it

So what's F1? By the number of people who got it it seems to be much easier than F2, but the weird scoring (2000-1500) suggests that F1 requires the harder step in whatever the full solution is. What's up with that?

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

    F1 is meet in the middle that, without any particular optimisations (at least I didn't try any), works in ~1s. Since MITM increases exponentially, the step from F1 to F2 isn't straightforward, but it might be some stupid constant optimisations...

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Well my MITM ran in 52sec locally and obviously TL-ed on the system. Half an hour of optimisation didn't get me any further. Obviously mine sucks so could you give some details on yours?

      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it +15 Vote: I do not like it
        vector<cat> cnt[1<<14][14];
        for(int i = 0; i < (1<<N); i++) if(__builtin_popcount(i) <= N-N/2)
          for(int j = 0; j < N; j++) if((i>>j)&1) cnt[i][j].resize(1<<6, 0);
        for(int i = 0; i < N; i++) cnt[1<<i][i][0] = 1;
        for(int i = 1; i < (1<<N); i++) if(__builtin_popcount(i) < N-N/2)
          for(int j = 0; j < N; j++) if((i>>j)&1)
            for(int k = 0; k < N; k++) if(!((i>>k)&1))
              for(int s = 0; s < (1<<5); s++)
                cnt[i|(1<<k)][k][2*s+G[j][k]] += cnt[i][j][s];
        vector<int> rev(1<<N, 0);
        for(int i = 0; i < (1<<(N-N/2-1)); i++)
          for(int k = 0; k < N-N/2-1; k++) rev[i] = 2*rev[i] + ((i>>k)&1);
        vector<cat> ans(1<<(N-1), 0);
        for(int i = 1; i < (1<<N); i++) if(__builtin_popcount(i) == N/2)
          for(int j = 0; j < N; j++) if((i>>j)&1)
            for(int k = 0; k < N; k++) if(!((i>>k)&1))
              for(int s1 = 0; s1 < (1<<(N/2-1)); s1++) {
                int s_start = (2*s1+G[j][k]) << (N-N/2-1);
                for(int s2 = 0; s2 < (1<<(N-N/2-1)); s2++)
                  ans[s_start+rev[s2]] += cnt[i][j][s1] * cnt[(1<<N)-1-i][k][s2];
              }
        

        Here cnt[i][j][k] is the number of ways to get string $$$k$$$ if we use subset $$$i$$$ and the last used element from $$$i$$$ is $$$j$$$. Then we combine "set $$$i$$$ ending with $$$j$$$", "edge $$$j-k$$$" and "set $$$\lbrace1\ldots N\rbrace\setminus i$$$ ending with $$$k$$$, reversed order", with $$$N/2-1$$$, $$$1$$$ and $$$N-N/2-1$$$ characters respectively; rev[i] is just to get the reverse of any binary string $$$i$$$ with length $$$N-N/2-1$$$.

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

        Fix the midpoint $$$[n]$$$. Partition the remaining $$$n-1$$$ elements into halves of size $$$n/2$$$ and $$$n-1-n/2$$$. Solve these halves by DP or by enumerating all permutations, counting how often you can make each of $$${0, 1}^{n/2}$$$ (or $$${0, 1}^{n-1-n/2}$$$ respectively). Paste everything together in $$$2^{n-1}$$$ time.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    "but the weird scoring (2000-1500) suggests that F1 requires the harder step in whatever the full solution is" — that's not the correct logic in subtasks xD

    And I guess you can come up with many solutions to F1. Mine looks on the first sight as $$$O(4^n)$$$, but it is in fact $$$O(3^n)$$$. Maybe fact that $$$\sum_{k=0}2^k {n \choose k} = 3^n$$$ will lead you on the right track.

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

    I passed pretests on F1 (73723311) with a meet-in-the-middle approach that probably shouldn't have worked.

    First calculate for every subset of up to $$$\left\lceil \frac{n}{2} \right\rceil = h$$$ wise men, how many ways there are to put them in a row such that the last one is wise man $$$i$$$ and the adjancencies are some mask $$$m$$$, just like how you would solve the Hamiltonian path problem. This part takes $$$\mathcal{O}(\binom{n}{h} n^2 2^{h})$$$ work.

    Then just naively combine these, by looping over first $$$h$$$ wise men, the two wise men that we will join the two parts on, and the adjancency masks of both parts. This part is $$$\mathcal{O}(\binom{n}{h} n^{2} 2^{n})$$$ work, which is around $$$10^{10}$$$, but the constants are good enough that the code works in around half the time limit.

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

      Mine was of the same complexity. It ran for ~1 minute locally and wasn't close to passing :|

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

    F1 is stupid.

    Calculate $$$\mathrm{dp}[\mathrm{mask}][i][s]$$$ — the number of ways to build the string $$$s$$$ if we have already visited the people in $$$\mathrm{mask}$$$, with the last visited person being $$$i$$$.

    This seems like it's obviously too slow, but we can notice that the length of the string $$$s$$$ is smaller if the popcount of the mask is small. Implement the DP table as vector<ll> dp [1 << MAX_N][MAX_N], and let the length of $$$\mathrm{dp}[\mathrm{mask}][i]$$$ be $$$2^{\mathrm{popcount}(\mathrm{mask}) - 1}$$$.

    I verified, before coding it, that calculating this takes about $$$10^8$$$ "operations".

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I managed to solve it with a standard $$$O(n^2 2^n)$$$ DP for a given string $$$x$$$ by exploiting the similarity between sequential strings, which in most cases differ only in a couple of lower bits. Therefore, when solving for string $$$x$$$, you can reuse a lot of the memoized solutions for DP states that you computed for string $$$x-1$$$.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

someone pls give me a hint (not solution) for E ?

»
3 months ago, # |
  Vote: I like it -22 Vote: I do not like it

Who liked the round put the "class" (the round was prepared by my classmate)

»
3 months ago, # |
Rev. 2   Vote: I like it +31 Vote: I do not like it

FactCheck: The number of friends of tourist is even greater than number of global contest participants.

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

Is it possible to solve D with hashing?

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

    Yes, I solved it this way with hashing: Get the longest prefix + suffix that matches(are equal).

    Then, get the longest palindrome in the mid of the string that doesnt contain the prefix and the suffix. To get this palindrome, use rolling hashes for all ranges (l, i) and (i, r), where l and r denotes de range of the mid of the string.

    Code: https://codeforces.com/contest/1326/submission/73727428 (Hacked)

    Code: https://codeforces.com/contest/1326/submission/73773544 (Accepted)

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

    can be done by hashing.

    I used kmp though.

    My solution:

    find the longest prefix and suffix to be equal.

    Then in the remaining string, find the longest palindromic prefix or suffix. In order to do that, link. I wish I had bothered to Googled for this earlier, could have saved almost 30 minutes of mine.

»
3 months ago, # |
  Vote: I like it -59 Vote: I do not like it

Thanks a lot to pikmike and vovuh for not coordinating this round.

»
3 months ago, # |
  Vote: I like it -56 Vote: I do not like it

There was already a youtube video explaining the solution for problem E

»
3 months ago, # |
  Vote: I like it +141 Vote: I do not like it

Yet another reason to hate subtasks at Codeforces: I solved D2 first, but my submission was stuck in the queue for 3 minutes. That situation either forces you to take the risk to get a WA on pretests on both problems, or to get 3 minutes more penalty on the first subtask. On other online judges this is a non-issue, as a submission to a problem is automatically a submission to all of its subtasks.

»
3 months ago, # |
  Vote: I like it -15 Vote: I do not like it

Welcome to a permutation contest ...

»
3 months ago, # |
Rev. 3   Vote: I like it +1 Vote: I do not like it

Can anyone hack my solutions for D? They are accepted even if my bases for hashing < 26

For D1: 73684043

For D2: 73683903

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

    lol ask boboniu (ranked 3rd in this contest), he hacked mine even though I considered my bases quite safe.

    ;_;

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

      Differenr from you, I used two different small bases and diffirent mods lol

      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it -8 Vote: I do not like it

        I don't think that will be hard either, two small bases further increase the chance of collisions.

        Not sure, but I think collisions should be more evident in your case.

»
3 months ago, # |
  Vote: I like it +42 Vote: I do not like it

What the hell is going on with order of judging submissions?

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Only submissions after 20 minutes from beginning of contest are judged.

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

    I guess they're ignoring everything submitted before 0:19 for now...

»
3 months ago, # |
  Vote: I like it -97 Vote: I do not like it

Hello, I wanted to propose that there are problems that seek to minimize the coronavirus transmission curve. Perhaps problems where data are given on the populations by age of different parts of the world, even the least populated and their communication channels, run a simulation of the interactions over time and wonder what would be the best strategy. A first intuitive solution would be, for example, to divide the inhabitants by age or risk groups and those least prone to getting sick, to send them to the densest urban centers and the least prone to the least dense urban centers, once they have been infected and cured. healthier they can go back to less populated places, so there would be less spread. What do you think ?.

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

i use KMP to solve D2 but i give TLE i think my code is O(sizeof(string)) for each test case anyone know why? my code

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

    ss = s + s[i] is the problem, s = s + y is O(|s| + |y|) , much better is to use s+=(y) as this is O(|y|) . I think that will solve the TLE issue , since I used KMP too

»
3 months ago, # |
  Vote: I like it +45 Vote: I do not like it

Anyone used EERTREE + binary jump on D? XD

»
3 months ago, # |
Rev. 2   Vote: I like it -8 Vote: I do not like it

how is this solution correct https://codeforces.com/contest/1326/submission/73692335

I tried a hack on it but the verdict said unsuccessful hack attemptt-

1

10

the result came out 2222222237 which is divisible by 7

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

    2222222237 / 7 = 317 460 319,571429

»
3 months ago, # |
  Vote: I like it +33 Vote: I do not like it

how does the system test work? it looks like it doesn't sort the submissions in time order

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

In the permutation partition problem I had applied the same logic as given in the editorial but I got wrong answer in pretest 5.Please help[submission:73710370]

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Your logic was correct but I'm afraid due to integer overflow during your calculation of: long long sum=n*k-k*(k-1)/2; you are getting wrong answer. Both n and k are declared int but their value can be 200000 and thus n*k >= INT_MAX.

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      yeah!! thank you! But what is the maximum accepted value in long long???

      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        long long range is : -9223372036854775808 to +9223372036854775807 (simply google it) Enough to fit calculated value. Just change type of n and k to long long and your code will be accepted. In general, I suggest you to always use long long type to avoid falling in overflow traps.

»
3 months ago, # |
  Vote: I like it -89 Vote: I do not like it

Please increase python complexity. Even O(NlogN) gave TLE in question C. Please rejudge.

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

    Don't think that you somehow deserve to get Accepted using Python.

»
3 months ago, # |
  Vote: I like it +194 Vote: I do not like it

What about giving full score (without drain) for easy subtask if you have solved hard? It is not ideal, but solves some problems of current state.

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

    There is a great satisfaction in having taken the risk to the solve the hard, then to get to do this pointless submission which you are sure will pass :p

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

    I agree, but I believe this brings other complications. How would you handle wrong submissions? Would you give double penalty (one for each subtask) on non-AC verdicts?

    The main issue is that subtasks are treated as separate problems. That shouldn't happen. There should only be one task, where each submission gives partial points if it passes the small testset, and full points if it passes the big testset. Just as it is done in other judges. This way, contestants can stop worrying of compromising their score or having their submissions wait in queue. It's also easier to handle wrong submissions. Just penalize if a submission doesn't gain any points.

»
3 months ago, # |
  Vote: I like it -58 Vote: I do not like it

I got a message saying my solution coincides with my alternate account

"Your solution 55166209 for the problem 1175A significantly coincides with solutions karunk/55140411, sayuri/5516620"

But I never logged into my alternate account! If you go to the profile, it says last login 7 months ago and there are no recent submissions...

Could it be a case that both accounts are somehow mapped together because of a bug? Please help me because I dont want to be penalised for something which is not my fault!

»
3 months ago, # |
  Vote: I like it -66 Vote: I do not like it

Coronavirus. Please help!. It helps in the containment of the Coronavirus.

»
3 months ago, # |
  Vote: I like it +42 Vote: I do not like it

Does anyone know what is going on with the system tests for this contest?

»
3 months ago, # |
  Vote: I like it +11 Vote: I do not like it

Very random order of system testing. Never seen something like this happen before.

»
3 months ago, # |
  Vote: I like it +41 Vote: I do not like it

Why did systest halted?

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

Is the order of system testing decided beforehand or is the server going berserk on its own.

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

    On my hours of waiting for system testing, i realized that the host has 20 cores, the algorithm it use is as follow:

    1. push all the submissions to the queue, in ascending order of time submitted/judged on pretests.

    2. add first 100 submissions in the queue, or all the remaining submissions if they are less than 100.

    3. judge them 20 by 20(or sometimes 1 by 1, it changed during the HOWFST(Hours Of Waiting For System Testing :P, its really close to "HOWFAST" but not the same).

    4. do things with newly judged submissions(for example update number of accepts for the problem, update standings and . . ., some of them were done in the time of judging, not sure about the exact algorithm as it changed a lot in the HOWFST)

    5. go back to line#1 if the queue is not empty, or go to line#5 otherwise.

    6. update everything.

    Probable the real algorithm is different, i did my best sorry if i let you down :)

    Note:

    Difference between 20 by 20 and 1 by 1 is that, the cores wait for each other to finish the judgement then they all go forward together in "20 by 20", but in "1 by 1" every core goes to the next submission which is not running or judged after it finished the judgement.

    P.S. I wrote 0 -> 1 -> . . 5 in the algorithm's lines, and the cf remade them using 1 -> 2 -> 3 . . 6, i didn't know cf is that much HI-TECH :D.

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

      You may say iam wrong with judging order, its more likely that they first started in a random order, then decided to make it more beautiful, then they sorted all the solutions in ascending order of time submitted/judged on pretests.

»
3 months ago, # |
  Vote: I like it +131 Vote: I do not like it

very slow system tests...

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

    Smh Internet Explorer is faster.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    xD at least internet explorer doesn't go back in time like what has happened in the last division 3 contest!

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

I wish system test will have completed before I will go to sleep.

»
3 months ago, # |
  Vote: I like it +31 Vote: I do not like it

Waiting for System testing!!

»
3 months ago, # |
  Vote: I like it -77 Vote: I do not like it

Thanks for antihash test!!!!!!!!!!!!!!!!!!!

It is really cool to make people writing 2 or more moduls!!!!!!!!!! It is really ideaful move!!!!!!

Thanks!!!!!!

»
3 months ago, # |
  Vote: I like it +88 Vote: I do not like it

Please codeforces make a gift to the people that donated money and upgrade the hardware. Codeforces it’s a great platform but people have to wait hours for system testing to complete every time when there is a contest.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Fast Editorial !!!

»
3 months ago, # |
  Vote: I like it +8 Vote: I do not like it

I guess this is a lesson to me to never write an algorithm with a $$$0.2\%$$$ chance of failing per test case when there's no full feedback... 73689147 73740657

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

    you don't realize it

    //this is such a bruh moment
    

    is an Overpowerful comment. Overrules the judge's verdict.

»
3 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Hey did anyone get this message wrong answer jury found longer string, jans = 12 > pans = 2. I got it as the message for a wrong solution to D.Can anyone tell what it means? My submission link if it may help https://codeforces.com/contest/1326/submission/73733467

»
3 months ago, # |
  Vote: I like it -13 Vote: I do not like it

I received a message saying that my code matched with the other two: rmodi9942,Black_Level. I checked on ideone and saw that my settings were public and they have copied the code. In order to prove it you can 1. check my submissions for C,B and A , the submission for D1 has the same template as that of A,B and C and theirs is different. In fact all my submissions for the past 1 month have the same template. 2. Both of them have ratings under 1000 and are newbie and hence the probability of them copying my code is high. I'm really sorry that i forgot to make ideone settings as private, and will surely change it to private.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    Infact i found another proof :

    1. rmodi9942 has copied in the previous contest also. I just checked his profile and his submissions for previous contest Codeforces Round #628 (Div. 2) has been skipped.
    2. Black_Level has also copied solution for the previous contest as can be seen on his profile the contest in which he copied is Codeforces Round #601 (Div. 2).

    Infact you should ban both of their accounts, since in their contest/submission history most of their solutions are skipped. Please give me my ratings back, you can see my profile is clean and it was only in this contest that i became their victim.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Today, I learned a harsh truth (sadly, after contest) that string concatenations aren't constant time even for single character concatenations. See the two submissions below:

https://codeforces.com/contest/1326/submission/73726135 (TLE) https://codeforces.com/contest/1326/submission/73741382 (AC)

The only difference is that I've replaced all concatenations (inside the for loops, don't ask me why I chose to do it in the first place) with their equivalent substr counterparts. If there're more things in this context that might be helpful knowing, please share. Thanks.

  • »
    »
    3 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Well in your TLE code you can just replace pref = pref + s[i] with pref += s[i], and this is constant time. After that, suf is just the reverse of pref. No need to change to substr if you didn't want to.

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks, can you tell me why are these two assignments treated this differently?

      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Well if you do a = a + b then you are creating a new string a + b and then assign back to a, so the time complexity for that is $$$O(\text{a.size() + b.size()})$$$. In the case a += b, you just extend a b.size() more characters, so the time complexity is $$$O(\text{b.size()})$$$.

»
3 months ago, # |
  Vote: I like it +76 Vote: I do not like it

Hi! Thanks for participation. This round broke all records for popularity: 18180 registrations and over 2.5M pageviews! Taking into account a large number of tests in easy problems, system testing turned out to be too long. I apologize for it.

I'm glad to announce the winners of the t-shirts! They are:

List place Contest Rank Name
1 1326 1 tourist
2 1326 2 Um_nik
3 1326 3 boboniu
4 1326 4 jiangly
5 1326 5 cuizhuyefei
6 1326 6 TLE
7 1326 7 WZYYN
8 1326 8 PavelKunyavskiy
9 1326 9 kefaa2
10 1326 10 Benq
11 1326 11 apiadu
12 1326 12 Swistakk
13 1326 13 RomaWhite
14 1326 14 aid
15 1326 15 Radewoosh
16 1326 16 ecnerwala
17 1326 17 ko_osaga
18 1326 18 DCXDCX
19 1326 19 yosupo
20 1326 20 amnesiac_dusk
21 1326 21 djq_fpc
22 1326 22 .I.
23 1326 23 Egor.Lifar
24 1326 24 Maksim1744
25 1326 25 FizzyDavid
26 1326 26 I_love_chickpea
27 1326 27 kraborak
28 1326 28 Golovanov399
29 1326 29 cookiedoth
30 1326 30 duality
53 1326 53 kobae964
76 1326 76 Maripium
95 1326 95 Celesta
97 1326 97 vasilescu_mihai
127 1326 127 Toxel
137 1326 137 jo_ulej
138 1326 138 Atreus
146 1326 146 Temotoloraia
174 1326 174 JaeminPark
232 1326 232 Kloze
273 1326 273 Ari
281 1326 281 ngtkana
292 1326 292 hyjtxdy
300 1326 300 BZZB
303 1326 303 gyz_gyz
312 1326 312 ddytxdy
396 1326 396 aropan
469 1326 469 uruuru8888
486 1326 484 Java
499 1326 499 Sahaand
  • »
    »
    3 months ago, # ^ |
      Vote: I like it -15 Vote: I do not like it

    Java orz

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

    How are the random t-shirts determined (random numbers between [31,500])? I also happened to get 281th place.

    • »
      »
      »
      3 months ago, # ^ |
      Rev. 2   Vote: I like it -19 Vote: I do not like it

      My calculation says that yes, let me say what ive dont, first for every two continues winners, $$$sum += (a_{i+1} - a_i) ^ 2$$$, the array $$$a$$$ is the ranks of the winners with higher rank than 30 in increasing order, then lets find the smallest sum we can get when choosing $$$a_i$$$s, then the displacement of the array $$$a$$$ will be $$$ds(a) = sum(a) - sum_{mn}$$$, $$$sum(a)$$$ returns the defined value $$$sum$$$ for an array, and $$$sum_mn$$$ is the lowest $$$sum$$$ we can get from any valid array $$$a$$$. You will see that choosing a random array $$$a$$$ should give us a quite low $$$ds(a)$$$, for example less than $$$n$$$, and the results of a good randomized array should give $$$sqrt(n) < ds(a) < n$$$, in my opinion. So the winners are well randomized so far. It's really my opinion and i really thought about it.

      P.S. I hope you liked my calculations :).

      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I can't tell if you're trolling or not.

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

          I am not, its just my opinion about how an array is well-randomized.

      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Oky i should say it was just a random idea about how to check an array is well-randomized or not, but in fact it was all done for nothing, as every valid array have the same probability =(.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Offtopic question, but do you get a penalty if you get WA on the first pretest? also, do you get a penalty if you get WA on the Tests included in the statement?

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You wont get penalty for WA on the first test/pretest in normal cf rounds, educational rounds and global rounds and . . ., but iam not sure about the rest, i bet on "no they dont have penalty".

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks a lot!
      I think you do get penalty, my latest contest i had 6 WA on the second and third pretest(part of the statement) and i think my score is way off because of it.

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

Sorry to bother, but why my O(n) solution got TLE in the system test but got AC just now when I submitted exactly the same code? Could somebody please tell me the reason? Thx a lot. 73666334 73748630

  • »
    »
    3 months ago, # ^ |
    Rev. 2   Vote: I like it -7 Vote: I do not like it

    Are you kidding yea? problems differ.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can see that your AC solution us barely passed the tests. If you are using c++ with cin/cout then you should check this out. IO actually requires a lot of times.

»
3 months ago, # |
  Vote: I like it +1 Vote: I do not like it

E is cool. A is too hard.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

After I read the Problem A, my mind is full of 3 and 8. But I thought that to verify 338 and 38 are not divisible by 8 is more troublesome than to verify 34 is not divisible by 4. And finally I chose 3 and 4.

»
3 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Can anyone give me any case for which my solution of D2 get WA?

I got verdict WA on test case 3.

My Submission: https://codeforces.com/contest/1326/submission/73732348

»
3 months ago, # |
  Vote: I like it +9 Vote: I do not like it

I have solved two problems for the fist time in a contest!! :D

»
3 months ago, # |
Rev. 3   Vote: I like it -21 Vote: I do not like it

https://www.youtube.com/playlist?list=PLl4Y2XuUavmsf8Os2QTsRgi6Gn5M1dWO8

Will be uploading solution videos of problems A — D2 on this link.

(I don't understand the reason behind so much hate (-25). A to C have been uploaded, D1 & D2 will be uploaded soon)

UPD: Solution videos of D1/D2 and E have been uploaded

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I screwed in D2 trying to insert in a StringBuilder. Remember java users insert has a time complexity of O(n). Its better to append and then reverse the operations.

»
2 months ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

The below code is getting TLE for D2, may anyone help me to know why?

include <stdio.h>

include <string.h>

include <math.h>

define MAX 500005

char text[MAX]; int min(int a, int b) { int res = a; if(b < a) res = b; return res; }

int findLongestPalindromicString() { int N = strlen(text); if(N == 0) return -1; N = 2*N + 1; //Position count int L[N]; //LPS Length Array L[0] = 0; L[1] = 1; int C = 1; //centerPosition int R = 2; //centerRightPosition int i = 0; //currentRightPosition int iMirror; //currentLeftPosition int maxLPSLength = 0; int maxLPSCenterPosition = 0; int start = -1; int end = -1; int diff = -1;

//Uncomment it to print LPS Length array
//printf("%d %d ", L[0], L[1]);
for (i = 2; i < N; i++)
{
    //get currentLeftPosition iMirror for currentRightPosition i
    iMirror  = 2*C-i;
    L[i] = 0;
    diff = R - i;
    //If currentRightPosition i is within centerRightPosition R
    if(diff > 0)
        L[i] = min(L[iMirror], diff);

    //Attempt to expand palindrome centered at currentRightPosition i
    //Here for odd positions, we compare characters and
    //if match then increment LPS Length by ONE
    //If even position, we just increment LPS by ONE without
    //any character comparison
    while ( ((i + L[i]) < N && (i - L[i]) > 0) &&
        ( ((i + L[i] + 1) % 2 == 0) ||
        (text[(i + L[i] + 1)/2] == text[(i - L[i] - 1)/2] )))
    {
        L[i]++;
    }

    if(L[i] > maxLPSLength)  // Track maxLPSLength
    {
        maxLPSLength = L[i];
        maxLPSCenterPosition = i;
    }

    //If palindrome centered at currentRightPosition i
    //expand beyond centerRightPosition R,
    //adjust centerPosition C based on expanded palindrome.
    if (i + L[i] > R)
    {
        C = i;
        R = i + L[i];
    }
    //Uncomment it to print LPS Length array
    //printf("%d ", L[i]);
}

int idx = 0, len = 0;
for(int i = 0; i < N; i++) {
    if(i - L[i] == 0) {
        len = L[i];
    }
}

return len;

}

int main() { int t; scanf("%d", &t);

while(t--) {
    char S[MAX];
    scanf("%s", S);

    int len = strlen(S);
    int l = 0, r = len - 1;

    while(l <= r) {
        if(S[l] != S[r]) break;
        ++l, --r;
    }

    if(l > r) printf("%s\n", S);
    else {
        for(int i = 0; i < l; ++i) printf("%c", S[i]);
        int top = 0;
        for(int i = l; i <= r; ++i) {
            text[top++] = S[i];
        }
        text[top] = '\0';

        int midLen = findLongestPalindromicString();
        int top1 = 0;
        for(int i = r; i >= l; --i) {
            text[top1++] = S[i];
        }
        text[top1] = '\0';

        int revLen = findLongestPalindromicString();
        if(midLen > revLen) {
            for(int i = l; i < l+midLen; ++i) {
                printf("%c", S[i]);
            }
        }
        else {

            for(int i = r-revLen+1; i <= r; ++i) {
                printf("%c", S[i]);
            }
        }

        for(int i = r+1; i < len; i++) printf("%c", S[i]);
        printf("\n");
    }
}

}

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

why current solutions are stuck in queue for an hour