khadaev's blog

By khadaev, 7 years ago, translation, In English

Hello everybody!

Round 443 will start on Thursday, 26 October in 17:35 MSK.

Tasks are prepared by me, Konstantin Khadaev. It's my first round on Codeforces. Thanks to zemen, AlexFetisov, vepifanov, and Belonogov for testing problems, KAN for coordination, and MikeMirzayanov for this site and the Polygon platform.

Both divisions will have five problems to solve in two hours.

Scoring: in Div 1: 500 — 12501250 — 2000 — 2500, in Div 2: 500 — 1000 — 1500 — 22502250

Good luck to all!

UPD1: Congrats to the winners!

Div 1:

  1. dotorya — solved all problems!
  2. Um_nik
  3. jqdai0815
  4. V--o_o--V
  5. Errichto

Div 2:

  1. monsoon
  2. belkka
  3. Roooooo
  4. stasio6
  5. AngusRitossa
  • Vote: I like it
  • +311
  • Vote: I do not like it

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

PS :- IT IS RATED -___-

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

    You triggered the curse :/

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

Wow, Two contests in two days(CS Academy and codeforces) and written by the same author. I enjoyed the problems on CS academy, Hope they are good tomorrow too!

»
7 years ago, # |
  Vote: I like it -36 Vote: I do not like it

Is it rated means? I am new so i didn't understand what rated means.

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

    Its the most common "three words" you will find on the CF. Next common three words is "how to solve".

»
7 years ago, # |
  Vote: I like it -112 Vote: I do not like it

=i'll make a submission...

-What is the complexity of your code ?

= O(N^3)

-

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

    A could be quite reasonable depending on the problem. Consider the problem you are solving and the bounds, instead of making a sweeping statement on complexity.

»
7 years ago, # |
  Vote: I like it -81 Vote: I do not like it

Is it rated?

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

will it be available C#?

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

Codeforces Round #https.

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

I want to describe this not only as a contest, this is an opportunity to explore new thinks for everyone, and this can give a handfull of distribution of our future succes so I wish good luck to everyone and PLUSES ^-^ at the end.!

»
7 years ago, # |
  Vote: I like it -18 Vote: I do not like it

Great!

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

    Simillar thing happened when I tried to login. I think server is very slow and unstable right now.

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

While registering, Error- "HTTP Status 403 -" :(

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

I was registered to the round, but now I see that I'm not registered and I can't register again (HTTP Status 403)

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

Apache Tomcat/8.0.46

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

Wow the scoring distribution is announced so early! I guess this is a non-"traditional" round...

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

Why the delay?

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

delayed))

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

Delayed again...

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

Delays, delays, delays :P :P

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

6000 reg only div2? Not bad :)

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

servidor is very slow today, hope the contest continue rated.

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

+10 min as usual

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

for the writer,pls be short!

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

Why test case 3 in div 2 C is 0? Is there no program? Thanks!

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

    it's empty

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

      its special :p !!

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

      I don't get it, man!

      (output => the length of your program)

      Why ^ 0 is not a program?

      Why empty program as output? (No program as output)

      Thanks in advance!

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

        It's the number of operations that your new function does before returning the value.

        For example, if k = 2:

        int modify(int value)
        {
           int value1 = value & 100;
           int value2 = value1 | 3;
           return value2;
        }
        

        If the k = 0, then you have the following function:

        int modify(int value)
        {
            return value;
        }
        
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How did you know it was empty?

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

What is the hack for B?

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

How to solve Div-1 C and D?

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

    div1C
    Consider graph where there are edges from A -> B iff A can beat B , now consider each SCC in this , if a node can beat atleast one from this SCC and if atleast one from this SCC can beat this node , this node also belongs to the SCC , so an SCC can be characterized by mini and maxi which denotes min value of ith game strength of someone from this scc and similarly for max. This breaks the graph into a chain of SCC's , when you add a new node , find where it should belong in this chain , it will either belong complexity between 2 scc's or at the endpoint of the chain in which case just add this , or it will result in merging of a subarray in this chain into this node.

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

      "when you add a new node , find where it should belong in this chain"

      But assuming the worst case that at step #k you have k SCCs in the chain, doesn't this mean that the overall complexity becomes O(n^2*k)?

      There's probably something I don't understand in your explanation. Could you maybe elaborate just a little bit?

      Thanks in advance :)

      EDIT: ah, nevermind, you can probably keep the SCCs sorted for each k and use lower_bound() or something similar

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

Summary of my performance this round.

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

Ignore ...

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

Why i prefer dynamic scoring

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

what's wrong with this 31762295 for div2 B??

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

The problem C in Div. 2 was nice. Required a good bit thinking (atleast for me). My mind was blown...

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

How to solve div2 C ? Was it like taking Xor , and , or of all values and print in the same order. ?

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

    no that will not print the correct answer.

    Try in this input:

    |3

    ^2

    |1 Take x as 2.

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

      Thanks , Then what was the algorithm behind this you constructed to solve ?

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

        Suppose you have a 10 digits binary numbers — let 'xxxxxxxxxx' be his digits : what happen to those after the N operations? Can we get the same result with just 1x of each binary operation? :)

  • »
    »
    7 years ago, # ^ |
    Rev. 2   Vote: I like it +4 Vote: I do not like it
    a = 1023
    b = 0
    
    for each (op, val) in input:
        a = a op val
        b = b op val
    

    From there, we can see that for each bit in a and b:

    bit on / off: no operation;
    bit on / on: or operation;
    bit off / on: xor operation;
    bit off / off: or and xor operation.
    
»
7 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Those rooms in which there are no hacks are going to be destroyed by system tests. n = 10, k = 4, arr = {1 5 4 3 2 10 9 8 7 6} ans: 5

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

    oh...

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

    sad(

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

    Oh.The sad moment when you realise there were about 14-15 WA solutions in your room and still you couldnt figure out a hack. In my room there were no hacks at all :p.Dont know why I missed this case :(

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

Hacked 3 solutions in the last 3 minutes... (my last hack was 3 seconds before the end) So tense!

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

I think for div 2 C the key is strongly connected components.

If you look at the directed graph of the strongly connected components it is always a straight line.

For each strongly connected component we need to save only two arrays of size K (the one with the minimum power levels for each skill and the one with the maximum power levels).

Thus we can save the strongly connected components inside a map (the key for the map is a structure containing the two arrays and the size of the component).

In order to add a new vertex we need to use a lower_bound on the map and then iterate through the map mixing together the new connected components.

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

    Div 2 C?? Are you kidding me??

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

    How did you bring connected components into picture Jefe ??

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

      we add an edge from vertex a to vertex b if player a can beat player b in at least one game. Then the players that have a chance to win the game are the ones that can reach every node. Of course these nodes form a strongly connected component.

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

        Okkay Got it !! Thanks

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

          Answer is number of strongly connected component or what ???

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

            Answer is the size of the initial connected component (they form a directed path)

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

              n is 5×10^4 though. Won't it get TLE?

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

                Jefe Sorry to disturb !!!! How would you solve for this one n = 3 k = 2 1 2 2 1 3 3

                so In the first case, a single node is present ,then the second node comes and two directed edges are formed 1->2 and 2->1 . How do you get answer here ??

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

                  First the first node forms a SCC -> answer = 1.

                  After adding the second node, you have a SCC nodes 1 and 2 -> answer = 2.

                  The third node will form a SCC by itself, and this SCC is better than the previous SCC (they form a directed chain SCC{3} > SCC{1, 2}). The answer will be the size of the best SCC -> 1.

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

                  Thanks I got it . :)

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

    I like the idea of that key structure.

    You find a position of the first characteristic and then move up and down looking for min/max on the next ones (expanding the interval), correct?

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

And again I will fail C :( When do I will come in div1 :(

OMG It passed :p. Finally here I come div1 :D

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

Huh, these were really hard B and C. How to properly solve B? I did something like binary exponentation of reductions (sequences when consecutive groups of same people are merged and when I see interval of length k of same numbers I throw it away). However when done naively these reducted sequences can grow a lot, so I kept only a big suffix and prefix of them, but I am not sure about correctness of the way I did it. On the beginning I tried to reduct initial sequence, then reduct result concatenated two times and consider some cases, but that seemed to be really prone to bugs.

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

    I hope I haven't missed any edge cases, but basically what I did was:

    1. Preprocess the single bus to remove as many teams as possible
    2. Process all the buses together, removing teams that came from the two consecutive buses
    3. At this point, if the "middle" buses (other than first and last) have contestants from more than one city, we're done. Otherwise, we take the prefix from the first bus, the number of participants from the middle buses, suffix from the last bus and do stuff in the naive way.
  • »
    »
    7 years ago, # ^ |
      Vote: I like it -26 Vote: I do not like it

    Just curious.
    Is it easy for you to get the idea from source code 31746290?

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

This is not a Div.1, it is Div.0... I spent a lot of time to solve 1B. Anyway, I need to go to sleep...

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

Noooo.. I screwed up on div2C! I submitted 30 sec before end of contest and got WA because i thought that x was <= 2047 and not 1023 :(

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

How to solve Div2 E or Div1 C ???

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

How to solve div 2c ?

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it
    a = 1023
    b = 0
    
    for each (op, val) in input:
        a = a op val
        b = b op val
    

    From there, we can see that for each bit in a and b:

    bit on / off: no operation;
    bit on / on: or operation;
    bit off / on: xor operation;
    bit off / off: or and xor operation.
    
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      same method as mine but in the bit off / off case , I used & operation instead of using | and ^ ..

      Any particular reason why you used | and ^ instead of just using & ?

      Anyways, here's my solution if you are interested.

      Short explanation : observe that 0 to 1023 means all numbers having 10 bits.. Also observe that all the & , | and ^ operations actually apply to INDIVIDUAL BITS rather than the full number... So keeping a = 1023 and b = 0 means all bits of 'a' are set to 1 and all bits of 0 are set to 0.

      so accordingly check what happens to them AFTER applying all the 'n' operations, If no change ==> means the AND bit was '1' , or bit was '0' and xor bit was '0' and so on..,

      my submission --> 31767545

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

        i don't understand. please explain more. why 1023 and 0, what i can get from them after the n operations.

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

          see, 1023 == (1 1 1 1..... 1) (10 times) and 0 == (0 0 0 ...........0) (10 times)

          so basically we can treat 1023 and 0 as rather a SET of 10 bits..

          now apply all the mentioned operations,

          after applying if the a particular bit of 1023 remains 1 and that bit of 0 remains 0, this means that all those operations do NOT CHANGE THAT PARTICULAR BIT IN ANY NUMBER! Why? --> well that's because in every number that particular bit can be either 0 or 1 and no matter what that bit is , it wont change because we have tested it for both 1 and 0

          Similarly there are 3 more cases , all the cases have the same reasoning , i.e. if 1 1023 bit changes but 0's bits do not change it means that whatever be the number that Bit has to be equal to zero,

          apply same reasoning to get to the final answer!.. Hope this helps!

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

            Thankyou.W hen i read your previous comment my mind was not registering the fact that BITS OPERATION apply to single bit, so i didnt understood the solution. so one day when i was working on something, suddenly my mind clicked and i was able to solve it. This was good problem.

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

How to solve Div2 D?

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

Is the Div.1 contest really of the difficulty of Div.1? I spent more than 1h 40min working on B and only resulted in 5 Wrong Answers on pretest.

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

O(NQ) solution for problem D .

Ugly code, without any beautiful optimizations, but ... AC =)

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

Thank you for 5 great problems!

btw, I got AC on E after contest by adding one character on my TLE code (I knew that could cause TLE, but my unconciousness omitted one character). and I got only A passed :(

I really liked this problemset although I'll get -170 :)

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

Tests for div1B are weak. Noam527 found a test, that breaks my AC solution:

4 3 3

1 1 2 1

http://codeforces.me/contest/878/submission/31762139

My solution outputs 6, while it should be 0.

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

    It is very bad to provide a hard task with weak tests:

    1. Not many people will solve it and they would be upset that other guys have accepted incorrect solutions.
    2. Those, who solved it correctly, would be upset that some other folks have accepted incorrect solutions, lowering their achievement.
    3. Those who have accepted incorrect solutions would also be upset, as this gives them no satisfaction and unjustified points. (Not 100% sure about that though.)
»
7 years ago, # |
  Vote: I like it +38 Vote: I do not like it

Challenge: div1D with k ≤ 1000.

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

    Do you have a solution on mind or is it just your wishful thinking? Looks really hard

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

      I think that my solution will work (except for input and sorting (the latter can be done in linear time))

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

        Can you please explain your solution? I could not understand the code.

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

          Let's suppose we have only one query of third type. Then we can maintain only the characteristic which we are asked for. Now let's do binary search on answer (there are only k possible answers), then we can maintain only one binary characteristic: is the real characteristic bigger than our bound (from binary search). Max/min on binary characteristic is equivalent to or/and.
          Now we can do parallel binary search for all queries of the third type and do our operations using bitsets.
          Complexity will be

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

Well,good problems today.

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

can anyone please explain Div 2 problem C logic ? thanks in advance :)

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

I failed test case #7 on problem C div 2.

Can somebody tell me what is wrong with my result?

3
^ 125
^ 377
& 1019

Participant's output

2
& 1019
^ 260

Jury's answer

2
| 4
^ 260

Checker comment wrong answer The participant's program isn't equivalent to the input

I passed this one with the same idea, grouping by operators:

3
& 242
^ 506
^ 522

Output

2
& 242
^ 1008

Answer

2
| 781
^ 253

Checker Log ok Ok

Thanks in advance!

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

    Just try any input, e.g. 0. With the input program: ((0 ^ 125) ^ 377) & 1019 = (125 ^ 377) & 1019 = 260 & 1019 = 256. With your program: (0 & 1019) ^ 260 = 0 ^ 260 = 260.

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

Cheater Report:- ImNaman and kingside have cheated as you can see even variable names are same for problem A and B and slight change in variables of C.

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

When will be editorial published?

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

Editorial!!?

»
7 years ago, # |
  Vote: I like it -6 Vote: I do not like it

Will there be any editorial? Thx :)

»
7 years ago, # |
  Vote: I like it -18 Vote: I do not like it

Why are the editorials so late?

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

Can Anyone Explain Div 2 Problem A?

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

    Iterate through the array of s[i] and d[i] and keep updating the present day of meeting the current doctor.

    To update the present day, if (presentDay < s[i]) presentDay = s[i]

    Otherwise, find the smallest value of k (>=0) such that: presentDay < s[i] + k*d[i] and put presentDay = s[i] + k*d[i] for that value of k

    The answer will be the presentDay for the last doctor in the array

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

Where is the editorial??

»
7 years ago, # |
  Vote: I like it -23 Vote: I do not like it

Hello, can someone tell me where can I find the editorial of this contest? Thanks.

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

In proB, why test 5 2 1 4 2 5 3. The output is 4? I think the output is 5? Can someone explain for me?

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

    5 2
    1 4 2 5 3
    first win: 4 because (1 < 4).
    4 2 5 3 1
    the second win: 4 because (4 > 2).
    Answer 4 (because 4 won two wins in a row).

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

      5 2 2 1 3 4 5 this test why the power's winner is 5 ? I think answer is 3 ?

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

        5 2
        2 1 3 4 5

        2 1 3 4 5 winner is 2
        2 3 4 5 1 winner is 3
        3 4 5 1 2 winner is 4
        4 5 1 2 3 winner is 5
        5 1 2 3 4 winner is 5
        5 have two wins. It means answer is 5.

»
7 years ago, # |
  Vote: I like it -19 Vote: I do not like it

Where is Editorial?

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

I get WA in Div2 C because of additional space at the end of first line. I thought that Codeforces typically ignores additional spaces at the end of line.