By PikMike, history, 4 weeks ago, translation, In English,

Hello Codeforces!

On Aug/22/2019 17:35 (Moscow time) Educational Codeforces Round 71 (Rated for Div. 2) will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 7 problems and 2 hours to solve them.

The problems were invented and prepared by Roman Roms Glazov, Adilbek adedalic Dalabaev, Vladimir Vovuh Petrov, Ivan BledDest Androsov, Maksim Ne0n25 Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all participants!

UPD: Our friends at Harbour.Space also have a message for you:

Hello Codeforces,

We are opening a new campus in Bangkok, Thailand!

We are delighted to introduce a strategic partnership between Harbour.Space University and the University of the Thai Chamber of Commerce – a collaborative effort powered by B.Grimm.

After 3 years of successfully disrupting education in Barcelona, with a unique educational model founded on active learning in entrepreneurship, technology, and design, as well as the most extraordinary academic and professional community on the planet to show for it, we are ready to bring the revolution to our new campus in Bangkok, Thailand.

Scholarships for our Bangkok campus are designed to completely eliminate the barrier between exceptional talents and sophisticated education: they cover the entire tuition fee as well as the cost of living expenses, and furthermore, they provide the student the valuable experience of both studying and working at Harbour.Space University.

Unique opportunities reserved for the most brilliant students from anywhere in the world, our scholarships are more than financial support – they are portals from your past to your future.

If you are graduating or have already completed a bachelor's degree, we are waiting for your applications for fully-funded Master's degree scholarships by the link below.

APPLY HERE→

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 hehezhou 7 235
2 pekempey 7 235
3 TadijaSebez 7 238
4 Barichek 7 241
5 ixy 7 247

467 successful hacks and 688 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A V--gLaSsH0ldEr593--V 0:01
B Dalgerok 0:04
C kmjp 0:12
D pizzadelivery 0:13
E AkshajK 0:10
F AnotherRound 0:07
G danya.smelskiy 0:26

UPD: Editorial is out

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

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

This may be the first contest for me after getting purple.Hope that I won't drop to blue. :D

I hope that the problems will be nice and easy to understand.

Wish all of you good luck && high rating!

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

    orz

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

    deleted

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

      [Deleted]

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

        deleted

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

          Please do not publish so many "orz"s on Codeforces. This is Codeforces, not Wechat or QQ or Instergram or Youtube.

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

            "Weixin" is "We-Chat" in English

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

            What does orz means??

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

              It looks like kneeling.Show admiration for the other person.

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

            Yeah, this is Codeforces, not Wechat or QQ or Instergram or Youtube. Here everyone orzes, not just Chinese people.

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

              Only kids, not everyone

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

    Last round you got +220 rating,so I think this round you can have higher rating. May be you can become Master.

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

      It doesn't work that way.

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

      Thank you for your wishes~,and no matter how it works,I will try my best.

      Wish you will become a master too. :D

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

    I am 1800 now, and I hope I can get +100 rating in near future.

    Best wishes to all of you!

    And if my rating is 1900, whether my name is purple or blue?

»
4 weeks ago, # |
Rev. 3   Vote: I like it -7 Vote: I do not like it

Educational #71 ^_^

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

let's hope that it won't be like the last educational round

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

Hope that problems will be interesting and the problems will take some time to develop logic. Then we can have a nice contest also fewer submission and no queue.

»
4 weeks ago, # |
  Vote: I like it -7 Vote: I do not like it

I hope taht the problems be easy to understand not like round 70 X)

»
4 weeks ago, # |
  Vote: I like it -6 Vote: I do not like it

Can I change my color?

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

    to green lol

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

      Simple trick: Do one wrong submission and quit.
      If you do this for next few contests, you will even reach grey.
      Good luck :)

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

        There is better method to solve a problem with lots of wrong submission, and make lots of unsuccessful hacks to decrease your point. This is more efficient. PS. My color will change to blue after few hour

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

          But I meant my method is simple, ofc there are many other methods like yours.
          Have a nice day :)

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

    why somebody always dis me are everyone want‘t be better? or what wrong with me

»
4 weeks ago, # |
  Vote: I like it -35 Vote: I do not like it

Why the answer in the first test case of problem C is not 86 = 14 * 5 + 8 * 2?

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

    you should ask question in the contest but not here

»
3 weeks ago, # |
  Vote: I like it -30 Vote: I do not like it

How to make problem C?

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

The problem set was real nice.

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

Why so many tests??? Especially F???

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

A much more friendly Educational Round. :)

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

What was testcase 5 on problem B? Been scratching head over all contest but couldn't debug it.

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

    Your logic behind calculating the modulo of the number of ones is wrong. It is not necessary that the number of ones is divisible by four for a valid sequence of transformations to exist.
    Here's an example:
    1 1 1 1
    1 1 1 1
    1 1 1 0
    1 1 0 0
    you can apply the operation at:
    1 1
    1 3
    3 1
    2 2

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

Did anyone solve C using DP ?

my code got TLE 8, any help?

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

    I think you forgot the case height 2 to height 1 (or height 1 to height 2) when the second position is '0' or '1', these two cases are not the same.

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

      then this should cause WA not TLE, right?

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

      Yes, but you used recursion so the complex is 2^n, you should store dp[indx][last] to avoid recalculate.

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

        hmmm, in this line ll &ret = dp[indx][last]; i already store the answer in the dp (by reference) !

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

    You memset all array in every test , clear only size n

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

    I found the answer for Problem C (using DP) after read your code. Solution: 59330841

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

What is the test Case 13 for C. I was trying DP. Btw I found E to be easier than B and C.

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

    The height of the rightmost pillar must be 1.

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

      :(. I have to improve my problem reading capability, I took eternity only to understand the problem.

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

        Mine also man. But can anyone tell me please whats going on problem C. I am reading continuously 3-4 hours but still didnt understood what the problem actually asked. Can anyone please expain it easily. Thanks in advance :) Sorry for my poor english.

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

    "Note that you must start and finish the pipeline on height 1 and, also, it's guaranteed that the first and last characters of the input string are equal to 0."

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

    You could just brute force for B. Check out every possible square, in O(N^2) time. N < 50.

    For C, DP isn't actually necessary, although it took me a lot of time implementing.

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

    can't we solve it using greedy? I tried it using greedy but got WA on test 13 and still don't know why.

    idea — first find all the continuous segments of zeroes with length > 1 and for each of them check the min of both possibilities and then just calculate the answer.

    entertained the first and last element case by combining them (they become a segment of 2 or greater elements).

    Edit: it should start and end at 1 (i didn't entertain it)

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

It took an hour for me to implement C and by the time I realized contest was already finished :P

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

Is authors' solution on problem F has time complexity $$$\mathcal{O}(n \sqrt{n})$$$? If yes, why is limits on $$$n$$$ is so big?

»
3 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

Did someone submit HLD + SQRT decomposition (fact that there SQRT groups of queries grouped by length of string) solution in G?

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

How to solve problem D?

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

    +1

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

    Use including exclusion, I calculate the number of ways to sort each part and minus the number of ways to sort both parts. The answer initially is n!.

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

      Can you explain how to calculate the number of ways to sort the arrays? I thought the same thing but i wasn't able to implement it.

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

        You can read my code, it's easy to read and understand

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

      Could you explain the intuitive idea to compute the number of ways to sort both parts. Just want a hint ,i dont want the complete solution.Thanks in advance.

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

        Sort the list of tuples (sorting by first element, then second by default). Then check if the list is sorted by second elements. Ignoring duplicates, there will only be one (if any) valid sorting, so you need to count how to add in the duplicates.

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

      missed something. but correct. thanks

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

Probably, the most "un-educational" educational round I've ever seen.

It's not a bad problemset, but I expect more DS and algorithm in an ed round.

In addition, the only Data Structure task in the contest (G) is actually similar to Chinese NOI 2011阿狸的打字机. (Link to problem)

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

Can you tell me please how to solve E?

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

    Let's say desired number is $$$X$$$. If you could query only one number, you would send 0 and get $$$X$$$ XOR 0 = $$$X$$$ as an answer. If you sent some degree of 2, you would get $$$X$$$ XOR $$$2^k$$$ = "$$$X$$$ with its k-th bit reversed". Generally, if you send an arbitrary number, you would get $$$X$$$ with some of its bits (the ones that are set to 1 in your number) reversed. The only problem is that you do not know which bits are reversed when you send 100 numbers.

    My idea was the following: use only odd bits in the first query and only even bits in the second query. So, the first query will contain 100 numbers with some of their odd bits set to 1, and the second query will contain 100 numbers with some of their even bits set to 1. Then you will get the following as answer:

       X = 100010110
    ANS1 = 101000111 // 1st, 5th and 7th bits were reversed; XOR happened with 1010001
    ANS2 = 100011100 // 2nd and 4th bits were reversed; XOR happened with 1010
    

    When you compare ANS1 and ANS2, you will see that they differ only in those places where bit reversal happened:

    ANS1 = 101000111 // 1st, 5th and 7th bits were reversed
    ANS2 = 100011100 // 2nd and 4th bits were reversed
             ^ ^^ ^^
    

    That means that ANS1 XOR ANS2 (1011011) will give you the set of bits that were XOR-ed in both queries. Then you just need to check which two numbers among those 200 you sent form the same set of bits. In other words, find $$$x_i$$$ from 1st query and $$$y_i$$$ from 2nd query such as $$$x_i$$$ XOR $$$y_i$$$ = ANS1 XOR ANS2. Then you can find X as ANS1 XOR $$$x_i$$$ or ANS2 XOR $$$y_i$$$.

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

    Let the input results be N and M and the answer be A. Then, we have two equations: A ^ X = N and A ^ Y = M, where X is in the first output set and Y is in the second output set. Taking the XOR-sum of these two equations gives A ^ X ^ A ^ Y = X ^ Y = N ^ M.

    Then, if we can find two sets of 100 numbers such that there are no two distinct pairs of integers, one in the first set and the other in the second set, with the same XOR, we're essentially done: find N ^ M, and then use that to find the unique X ^ Y such that X ^ Y = N ^ M.

    This is fairly easy--just take 100 integers that make use only of the first seven binary digits as the first set and 100 integers that only use the next seven binary digits as the second set. One simple construction is to use 1 through 100 as the first set and 1 * 128, 2 * 128, ..., 100 * 128 as the second set. From here, we can iterate over all pairs of these integers to find the appropriate X and Y. Afterwards, reconstructing the answer is easy--if A ^ X = N, then A = X ^ N, so once we know X we can simply print X ^ N.

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

      Thank you too!

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

      We can also try to bruteforce for these two sets(although it is not guaranteed we will find them this way).

      I assumed that numbers from the first set are $$$0, 1, ..., 99$$$ and was greedily choosing $$$b_i$$$ as the least number, such that its xor with every $$$a_j$$$ doesn't equal to any of past pairwise xors. The biggest number in the second set happened to be $$$12672$$$.

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

      Cool, this looks simpler than I imagined to myself :)

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

      We can even simplify that logic:

      If we took "100 integers that make use only of the first seven binary digits as the first set" then, after getting the answer, we will know the next 7 bits of X, since all integers in the first set have same 7 most significant digits.

      Analogically, asking the second set will lead us to knowing 7 least significant bits. Profit.

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

      Geothermal WOOOOOOOOOW XD your solution in other place, really soooooooooo amazing

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

In problem A, this solution print the answers in one line, while it is required to print them in seperate lines. Still, it received an AC verdit.

Should this solution be considered AC or WA?

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

    Where exactly in the problem statement is it written that you must print one integer per line? :)

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

The distribution of the number of accepted submissions of each problem is like Div. 3!

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

If you liked problem F, here’s a similar one for you. https://open.kattis.com/problems/modulodatastructures

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

would someone explain why this submission got WA on test 4 , please :)

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

    Change every int to long long int (you can leave int i), and you will get AC.

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

Got AC in problem C with greedy, why is everyone using dp? https://codeforces.com/contest/1207/submission/59315532

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

for problem D I tried taking all possible ways to get the first half sorted basically taken the frequency of every number and multiplying those , and the same for the other half , now if the sorted state of the array is sorting the first half along side the other half (both half's are sorted ) then the answer is all the possible permutations — max( number of ways the first half could be sorted , number of ways the other half could be sorted ) otherwise its gonna be all the possible permutations — (number of ways for the first half + number of ways for the second half ) note that there is only one way for the array to be sorted( bad ) but we must calculate the number of times this happens consider the example 1 1 2 2 3 3 the only way it could be sorted is 1 1 2 2 3 3 but this could happen 8 times factorial( frequency(1) ) * fact( freq(2) ) * fact( freq(3) ); = fact(2)*fact(2)*fact(2) = 2*2*2 = 8 can someone prove this wrong please

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

    did u get anything !!!

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

      nope still stuck

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

        i have also done the same thing and getting WA on 4.but that test case is too large to find out the mistake.

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

          me 2 , I get a negative number so something must be wrong , I think it's because of the mod operation ( a — b )% c

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

            yah u can add do (a-b+c)%c to get positive but still your ans remains wrong

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

I don't know why my D wrong answer on pretest 13... who tell why? thank you very much 59302847

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

    sorry)

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

      The answer should be 0 and not 1. Any permutation of that will give a bad sequence.

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

        what are you saying...?

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

        is there any example?

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

          My comment was in response to Nutella3000's old comment. He has revised his comment now. I can't find any counter cases with your code.

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

Is there any hack for a greedy solution for problem C ?
Because, I see ppl talking about DP solutions, while I felt greedy should work. :)

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

    Greedy seems correct to me. Basically, you only need to take care of separate segments that look like ...100001..., and you either select to cover it all at height 2, or choose to dive at least once to the height 1. But if you go to height 1, you already spend 2*a, and there is no reason to put any additional pillars on this segment. It is just that DP is a safe bet :)

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

      Yeah, dp solution is just quick to arrive as soon as you know you can fit the statespace in memory and pass the time limit. And can promise correct answer.
      Where as greedy took time to prove and is still risky.

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

    My solution greedy: https://codeforces.com/contest/1207/submission/59310430 DP code faster than greedy. I think so..

»
3 weeks ago, # |
  Vote: I like it -11 Vote: I do not like it

I think the problem D statement was not clear ... there is no thing refer the the permutation is of indexes not permutation of elements it self ( it different in handle the same permutations )

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

Help me with Problem B please.

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

      Got it. Thanks that helped. If you don't mind, Can you explain me Greedy approach for Problem C.

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

        for every index we check the position of the next 1 we iterate through the array and check if we should go up or go down and then calculate the cost we start at state down 0 and move up only if a[i] = 0 && a[i+1] = 1 this must happen always now if a[i] = a[i+1] you shouldn't change the state just calculate the cost and if a[i] = 1 && a[i+1] = 0 calculate the value i would lose if we go up , and if we go down and go according to the min

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

      alot of contestant got hacked by doing brutefoce... do you know why?

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

What is the hacking case for problem B ?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +14 Vote: I do not like it
    hacking test for my submission
    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      It should be -1 isn't? My solution does so.

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

      so if we pick x=3,y=3, the 2x2 matrix will only change the value of A(x,y)?, i thought we cant do that :(

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

        You can't pick (3, 3) according to the statement.

        ... In other words, you choose two integers x and y such that 1≤x<n and 1≤y<m, and then set Bx,y, Bx,y+1, Bx+1,y and Bx+1,y+1 to 1.

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

        No we can't do that. As problem statement says "you choose any submatrix of B having size 2×2". When you take x=3, y=3 then the 2x2 matrix will not be a submatrix of B.

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

        Looking at the expected output, they only output 1 1 as the sequence; they don't even address (3,3) at all.

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

is their is something better it cost me 7 wa 5 what is that test that fails my solution i tried all possible cases thanks in advance.my submission

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

    Try this snippet:

    5 50
    0 0 0 1 1 0 0 0 0 1 1 0 1 1 0 0 1 1 0 0 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0 0 1 1 0 1 1 1 0 0 0 1 1 1 0 0
    0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 0 0 1 1 1 1 0 0
    0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 0 0
    0 0 0 0 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0
    0 0 0 0 1 1 1 0 0 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 0 1 1 0 0 1 1 1 1 1 1 1 0 1 1 1 1 1 0
    

    The answer is not -1.

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

Can anyone explain me the logic of solution to question A?

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

    Brute Force!!!

    Try all possible sizes of hamburger and chicken burger and check if you have enough buns, beef patties, and chicken cutlets to make them both if you do save the result and at the end output the maximum.

    JUST CURIOUS

    Does anyone have an O(1) solution excluding the number of queries?

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

in problem D,can someone explain me the sequence include one pair is non-descending or non-increasing ,thanks???

»
3 weeks ago, # |
Rev. 1995   Vote: I like it -58 Vote: I do not like it

Nice contest!

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

    HOW? MAXSUM = MAX(yi)*q <= 1000*500000 < 1000000000 (it must be int) Your solution get WA only because you should get sum of all numbers from 1 to 500000 which have remainder y, but you sum all numbers from 1 to q which have remainder y

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

    2000 revisions wut

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

    For those who are curious. Comment You can't hide it by 2000 revisions.

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

Can G be solved without Aho corasick and segment tree ? Like using hashing and sqrt decomposotion ?

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

    You can use modified suffix array algorithm to build something like suffix array on the given strings.

    The modification you need in the suffix array is that on the $$$i$$$-th iteration you should compute the equivalence class for every vertex $$$v$$$ of the ``string tree'' (the class of the suffix of the $$$v$$$-th string from the input which has length $$$2^i$$$).

    UPD: Forgot to mention that you should consider reversed strings in this approach to build suffix array correctly.

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

      Even if we build the modified suffix array, how are we calculating the answer for each query ? I have a solution but that is quite ugly.

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

        With suffix array we can find all occurences of the string $$$t$$$ from the query in our strings in $$$O(|t| \log n)$$$. To do so, you may do two binary searches.

        Then you have to consider only the vertices that belong to the path from the root to the vertex we need. The easiest option that comes to my mind is to do DFS on the string tree and use Fenwick tree to maintain the vertices we need, but maybe there's something simpler.

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

    Hey I solved it only with Aho corasick, Can you explain your approach with segment tree? Mine is solved ofline and having an array of frequencies for each string (like all the matches from the root to current node). So basically I do a dfs traversing the tree and process the current character of the current node, and then answer all queries. In order to update the array, I iterate over the fail links in the aho corasick. The code is very simple if you know Aho corasick. It works in N*sqrt(n). code

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

      Can jumping through the failure link again and again timeout ? What happens if the query string is all aaa...aaa and so is the given string ?

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

        The trick here is that there are only sqrt(n) different lenghts. So you cannot jump more than sqrt(n) for each node in the aho corasick (notice that actually I'm not using the direct fail link but the output fail link.

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

          ** notice that actually I'm not using the direct fail link but the output fail link. ** Now I get it. I didn't have this observation. My solution is almost the same. Instead of jumping through the failure link, I use a data structure that can add a value to some node and query the sum in a subtree. This can be done using euler tour of the tree and segment tree.

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

            Just to clarify, you use the data structure over aho corasick tree?

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

              yes, on the failure link tree.

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

    I solved it with centroid decomposition.

    We only need two string algorithms. Denote $$$n = |STR|, m = |PAT|$$$:

    1. O(n log n) preprocessing, O(m log n) counting of appearances of pattern in string
    2. O(n) counting of appearances of pattern in string

    I did the first by binary searching suffix array, and the second is just KMP.

    Given these two, we can solve the problem with centroid decomposition. First read all queries and place them into the nodes in the tree where they occur. Find the centroid of the entire tree. Preprocess the string from the root to the centroid. Then DFS all queries in the subtree of the centroid, and add to their answer the number of the pattern's occurences in the preprocessed string (with algorithm 1), and its occurences overlapping with the end of the string but not contained in it (with algorithm 2). Note that we only have to process a string with length 2m in algorithm 2.

    After processing the centroid, clip its subtree away from the original tree and recursively solve its subtrees. Repeat until the original tree is empty.

    This correctly answers the queries by dividing the query string into multiple strings $$$S = S_{1} S_{2} \dots S_{k}$$$, and calculating its appearances inside each individual $$$S_{1}, \dots, S_{k}$$$ (with algorithm 1) plus its appearances not inside any individual $$$S_{i}$$$ with algorithm 2.

    Total time complexity is $$$O((n + m) \log^{2} n)$$$ where $$$m$$$ is the total length of the query strings, since due to the centroid decomposition we do the preprocessing of algorithm 1 on every character at most $$$\log n$$$ times, and we do the matchings with algorithms 1 and 2 for every pattern at most $$$\log n$$$ times. Note that if a suffix automaton was used instead of binary searching a suffix array, we could do algorithm 1 in $$$O(n)$$$ and $$$O(m)$$$ time, bringing the whole algorithm to $$$O((n + m) \log n)$$$.

    Code: 59351316. My submission during the contest TLE'd due to doing $$$O(n \log^{2} n)$$$ suffix array construction.

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

      I solved with heavy-chain decomposition. Please see my comment at the bottom.

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

The penalty of taking long long is too high in F, anyone agree with me?

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

    Can't agree with that.

    Model solution with ints replaced by long longs works in something like 2.2s.

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

      Mine works in 3.993 :( Any ideas for improvement?

      Link

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

        Okay, it seems I was wrong.

        I replaced only the variables required to store the answers and the result on each query with long longs. It seems that creating a new long long in each for-loop and changing it can be really heavy.

        I am sorry for putting the constraints too high.

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

        One if statement can be taken outside the loop, down 0.1 sec only though. https://codeforces.com/contest/1207/submission/59323107

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

        You should probably know, that the modulo operation is much heavy than simple addition, so decreasing the number of taking modulo is almost always good.

        In this task you can decrease number of modulo operations by decreasing the "sqrt-constant". For example, changing $$$700 \to 400$$$ leads to two times speedup, so the solution with int64t works in only $$$2$$$ seconds.

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

          Wow!Didn't know that big a difference was there.Thanks!

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

    My solution with long long works in 2s (59309544)

    However, just because of the adrenaline of the contest, I couldn't notice that long long wasn't needed.

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

So sad. I thought minimize answer for problem B. too hurry :(( i spent 30 minutes for it

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

How to solve F?

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

    For large x, you can easily accumulate all values in a (There are about 500.000 / x indices with remainder y).

    For small x, this is not suitable. But for a small x, you can maintain a 2D-Table (i,j) := Sum of all values in array slots with index % j == i. Updating this table for a single query takes j steps.

    Now use the sweet spot K = sqrt(n) to decide if x is small (about 700 for n = 500.000, but depending on the constant factors of both sides this value can be shifted 'slightly' between at least 400 and 1000.)

    Update: - the array in O(1) - the 2D-Table in O(sqrt(n)) is about 700 Query: - Large x (x > K = 700) in O(n / x) is about 500.000 / 700 =~ 700 - Small x : query the table in O(1)

    For n queries you get a total of O(n sqrt(n)).

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

I can't understand why overflow (task C) 59307028 (may be I am wrong and it is not overflow)

There is no hard limits

Third Edu round in a row when I change algo to BigInt (previous five minutes after contest)

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

I still do not understand the implementations of D. The solution is, (more or less obvious)

allPermutations - permutationsSortedByA - permutationsSortedByB + permutationsSortedByAandB

So far, so simple. The numbers are calculated using factorials. But, how do we get the number of permutations sorted by a and b? I dont get the idea, even after reading the working codes.

Somebody explain this?

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

    deleted (I am not right)

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

    allPermutations = n!

    permutationsSortedByA = multiplication of count of first value in pair

    permutationsSortedByB = multiplication of count of second value in pair

    permutationsSortedByAandB = multiplication of count of each unique pair

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

      What about like folowing 4 pairs:

      2 1
      3 2
      3 3
      4 4
      

      There are two perms sorted by a, one by b, and one by both. How do I find the number of both if there are no duplicate pairs?

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

        Check if sorting by first, second will also get sorted then it will be 1 else it will be 0.

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

    Sort the array by first number, ties broken by second number. Then check if a[i].fi <= a[i+1].fi & a[i].se <= a[i+1].se. If so, then count occurence of each pair and arrange then in fact(cnt) ways.

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

    My idea that sortedByA : if all A is equal than answer n! because each permutation is sortedByA, now multiplicate factorials of number of equal numbers by A: 1,1,1,2,2,3,3,3,3 -> 3!*2!*4! Now numbers of permutations SortedByA, SortedByB, SortedByAandB can calculated in same way. (1,1),(1,2),(1,3),(2,2),(2,2),(2,2),(2,3): A(3!*4!), B(1!*4!*2!), A_B(1!*1!*1!*3!*1!)

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

      What happens when there are no permutations that are sorted by A and B?

      The first test case is an example of this:

      3
      1 1
      2 2
      3 1
      

      According to your idea:

      SortedByA = 1! * 1! * 1! = 1

      SortedByB = 1! * 2! = 2

      SortedByAandB = 1! * 1! * 1! = 1

      And the result is 6 - 1 - 2 + 1 = 4

      But the actual result should be 3.

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

        You need to check whether sorted by A and then by B is sorted by B

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

Problem C , i used the greedy approach : first if the string input doesn t contain any 1 the answer is _ (a+b)*n +b_ else

i search for the first index i1 such that s[i1]=0 and s[i1+1]=1 i search for the first index i2 such that s[i2]=0 and s[i2-1]=1 this way we are sure that segements[0,i1-1] and [i2+1,n-1] are on level one so initialy i consider that [i1,i2] is on level 2 so the initial cost is ( (((i2-i1)*(2*b)))+ b*(n+1-i2+i1) + n*a + 2*a )

it s clear ( i assumed) that continous segements of 1 or 10 should be on level 2 let s call them type 1

so inside segement [i1,i2] we just need to consider those that aren t type 1 do we replace them by level 1 or change them to level 2 comparaison between 2*a and the nunber of pillars in that interval d * b we then decrement cost by db and add 2a if it s optimal to do so

my submission stops on test 11 i don t know why any suggestions ?

https://codeforces.com/contest/1207/submission/59321454

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

Any explanation on why the following solution for E does not work would be appreciated.

Make a query with the integer set S = {1, 2, 3..., 99}. Let the result obtained from the judge be result_S. Similarly, make a query with the integer set T = {100, 101, 102..., 199}. Let the corresponding result be result_T. Now, result_S = x XOR i, where i belongs to S. Also, result_T = x XOR j, where j belongs to T. Taking an XOR of result_S and result_T yields i XOR j. Brute forcing over all possible values of x and i should be sufficient to determine x_actual, I think.

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

    You should choose 2 possible sets of 100 numbers such that there is unique pair (i,j) which gives that i xor j value to guarantee that your answer is correct.In your case (i,j) may not be unique(For example in your sets consider two cases, case1:i=3 j=127 and case2: i=2 j=126, both give same xor value which is 124).

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

      Wouldn't i XOR x and j XOR x be sufficient checks?

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

        They would be sufficient checks if you choose sets S and T such that xor of numbers in every pair (i,j) where i is in S and j is T is unique. Otherwise there would be a possibility that two different numbers satisfy the conditions as stated by you. So if we choose S={1,2,3,...,100} and T={1*128,2*128,....,100*128} it would be guaranteed that for every (i,j) i xor j gives a unique number(since last 7 bits of every number in T is 0 and first 7 bits of every number in S is 0).Then you can solve the problem as you have stated.

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

    first of all, your first query has 99 numbers, not 100. But the i^j of your sets are not unique, for example 97 ^ 101 == 98^102.

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

Editorial please.

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

Problem F is just the reverse version of this problem:

https://open.kattis.com/problems/modulodatastructures

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

How to solve problem G?

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

I feel sorrow at missing this contest. Problem A really convinced me.It 's interesing. My solution: 59330841

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

Won't there be any system testing (on hacks), because it's showing final standings?

»
3 weeks ago, # |
  Vote: I like it -7 Vote: I do not like it

Ever pondering of entertainment-al rounds in addition to education-al rounds? Let's watch our newest entertainment-al content: https://youtu.be/D3wC1hgWcZA. Feel free to like, share, subscribe, upvote and feedback. Thanks a lot.

»
3 weeks ago, # |
  Vote: I like it -6 Vote: I do not like it

Is it rated?

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

Is it rated? Why I have no change in rating?qwq

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

How to solve C by dp?

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

i have participated in the contest i got a mail that my code has been copied. I dont know the guys mentioned.I think it happened by coincidence can you add my score.

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

Is Problem G solvable with Suffix Automaton ?

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

    An online solution to problem G :

    We build the suffix automaton for the trie which is given, and then we build a segment tree for every node (endpos set) . For a query, we do the heavy-chain decomposition for the trie, and then we query the segment tree sum.

    Total time complexity is $$$\mathrm O(n\log^2n)$$$ .

    My code : https://codeforces.com/contest/1207/submission/59299826

    This method use so much memory that it will get MLE on test 21 (https://codeforces.com/contest/1207/submission/59296517), but you can get AC with replace the array with std::map.

    Sorry for my poor English.

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

      i'm curious where people learn this kind of stuff,do you have any suggestion where to start learning data structure and the implementation like that?

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

After I saw the announcement, I added if(n==1)cout<<1<<endl; to my code.

I have perfectly reached top stupidity.

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

Can someone help me with 59286702. I have got wrong answer on case #87. while I am getting correct answer on my local machine. Any help will be appreciated. I think there is some issue with 14th line int a[n][m]={0}; I checked custom invocation with G++11, it works fine. In G++14 it gives wrong answer. Please help.

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

    The problem comes from this line:

    int a[n][m] = {0};

    I'm not sure how it works, but it just wouldn't initialize all elements to 0 properly.

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

      Yeah, will search for it. Thanks a lot.

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

        When did you edit your comment though

        I just made it look like a weird conversation xD

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

      yes you're correct.Though it works perfectly fine when done on single dimensional array.Still memset is a bit safer choice.

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

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

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

Can you add top hackers PikMike

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

    Sorry, I found out it'd been broken after the previous round and haven't fixed it yet.

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

Is there is any better way to solve F other than obvious q sqrt(n)

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

    sorry, could you elaborate me about problem F? i dont the second query, especially "set of all integers from 1 to 500000 which have remainder y modulo x", thanks in advance

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

Does not educational round show top hackers anymore?

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

Editorials please

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

When will be the tutorial?

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

Wanted help with problem C dp solution. I have the following: MY DIV2-C Solution. I added 1) comment line in the code by a hunch... and it gives AC with it... What I dont understand is how this line works and gives AC? Thanks for the help in advance.

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

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