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

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

Hello Codeforces!

I would like to invite you to Manthan, Codefest'19, which will take place on Sunday, August 25, 2019 at 8:05 PM IST. This is a combined Div. 1 + Div. 2 round and is rated for participants from both divisions.

The Department of Computer Science and Engineering, IIT (BHU) is conducting Codefest from 23rd August — 25th August. Manthan, the algorithmic programming contest under the banner of Codefest, is being held as a special Codeforces round. The round follows regular Codeforces rules.

All problems in this round were created and prepared by drastogi21, _shanky, Enigma27, _hiccup, KAN and me (hitman623).

A lot of thanks to KAN, 300iq, vintage_Vlad_Makeev, _overrated_, Rox for the testing and valuable comments, and to MikeMirzayanov for the awesome Codeforces and Polygon platforms!

Prizes -

  • 1st place — INR 25,000

  • 2nd place — INR 18,000

  • 3rd place — INR 12,000

  • 1st place in India — INR 6,000

  • 1st place in IIT(BHU) — INR 3,000

  • 1st place among freshers (1st/2nd Year) of IIT(BHU) — INR 1,000

  • Codeforces T-shirts to the participants who will be the first to solve each problem.

Participants will be offered 8 problems and 2 hours to solve them. As usual, the scoring distribution will be announced later.

Hope you guys enjoy the contest! See you on the leaderboard!

UPD: The scoring is 500 — 1000 — 1500 — 2000 — 2250 — 2500 — 3000 — 3750

UPD: The contest has ended. Congratulations to the winners.

1. tourist

2. Um_nik

3. jqdai0815

First place in India: cerberus97

Following are the participants who were the first to solve each problem and have won a Codeforces T-shirt. Congrats!

A. IgorI

B. Geothermal

C. icecuber

D. ILoLy

E. nocriz

F. GoGooLi

G. jqdai0815

H. tourist

UPD: We decided to give the 8th T-shirt to IgorI for problem A. Congrats!

The editorial has been published.

Hope to see you next year!

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

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

Finally some Indian Contest ..waited for it ..hoping for great problems.. last one was great

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

Waited for the whole year! Hope the legacy of greatness continues!

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

Probably tourist will win the prize for 1st place ...

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

The Legends battle are coming

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

Hope that I'll become a candidate master after this round! Div.1 + Div.2 is a great chance to promote my rating and I only need +8 rating to become a candidate master :D. And also, good luck to everyone!

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

"Codeforces T-shirts to the participants who will be the first to solve each problem.", well, this gonna be interesting

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

    Yes,it will.And I think it doesn't matter if you do a great job or win a T-shirt or not,I think the
    feeling during the contest is the most exciting thing! And good luck to all of you!

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

Wow, an awesome contest ^_^

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

1st place is constant for tomorrow's contest if he participates.

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

8 problems, 4 for div 2, 4 for div 1 or another?

Sorry for my bad english

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

I'm disappointed they scraped my e-mail from my profile and decided to send me spam.

It is an old e-mail, meaning that they did it some time ago and not just now near this contest, and I've never registered in their site.

The closest I got was participating in Codefest '18, here in Codeforces, but at that time, I used a different e-mail (a third one).

PS.: And even if they did it at that time (they didn't), nowhere it says they would send e-mails to registered participants.

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

Manthan, Codefest 18 (rated, Div. 1 + Div. 2) The Previous Manthan codefest contest .

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

8 problems for 2 hours?? Isn't that too tight?

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

    It's combined round (Div. 1 + Div. 2), the high rated coders will be bored if they solved all the problems quickly. you can see that tourist solved all the 8 problems of Good Bye 2018 in less than 2 hours, also few contestants solved all the 8 problems of last year Manthan, Codefest 18 in less than 2 hours.

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

I hope that I will raise my rating to 1500-1600

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

Wow.... Such a big prize

$$$出题人家里有矿_{泉水}$$$

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

Any update on scoring distribution?

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

I relize that lots of people use anime avatar like me ^______________^

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

None of the other severs (m1.codeforces.com), (m2.codeforces.com), (m3.codeforces.com) seem to have the contest added in there?!

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

Have been participating regularly for the past 2 editions of this contest and had lots of fun.
Hope everyone has fun this time too :)

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

not able to register before 5 minutes of contest... why??

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

can someone submit? it keeps loading

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

It's legendary grandmaster battle. I can't wait to see that. All top 3 highest CF rating have already register, who will win???

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

R.I.P queue

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

VERY long queue

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

What was the pattern for 1208C - Magic Grid?

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

    Use subsquares 4x4 of numbers 0-15 MOD 16 like (0, 1, 2, 3), (4, 5, 6, 7), (8, 9, 10, 11), (12, 13, 14, 15) — it has zero XORs and prefixes are repeated 4 times, thus their XOR is also 0.

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

      Very nice solution bro, I also thought about that thing, I saw with n=4 and n=8 we can easily solve the problem, just write sequence 0..(n^2-1) from left to right and from top to bottom, but then I couldnt figure out how to use them for another multiple of 4 numbers and your solution helps me a lot. Thanks again!!!

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

    0 1 2 3__________16 17 18 19

    4 5 6 7__________20 21 22 23

    8 9 10 11________24 25 26 27

    12 13 14 15______28 29 30 31


    32 33 34 35_____48 49 50 51

    36 37 38 39_____52 53 54 55

    40 41 42 43_____56 57 58 59

    44 45 46 47_____60 61 62 63

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

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

      Why not doing it in a nice order?

       0  1  2  3
       4  5  6  7
       8  9 10 11
      12 13 14 15
      
    • »
      »
      »
      5 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Everyone is giving example of 8x8, how to extend this to 12x12?

      Edit: To extend, order doesnt matter, just place those new 4x4 matrices anywhere. All will be 0. Good god.

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

B question was good. Took more than 1 and half hour to understand it what's it trying to say and implement it.

Thanks for this contest IIT BHU :) . Cheers!

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

    It also took me 1 and a half hour. I am not even sure whether it is correct or not. Let's see the system testing results.

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

How to solve C, it seems much harder than D and E

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

    Fill that array in increments of 4 like 0 4 8 12 1 5 9 13 2 6 10 14 3 7 11 15

    This way xor will always be zero of all rows and columns.

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

      not necessarily zero. When n%8 equals 0 then it will be zero else it will be 13.

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

    Some one here said that B was harder than C. And you say that C is harder than D and E. It took me more than one and a half hours to get the B pretests correct. I am thinking whether I should I have skipped B.

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

tourist achieved top 1 is really very normal =))

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

How to solve C?

I feel D was easier than C :(((

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

    Oh dear, I got bug at D.

    Dunno whether my C is correct. Btw I use the fact that I can construct a grid for numbers 0->15, then I could construct numbers for 16k->16k+15

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

    U can find a pattern that if you break the given nxn matrix into 4x4 matrices with increasing values (For ex: 0 to 15, 16 to 31 etc) , you can make all the rows and columns have xor sum = 0.
    Find my submission here :)

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

      nice trick, thanks

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

        Could you please share your idea for D? :)

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

          Mine is Nlog^2(N)

          basically binary search + segment tree

          I start filling the answer array in reverse order, Binary search on all feasible values to check the following condition

          if array[mid]+query(0,mid-1) == mid(mid-1)/2, then mid is at current position
          
          else array[mid]+query(0,mid-1) >= mid(mid-1)/2, then lo=mid+1
          
          else hi=mid-1
          

          I used pbds for convenience. thats not needed.

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

      How did you find this pattern ?

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

        They had emphasized that n is a multiple of 4. So I wrote down the binary representation of 0 to 3 ( i.e first 4 numbers, and realized their xor was 0).
        That was the beginning of the idea, and developed the pattern.

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

    This is my approach:

    Divide the whole matrix into 4 * 4 matrices. Then fill every matrix with slight modification of a valid answer for a 4 * 4 matrix. I used the result of test case 1 of the problem statement. Keep a variable that tells us the number of matrices that has been processed. Left shift counter variable by 4 and then perform bitwise OR operation with the corresponding number of the initial matrix while assigning.

    Will it be correct? Yes, because the XOR of each row and column of every 4 * 4 matrix will be the same. So, if you use test case 1, then the XOR of each row and column of the whole matrix will be 13 or 0.

    Will any number repeat? No, because we are using counter variable. Every number has 4 initial bits with 2 ^ 4 possible combinations. These are covered by the initial matrix. We just need to cover the extra bits. The counter gives us new combinations of the extra bits, starting from the lowest. By performing bitwise OR, we are reaching each bitwise combination. So, we will hit each number once.

    My submission can be found here.

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

How to solve D ?

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

    I did it with a lazy segment tree, but there seems to be a way to do it with just a regular segtree/fenwick tree. In the sequence you get, the last 0 is always the 1 in the original. If you imagine that you remove the 1 you found and subtract 1 from every item after that you would get a similar sequence for 2..N. Then you find the last zero again, which now is the 2 and you subtract 2 from everything after etc. You use a lazy min segment tree to find the last zero (order by value and index) and to do the range subtractions.

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

      I thought of this idea last 5 mins before contest end, indeed can't implement it.
      Thank you anyway :)

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

        Pretty much the same. Thought of it 15 mins before, but min segment tree + lazy, gave up there itself >.<

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

          I also got the solution quite late, but I copy pasted the segment tree from kactl. It's a really nice repo with lots of standard CP things.

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

most of the WA10 because of something like this :

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

What is test #5 of D?

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

I was able to solve C but couldn't solve B. :( Was B more tough than it is supposed to be??

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

Thanks for the short statements

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

I must be crazy. I think the problem should be like ABEDCFGH...

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

Is there any way to solve D without converting it into a Segment tree RMQ problem? I saw the number of submissions and thought I probably need to think simpler.

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

When in the last 20 minutes of the contest you start doing problem D but in the last 9 seconds you submit it without any tests, because you just finished coding it, and you misstyped a -=, instead of typing +=. I've neve felt this bad before ;(

PS: Submission during the contest: https://codeforces.me/contest/1208/submission/59484539

Submission after the contest, after changing the signal: https://codeforces.me/contest/1208/submission/59486030

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

hard contest for me but I enjoy it very much. Thanks :)

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

How to solve E in time? I had a made a sparse table solution and then just iterated over all of the columns but I couldn't figure out the final optimization. At the end I tried to use a lazy seg tree to propogate the maximum over all columns where the the array can take all of it's values. Is this the right approach?

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

B and D are not good problems. C is nice

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

I love how tourist was able to get 500 on A (submision time 52s) :-)

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

    Keep up to date (hipozhor)

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

    3 miniutes for D and 2 minutes for C is unbelieveable

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

    Guys, I know what happened. tourist obviously cheated. See for yourself:

    How can he start coding at 17:33:16 if the contest started at 17:35:00? I knew something wasn't right about him, but now he gave himself away!

    I would disqualify everybody whose handle starts with t as a warning.

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

      majk Come on. It can be possible that he might have created pre template file for A problem before the contest. We all do a little preparation.

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

        How would he know there's a problem A? You're only making this worse.

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

The best utilization of last ( extra ) five minutes : tourist submitting H at 2:03

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

Can someone give a quick editorial of B.

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

    You can delete either:

    1. some prefix
    2. some suffix
    3. something in the middle

    You will be left with (respectively):

    1. some suffix
    2. some prefix
    3. some prefix + some suffix

    Basically, (1) and (2) are the same as (3) if you assume that there is an empty prefix/suffix.

    So, what you can try to do is for each prefix (empty, too) find the largest suffix satisfying the conditions -- what is left between them is exactly what you delete, take the minimum of all such gaps.

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

    The simplest way, according to the given constraints would be to add each element in the array to a set. Then for every index i starting from 0, we traverse j left to right from i, generating every subarray starting at i, and trying to remove each element from the set and check if size of the set at any point is N- (j-i+1). We stop the first time it happens and we've found the smallest subarray starting at i. Then we increment i again, but before doing that make sure you add back the i'th element to the set. It will be O(N^2 lgN) There's also an O(N) solution by the way, that I used.

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

    you can try two pointers to solve that...i am not sure,but I have passed the pretest

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

Okay, why lot of system test fail on B?

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

I solved C with something really easy: I print all even numbers first then I print what is left. For example for n=4 my output will be :

0 2 4 6 
8 10 12 14 
1 3 5 7 
9 11 13 15
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Incredible.

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

    Definitely the best solution here :D.

    It is also easy to prove that it is correct — lines have XOR of 0 trivially (split them by 4) and every consecutive even-odd pair in each column have XOR of 1. There is even number of such pairs, so the total XOR is also 0.

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

so sad I thought C xor will be zero because it looked impossible to guess some number but didn't know how :'(

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

At least 3 persons on my friend list who got F accepted fail this test:

3
2 4 2

Please look into this.

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

    I got uphacked (59479538) by

    3
    0 0 1
    

    Because I looped the number to or with up to the last number, instead of to the third-to-last. The tests were definitely pretty weak :P

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

why codeforces don't compare codes like this 59482093 and this 59481769

tihs is not fare

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

Can we solve B using Binary Search?

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

    Yes. I solved it using binary search. Code Search space is the answer range i.e. [0,n]. isValid function checks if it's possible to delete 'mid' number of values such that rest of them are distinct. I used map to store the values and their frequencies in the 'undeleted' array. If the size of map is n-mid for some undeleted part, it means that all the undeleted elements are distinct.

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

    I think you can.If deleting a large portion from a given position gives you a valid sequence then you can check for even smaller portion.

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

What id test 54 for B ?

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

Guys, I've found a really nice solution for C.

The Ideea is this: Put even numbers in increasing order on odd rows and odd numbers on even rows.

Ex: n=4 0 2 4 6 1 3 5 7 8 10 12 14 9 11 13 15 This is 100% correct and much easyer to implement. :)

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

How to solve F?

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

    Could anyone explain why this solution 59478005 for F works?

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

    My solution: We want to be able to fix a_i and compute the best (a_j&a_k) for that a_i quickly. To do so, we iterate through i from large to small, and maintain an array cnt[bit] which stores the number of elements among $$$a_{i+1}, a_{i+2}, ..., a_{n}$$$ that have bit as a submask. How to we update cnt? Note that we only need to know if cnt is >= 2 or not. Now, when we have a new element $$$x$$$ to be added, we do something like a dfs, starting by adding 1 to $$$cnt[x]$$$, and then recursing on all submasks of $$$x$$$ that are one bit away from $$$x$$$. If at any point of time we visited the same number or cnt[x]>=2, we can terminate because we know all submasks must also have cnt>=2. Thus, the complexity of updating cnt is amortized $$$O(n\log a_i)$$$. Finally, with the values of cnt you can also find the best answer for a fixed $$$i$$$ in $$$O(\log a_i)$$$ time.

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

can you tell, where my code for B fails?

My Solution

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

    Check this test case: 8 1 2 3 4 1 6 5 4 The correct answer is 2.But your code gives 4 as the output. I guess most of the solutions got failed at system testing in these type of test cases.My solution got failed too.

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

      Thanks, got your point.

      I think we went wrong in trying to implement B in o(n).

      Constraints are the real insights to the problems.

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

    Try this one:

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

Why does solution for B in $$$n^2 \log^n$$$ give TLE? I used both binary search and sets (I know it's not the most efficient), and couldn't get it accepted. TLE on test 18. Can anyone help?

$$$n^2\log^2n$$$ is roughly 43587196 ops at n=2000 which should work in under 2secs imo.

Submission

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

    You might have a miscalculation.

    4million*log*log is around 400 million, which might not pass because of set constant.

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

    You took the log to the base 10. Base 2 would be more realistic and then it's already $$$5*10^8$$$, also set::insert probably has some additional constant factors.

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

Can someone please point out the logic flaw in my solution for problem B?
PS: Found my mistake. Thanks everyone.

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

Можно ли как-то полностью посмотреть 85 тест в задаче B, так как на нем программа выдает неверный ответ?

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

    Контртест к твоему решению: 6 3 3 1 4 3 3 Твоё решение дает ответ 3, правильный — 5

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

I didn't leak code to anyone but I receive system's message :'(. May be this is an accident

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

My Solution for B, fails on test 54 but I don't know why? Someone please help! LinkL: https://codeforces.me/contest/1208/submission/59459333

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

So tourist doesn't get two T-shirts? :sad:

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

It is totally unfair to me . I have solved the second problem completely with required time complexity even than your website is showing TLE . Why? Do something otherwise it is totally waste of time for me to participate in challenges on your website

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

    Maps are not constant complexity. Expected complexity was O(n²log(n)), not O(n²log(n)log(n))

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

    The CF judge is fair to everyone. It's just because your solution is too slow. Having a solution of intended time complexity does not necessarily mean it must pass.

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

    No one cares if you participate or not. This platform is for everyone to learn and improve. If you have done a mistake try to accept it and learn from it, instead of complaining.

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

I was able to pass pretests with my too complicated solution for G, but I got TLE on one of the pretests during system testing. Moreover, after the contest I submitted the same code 10 times, 9 of those 10 attempts got AC. Maybe solutions should not be rerun on pretests during final testing, to prevent such disappointing situations in the future xD

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

1179 contestants solved segment tree problem. It seems like CF is "growing up" or I am "growing down".

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

    I solved B in more than 13 minutes and solved D in less than 10 minutes.

    I think I need more "IQ"...

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

    I can't solve C because I'm not good at constructive problems. I think I should practise it more.

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

tourist returned to 3700+ in 31 months.

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

Can someone tell why my code 59471606 of B problem gave wrong answer on pretest 9? It gives same output as jury's output when I run it in my system.

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

How to solve D,I don't understand the editorial ?

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

    If the input is valid, as the problem statements says, there is always an answer and it will be unique.

    Let's build from the last element in the array to the first one. Also create a data structure that can query the sum of all values in range[0, r] and update a point in log.

    Whenever you try to put some number into the answer, it will have sum of all the other unused numbers, because they will be somewhere before it in the answer. Initially, all numbers are available. So you can do N updates like: update(i, +i).

    As you know the sum of all numbers before it in the array, just binary search what element have exactly the same sum as the input, then remove it from the answer like: update(i, -i).

    Suppose that you initially have 1, 2, 3, 4, 5. So, your data structure will be: 1, 3, 6, 10, 15.

    If you want to put an element with sum 6, you should put element 4 as the last one, then your data structure will look like this: 1, 3, 6, 6, 11.

    Keep doing this and you will end up with the answer.

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

      It seems a same approach with mine (and different with the editorial).

      However, I don't know how to deal with such condition:

      n=5, the sequence is 0 4 0 1 1

      0 1 3 6 10

      (the last one is 2)

      0 1 1 4 8

      (the last one is 3)

      0 1 1 1 5

      Now, there are three 1 can be chosen (in fact, the third 1 is correct), and how can my program deal with such condition in appropriate complexity.

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

        You should always try to find the last one element that have the same sum. If the data structure is like ... 0 1 1 1 1 2 ... And you are searching for 1, just get the last 1.

        If you put another value except from the last, you can't build the answer.

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

          Thx! I do exactly the same thing as you say and got WA on 9. However, it turned out to be that it is "long long" which made me get WA. QAQ

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

            You can also improve your answer by removing the binary search, just traversing the segment tree.

            If you are in a vertex searching for something with sum x, then:

            • if left node have sum >= x, then call left vertex with x

            • otherwise call right vertex with x - left_sum

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

How is it possible to solve A in 52 secs if statement loads for half a minute xD?

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

Tourist is such a monster!

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

I think we should swap problem C and problem D.....

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

I tried to solve the second question using binary search on the length of segment to be removed. The pretests passed but I got TLE in the final testing.

http://codeforces.me/contest/1208/submission/59462841

Can someone tell me what went wrong ?

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

why I dont see the prize for first solve of problem H in the list above while there is someone has solved this in the contest, can anyone explain this for me?

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

How to solve G? It seems like a math problem about divisors, and the AC code looks very simple. However, I did not understand the behind logic yet. Anyone can help?

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

Can someone help me with the code for B problem? Here is my code:

#include <bits/stdc++.h>
#define ll long long int

ll n,m;
ll a[4004];
// set<int>s;
map<int,int>mp;
int last[4004];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        a[n+i] = a[i];
    }
    for(int i=1;i<=2*n;i++)
    {
        last[i] = mp[a[i]];
        mp[a[i]] = i;
        // cout<<last[i]<<" ";
    }
    // cout<<endl;
    int ans = 0;
    for(int i=1;i<=n;i++)
    {
        int cnt = 0;
        for(int j=0;j<n;j++)
        {
             if(last[i+j]<i)
             {
                cnt++;
                ans = max(ans,cnt);
             }       
             else{
                break;
             }
        }
    }
    cout<<n-ans<<endl;
    return 0;   

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

Can Any one explain Problem D ??

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

Request for future contests :: Please make large inputs downloadable

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

If you've solved problem D. And want to solve another interesting problem like this. Try Lightoj — Lining Up Students In Lightoj one need a account in case of view a problem. In case you don't have an account there you can read the problem here

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

asd

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

hello my fan

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

Codeforces is too easy to me

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

Can I get some help to solve B...This was my code https://codeforces.me/contest/1208/submission/59474361 ...Why am I getting TLE...As much as I can see, the solution will execute 6.4*10^7 instructions at max

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

    Operations on unordered_map are often more than 1 instruction, and the $$$O(n^{2}logn * map)$$$ will probably have a bad constant and run for longer than expected.

    Some improvements:

    The actual elements in the array don't matter, only that they're unique. Therefore, you can compress coordinates and use a boolean array (or bitset, if you really want) instead of a map. This alone should get you under TL.

    The binary search doesn't actually help you. Since the check function is $$$O(n)$$$ anyway, you may as well get rid of the $$$logn$$$ factor by just finding the first location, iterating from the right to r, that creates a duplicate (of course, include the elements to the left of l first and account for duplicates there)

    And because three is a good number, even though this isn't necessary, your loop in check skips over a lot of elements. Each continue can cost you, and it will be better to split check into two loops.

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

Was anyone able to get AC with binary search on B ? If yes can you share your solution ?

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

The problems are good.

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

Hmmm. Is the difficulty point of H right???