300iq's blog

By 300iq, 4 years 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, Howadji, 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

| Write comment?
»
4 years ago, # |
  Vote: I like it -13 Vote: I do not like it

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

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

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

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

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

        Hope is a good thing.

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

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

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

  • »
    »
    4 years 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 ❤️

  • »
    »
    4 years 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$$$

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

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

    We are really sorry for the delay. :(

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

    I guess you'll need smaller size now :D

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

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

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

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

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

    Div1 + Div2 , it's rated for everyone.

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

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

      Why you won't get anything?

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

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

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

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

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

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

Hope you have a good year.

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

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

    Extremely.

  • »
    »
    4 years 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]

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

      [Deleted]

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

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

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

I hope this round will have strong pretests. :)

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

No thanks to Mike. I am very afraid.

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

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

Ivan and Ildar are trusted authors :sunglasses:

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

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

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

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

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

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

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

Hope that I can solve ABC ❤️

Good luck guys ❤️

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

May I know who is the coordinator? :P

»
4 years ago, # |
  Vote: I like it -13 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it +13 Vote: I do not like it
»
4 years 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?

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

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

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

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

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

I will get 0 points :(

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

High ratings everyone :)

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

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

Hi! The codeforces app here .

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

.

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

are we going to see a dp problem after all?

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

How long is it gonna be?

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

With how many problems?

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

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

»
4 years 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..♥♥

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

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

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

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

.

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

Best of luck to everyone!

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

Expert will belong to me again after this round haahahahahahaahaaaaaaaaaaaaaaaa

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

Score distribution??

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

Effect of Corona Virus situation. 17500+ registration.

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

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

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

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

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

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

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

»
4 years ago, # |
  Vote: I like it -12 Vote: I do not like it

Such Long Queues !!

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

God bless adamant !

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

Subtasks === poor problemset

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

Me when I read problem F:

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

![ ]()

C, WA on pretest 5.

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

    same i also got Wa

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

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

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

      Almost 2000 lines of templates, lol =))

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

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

      orz

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

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

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

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

»
4 years ago, # |
  Vote: I like it -12 Vote: I do not like it

Queue,Speed,Think,String and Math FORCES.

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

How to solve C and D ?

  • »
    »
    4 years 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..
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve E?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Is it possible to solve D with hashing?

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

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

      This is exactly what I did but got WA-2, I used double rolling hash

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

      Is hashing still a safe approach to D? I saw a lot of hashing based solutions that are failing system testing.

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

»
4 years ago, # |
  Vote: I like it -59 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it -56 Vote: I do not like it

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

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

»
4 years ago, # |
  Vote: I like it -15 Vote: I do not like it

Welcome to a permutation contest ...

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

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

    ;_;

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

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

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

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

»
4 years 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 ?.

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

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

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

Anyone used EERTREE + binary jump on D? XD

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

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

    2222222237 / 7 = 317 460 319,571429

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

»
4 years 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]

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

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

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

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

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

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

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

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

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

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

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

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

Why did systest halted?

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

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

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

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

very slow system tests...

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

    Smh Internet Explorer is faster.

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

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

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

Waiting for System testing!!

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

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

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

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

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

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

    Well, your task was to find the longest string that satisfied the conditions in the question. Since the intended answer is a string longer that the one you output, it showed a wrong answer

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

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

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

      • »
        »
        »
        »
        4 years 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()})$$$.

»
4 years 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 244mhq
10 1326 10 Benq
11 1326 11 sunset
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 tribute_to_Ukraine_2022
27 1326 27 craborac
28 1326 28 Golovanov399
29 1326 29 cookiedoth
30 1326 30 duality
53 1326 53 kobae964
76 1326 76 JettyOller
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 minato
486 1326 484 Java
499 1326 499 Xahandd
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -15 Vote: I do not like it

    Java orz

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

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

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

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

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

      • »
        »
        »
        »
        4 years 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 =(.

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

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

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

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

    Are you kidding yea? problems differ.

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

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

E is cool. A is too hard.

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

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

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

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

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

»
4 years 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");
    }
}

}

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

why current solutions are stuck in queue for an hour