AlexandruValeanu's blog

Invitation to CodeChef August Lunchtime 2017!
By AlexandruValeanu, history, 7 years ago, In English

Hello, CodeForces Community!

I am really pleased to announce that August Cook-Off 2017 saw mind boggling performances by the participants. The zeal and enthusiasm amongst the participants, really makes us feel proud and we are on cloud nine. To keep the competitive spirit on, we bring August LunchTime (https://www.codechef.com/LTIME51)

The contest will have four problems set by me and joining me on the problem setting panel, we have:

  • Problem Setter: AlexandruValeanu (Alexandru Valeanu)
  • Problem Tester and Contest Admin: kingofnumbers (Hasan Jaddouh)
  • Editorialist: likecs (Bhuvnesh Jain)
  • Russian Translator: CherryTree (Sergey Kulik)
  • Mandarin Translator: huzecong (Hu Zecong)
  • Vietnamese Translator: Team VNOI

I hope you will enjoy solving them. Please give your feedback on the problem set in the comments below after the contest.

So, note down the details and be there when the contest starts:

Time: 26th August 2017 (1930 hrs) to (2230 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.

Details: https://www.codechef.com/LTIME51

Registration: You just need to have a CodeChef handle to participate. For all those, who are interested and do not have a CodeChef handle, are requested to register in order to participate.

Prizes: * Top 10 performers in Global and Indian category will get CodeChef laddus, with which the winners can claim cool CodeChef goodies. Know more here: https://www.codechef.com/laddu. (For those who have not yet got their previous winning, please send an email to [email protected])

Good Luck! Hope to see you participating!!

UPD: The contest has started!

UPD1: The contest has ended!

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

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

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

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

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

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

If I have totally 0 points at contest (also I submitted something), am I considered participant of contest?

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

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

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

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

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

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

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

Too long queue :(

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

Submitted and got 10 points from MATCUT, 35 minutes passed and my score still not updated.

UPD: FIXED

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

I hope you all enjoyed the problems.

The editorials for the problems can be found below :

MATPAN

MATDYS

MATTEG

MATCUT

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

Problem 2 has a slight disadvantage for Java programmers as Java doesn't have native support for unsigned long , so we either have to use Long.parseUnsignedLong() or BigInteger . Also 1 << 63 returns 0 in Java , so I had to hard code the value of 263 .

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

    There is no disadvantage as Java has native support starting with version 8 (it is true that you have to use Long.parseUnsignedLong() but that's not a disadvantage).

    Please check my Java solution: https://www.codechef.com/viewsolution/15131819 (there is nothing hardcoded into it).

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

      That's really a cool way to solve the problem . I solved it in a different way and it required me to compute 263

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

    I guess no. The author solution in Java had nothing of that sort. You can see the source code here

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

Another way to solve MATDYS:

  1. Read the problem and realize you can get something with observation.
  2. Write bruteforce solution and check it with sending judge. https://www.codechef.com/viewsolution/15121998
  3. Print full array instead if k'th element with n=1 to 5.
  4. OBSERVE (observation skills++).
  5. Write simple recursive solution and gain 100 points. https://www.codechef.com/viewsolution/15122742
  6. PROFIT!!
→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I did the same. and I still have no idea how or why it works.

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

Why does this brute force solution for problem 3 fails in test 1Link Please help!

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

Can someone explain reason for WA?
MATDYS

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

Array of size 5*(10^8) allowed in question Mathison and the teleportation game. Are you serious bro ??? 256 mb was more than enough

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

I had some issues with problem B and couldn't resolve them yet. I hope someone helps me.

(1) My initial approach :

We wish to find the element at index k after all shuffles. We view the process backwards. So we try to transform the index k to some corresponding index j before the last shuffle. Then we use this j and apply the same process again. To find the transformation from k to j, we find the window in which k lies while shuffling (by using binary search) and next do the inverse transformation to find k. Here is the link to code using the mentioned approach. Though this doesn't handle the n=64 case (I still don't know how to store it :( ) I expected my solution to clear other subtasks but it failed.

(2) Then I wrote a brute force solution to stress test my solution.Here is the link to the code. It passed the basic test cases ie with n <= 10. I just wrote a script and compared the outputs from n=1 to n=15 (I basically compared the whole array after all shuffles) and I didn't find any difference.

I don't get the mistake even now. Are the constraints for subtask 1 definitely correct?! :D

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

    if(n==64) then in the first iteration you'll have to add 2^63(if number is odd).So just add 2^63(fits in unsigned long long) and decrement n by 1.After that you can do standard binary search.

    → Reply